一、选择排序

过程分析：

  1. 找到数组中最小的那个元素；
  2. 将它和数组的第一个元素交换位置（如果第一个元素就是最小元素，那么它就和自己交换）；
  3. 在剩下的元素中找到最小的元素，将它与数组的第二个元素交换位置；如此往复，直到将整个数组排序。

算法的时间效率取决于比较的次数。

注：对于长度为N的数组，选择排序需要大约N^2/2次比较和N次交换。

特点：

  1. 运行时间和输入无关；
  2. 数据移动最少；每次交换改变两个数组元素的值，选择排序用了N次交换——交换次数和数组大小呈线性关系。
  1. //升序排列
  2. public static void sort(int[] a){
  3.     int N = a.length;
  4.     for(int i = 0;i < N;i++){
  5.         int min = i;    //最小元素的索引
  6.         for(int j = i+1;j < N;j++){
  7.             if(a[j] < a[min]){
  8.                 min = j;
  9.             }
  10.         }
  11.         int temp = a[i];
  12.         a[i] = a[min];
  13.         a[min] = temp;
  14.     }
  15. }

二、插入排序

定义：选择要插入的元素，将其余所有元素在插入之前向右移动一位给要插入的元素腾出空间。

插入排序所需的时间取决于输入中元素的初始顺序。

注：对于随机排列的长度为N且主键不重复的数组，平均情况下插入排序需要N2/4次比较及N2/4次交换。最坏的情况下需要N2/2次比较及N2/2次交换，最好情况下需要N-1次比较和0次交换。

  1. public int[] sortArray(int[] nums){
  2.     int N = nums.length;
  3.     for(int i = 1;i<N;i++){
  4.         //将nums[i]依次前插
  5.         for(int j = i;j>0;j--){
  6.             if(nums[j]<nums[j-1]){
  7.                 int temp = nums[j];
  8.                 nums[j] = nums[j-1];
  9.                 nums[j-1] = temp;
  10.             }
  11.         }
  12.     }
  13.     return nums;
  14. }

注：插入排序需要的交换操作和数组中倒置的数量相同，需要的比较次数大于等于倒置的数量，小于等于倒置的数量加上数组的大小再减一。

插入排序对于部分有序的数组十分高效，也很适合小规模数组；对于大规模乱序数组插入排序很慢，因为它只会交换相邻的元素。

==对于随机排序的无重复主键的数组，插入排序和选择排序的运行时间是平方级别的，两者之比应该是一个较小的常数。==插入排序通常应该比选择排序稍快一些。

三、希尔排序

定义：一种基于插入排序的快速排序算法。

思想：使数组中任意间隔为h的元素都是有序的（h有序数组）；一个h有序数组就是h个互相独立的有序数组编织在一起组成的一个数组。对于每个h，用插入排序将h个子数组独立地排序/在插入排序的代码中将移动元素的距离由1改为h。

  1. //希尔排序
  2. public int[] sortArray(int[] nums){
  3.     int N = nums.length;
  4.     int h = 1;
  5.     while(h<N/3) h = 3*h+1;    //h = 1,4,13,40...
  6.     //疑问：为什么间隔h选择N/3
  7.     while(h>=1){
  8.         //将数组变为h有序
  9.         for(int i = h;i<N;i++){
  10.             for(int j = i;j>=h;j-=h){
  11.                 //将nums[i]依次前插h
  12.                 if(nums[j]<nums[j-h]){
  13.                     int temp = nums[j];
  14.                     nums[j] = nums[j-h];
  15.                     nums[j-h] = temp;
  16.                 }
  17.             }
  18.         }
  19.         h = h/3;    //将h有序的间隔逐渐缩小，直到间隔为1，此时排序完成
  20.     }
  21.     return nums;
  22. }

希尔排序比选择排序和插入排序要快的多，并且数组越大，优势越大。

注：使用递增序列1，4，13，40…的希尔排序所需的比较次数不会超出N的若干倍乘以递增序列的长度。

四、归并排序

定义：将两个有序的数组归并成一个更大的有序数组

性质：保证将任意长度为N的数组排序时间和NlogN成正比

缺点：所需的额外空间和N成正比

原地归并：

自顶向下的归并排序：

五、快速排序

public int[] quickSort(int[] arr, int left, int right){
    if(left > right){
        return arr;
    }
    int low = left,high = right;

    // 基准数
    int temp = arr[low];
    while(left < right){
        while(temp <= arr[right] && left < right){
            right--;
        }
        while(temp >= arr[left] && left < right){
            left++;
        }

        if(left < right){
            int swapTemp = arr[left];
            arr[left] = arr[right];
            arr[right] = swapTemp;
        }
    }

    arr[low] = arr[left];
    arr[left] = temp;
    quickSort(arr, low, left-1);
    quickSort(arr, left+1, high);

    return arr;
}