Java API中的排序

Arrays.sort(T[] t);是快速排序
Arrays.sort(T[] t,Comparator<? super T> c )是归并排序
Collection.sort(List list)，归并排序
Collection.sort(List list, Comparator<? super T> c)归并排序

选择排序

算法思想：将数组分为两个部分，一个为有序部分一个为无序部分，有序部分一开始为0。

  1. 先从无序部分选出最小的一个数放入有序部分（或者与第一个元素进行交换）。
  2. 接着不断的从无序部分选出最小或者最大的数放入有序部分。
  3. 最终得到一个有序队列

时间复杂度为N的平方，空间复杂度为常数，它与输入无关，即便是对一个已排序好的数组也需要比较和交换较多次数。

  1. //选择排序
  2.     public void selection(int[] nums){
  3.         int min;
  4.         for (int i = 0; i < nums.length; i++) {
  5.             min = nums[i];
  6.             for (int j = i; j <nums.length ; j++) {
  7.                 if (nums[j]<min){
  8.                     min = nums[j];
  9.                     swap(nums,i,j);
  10.                 }
  11.             }
  12.         }
  13.     }

插入排序

算法思想：每次将一个待排序的元素作为关键字，按照关键字大小插入到已排好序的适当位置上。直至无待排序的元素。
image.png

  1. public void selection(int[] nums){
  2.         int min;
  3.         for (int i = 0; i < nums.length - 1; i++) {
  4.             min = nums[i];
  5.             for (int j = i; j <nums.length ; j++) {
  6.                 if (nums[j]<min){
  7.                     min = nums[j];
  8.                     swap(nums,i,j);
  9.                 }
  10.             }
  11.         }
  12.     }

希尔排序

希尔排序为改进版插入排序
image.png
每次以一定的增量进行插入排序，再将增量每次缩小为原来的一半，直到增量为1，这是就实现了数组的有序。

冒泡排序

从左到右不断的交换相邻逆序的元素，在一次循环后，就可以让数组中最大的元素上浮到右侧。

可优化的地方，在一次遍历后，发现没有发生交换，说明数组已经是有序的，此时可以直接退出。

  1. public void bubble(int[] nums){
  2.         boolean sorted = false;
  3.         int N = nums.length;
  4.         for (int i = N-1; i >0 && !sorted; i--) {
  5.             sorted = true;
  6.             for (int j = 0; j < i; j++) {
  7.                 sorted = false;
  8.                 if (nums[j]>nums[j+1])swap(nums,j,j+1);
  9.             }
  10.         }
  11.     }

归并排序

利用递归将两个已经排好序的数组合并成一个

自顶向下的归并排序

分三个部分：

  1. 排序算法主体

    1. int[] aux;
    2. public void mergeSort(int[] nums){
    3.  aux = new int[nums.length];
    4.  sort(nums,0,nums.length-1);
    5. }

  2. 递归分解、合并

    1. public void sort(int[] nums,int l,int h){
    2.  if(l>=h) return;
    3.  int m = l+(h-l)/2;
    4.  sort(nums,l,m);
    5.  sort(nums,m+1,h);
    6.  merge(nums,l,m,h);
    7. }

  3. 合并同时排序

    1. public void merge(int[] nums,int l,int m,int h){
    2.  for(int i = l;i<=h,i++){
    3.      aux[i] = nums[i];
    4.  }
    5.  int i = l; int j = m+1;
    6.  for(int k = l;k<=h;k++){
    7.      if(i>m){
    8.          nums[k] = aux[j++];
    9.      }else if(j>h){
    10.          nums[k] = aux[i++];
    11.      }else if(aux[i]<=aux[j]){
    12.          nums[k] = aux[i++];
    13.      }else{
    14.          nums[k] = aux[j++];
    15.      }
    16.  }
    17. }

自底向上的归并排序

先归并整理较小的数组，向上得到较大的有序数组。

  1.     public void sort(int[] nums) {
  2.         int N = nums.length;
  3.         aux = new int[N];
  4.         for (int sz = 1; sz < N; sz += sz) {
  5.             for (int lo = 0; lo < N - sz; lo += sz + sz) {
  6.                 merge(nums, lo, lo + sz - 1, Math.min(lo + sz + sz - 1, N - 1));
  7.             }
  8.         }
  9.     }

快速排序

快排思想：通过切分一个元素，使元素左边的数组小于等于切分元素，元素右边的数组大于等于切分元素，那么这个元素在数组中的位置也就确定了，再对左边和右边的数组递归的使用快速排序，当数组中的每个元素都找到自己的位置之后，相当于数组已经排好序了。

算法步骤：

  1. 算法主体：递归

    1. public void quickSort(int[] nums){
    2.  sort(nums,0,nums.length);
    3. }
    4. public void sort(int[] nums,int l,int h){
    5.  if(l>=h) return;
    6.  int j = partition(nums,l,h);
    7.  sort(nums,l,j-1);
    8.  sort(nums,j+1,h);
    9. }

  2. 切分，并返回切分元素的位置

    1. public int partition(nums,l,h){
    2.  int i = l; int j = h+1;
    3.  while(true){
    4.      while(nums[++i]<nums[l]&&i<h);
    5.      while(nums[--j]>nums[l]&&j>l);
    6.      if(i>=j) break;
    7.      swap(nums,i,j)
    8.  }
    9.  swap(nums,l,j);
    10.  return j;
    11. }

快排的优化

  1. 三数取中：最好的情况是每次都能取数组的中位数作为切分元素，但精确的求出中位数的代价很高，折中方案是取三个元素，将大小居中的元素作为切分元素。
  2. 三向切分：使用两个变量将数组切分为三个部分，有利于大量重复元素的随机数组。
    1. public void ThreeQuickSort(int[] nums,int l,int h){
    2.  if(l>=h) return ;
    3.  int lt = l,i = l+1,gt = h;
    4.  int e = nums[l];
    5.  while(i<=gt){
    6.      if(nums[i]<e)
    7.          swap(nums,i++,lt++);
    8.      else if(nums[i]>e)
    9.          swap(nums,i,gt--);
    10.      else
    11.          i++;
    12.  }
    13.  sort(nums,l,lt-1);
    14.  sort(nums,gt+1,h);
    15. }

基于快排思想的快速选择（Kth Element）

快速定位第K大的元素（或者第K小的元素）

  1. public void quickChoice(int[] nums,int k){
  2.     int l = 0;int h = nums.length-1;
  3.     while(l<h){
  4.         int j = partition(nums,i,j);
  5.         if(j==k){
  6.             return nums[k];
  7.         }else if(j<k){
  8.             l = j+1;
  9.         }else{
  10.             h = j-1;
  11.         }
  12.     }
  13.     return nums[k];
  14. }

堆排序

堆

堆中某个节点的值总是大于等于其子节点的值，并且堆是一颗完全二叉树。

堆可以用数组来表示，这是因为堆是完全二叉树，而完全二叉树很容易就存储在数组中。位置 k 的节点的父节点位置为 k/2，而它的两个子节点的位置分别为 2k 和 2k+1。这里不使用数组索引为 0 的位置，是为了更清晰地描述节点的位置关系。

一个堆的高度为 logN，因此在堆中插入元素和删除最大元素的复杂度都为 logN。

对于堆排序，由于要对 N 个节点进行下沉操作，因此复杂度为 NlogN。

堆排序是一种原地排序，没有利用额外的空间。

现代操作系统很少使用堆排序，因为它无法利用局部性原理进行缓存，也就是数组元素很少和相邻的元素进行比较和交换。

排序算法的比较

算法 稳定性 时间复杂度 空间复杂度 备注
选择排序 × N2 1
冒泡排序 √ N2 1
插入排序 √ N ~ N2 1 时间复杂度和初始顺序有关
希尔排序 × N 的若干倍乘于递增序列的长度 1 改进版插入排序
快速排序 × NlogN logN
三向切分快速排序 × N ~ NlogN logN 适用于有大量重复主键
归并排序 √ NlogN N
堆排序 × NlogN 1 无法利用局部性原理

image.pngimage.png
快速排序是最快的通用排序算法，它的内循环的指令很少，而且它还能利用缓存，因为它总是顺序地访问数据。它的运行时间近似为~cNlogN，这里的 c 比其它线性对数级别的排序算法都要小。

使用三向切分快速排序，实际应用中可能出现的某些分布的输入能够达到线性级别，而其它排序算法仍然需要线性对数时间。

Java的Arrays.sort()实现

Java 主要排序方法为 java.util.Arrays.sort()，对于基本数据类型使用三向切分的快速排序，对于引用类型使用归并排序。