简单排序算法

选择排序

选择排序的一次遍历是选择一个最大的元素然后跟最后一个元素交换。

void selectionSort(int a[]) {
   if(a == null || a.length <= 1) return ;
   int n = a.length;
   // i=0 就不需要再比较了，已经有序了
   for(int i = n - 1; i > 0; i--) {
      int maxIdx = i;
      for(int j = 0; j <= i;  j++) {
          if(a[j] > a[maxIdx]) {
             maxIdx = j;
          }
      }
      int temp = a[maxIdx];
      a[maxIdx] = a[i];
      a[i] = temp;
   }
}

冒泡排序

冒泡排序跟选择排序类似，每次也是将最大的元素放置到最后一个元素。跟选择排序不同的是，冒泡每次都是两两比较，如果前者比后者大就交换，那么一次遍历完成后最大的元素就在数组的最后一个位置。

void bubbleSort(int a[]) {
  if(a == null || a.length <= 1) return;
  int n = a.length;
  for(int i = 0; i < n - 1; i++) {
      for(int j = 0; j < n - 1 - i; j++) {
          if(a[j] > a[j + 1]) {
             int tmp = a[j];
            a[j] = a[j + 1];
            a[j + 1] = tmp;
          }
      }
  }
}

插入排序

插入排序的思想是将一个数字插入到一个有序列表。如5, 3, 1进行排序。

1. 首先认为第一个元素5是一个有序列表，考虑将1插入这个有序列表中。5跟3交换即可==> 3,5
2. 然后将1插入到3,5这个有序列表中。首先5,1交换==>3,1,5，然后3,1交换==>1,3,5

static void insertSort(int a[]) {
    if(a == null || a.length <= 1) return;
        int n = a.length;
        for(int i = 1; i < n; i++) {
            for(int j = i - 1; j >= 0 && a[j] > a[j + 1]; j--) {
                int temp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = temp;
            }
        }
 }

希尔排序

希尔排序是插入排序改进版本。参考：https://www.runoob.com/data-structures/shell-sort.html

  static void shellSort(int a[]) {
        if(a == null || a.length <= 1) return;
        int n = a.length;
        for(int gap = n / 2; gap > 0; gap/=2) {
            for(int i = gap; i < n; i++) {
                for(int j = i - gap; j >= 0 && a[j] > a[j + gap]; j-=gap) {
                    int temp = a[j];
                    a[j] = a[j + gap];
                    a[j + gap] = temp;
                }
            }
        }
    }