排序

插入排序（Insert Sort）

　　插入排序的原理很类似于我们抓扑克牌，对于未排序数据（右手抓到的牌），在已排序序列（左手已经排好序的手牌）中从后向前扫描，找到相应位置并插入。 　　　　　　 　　插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。　　 　　对序列{ 6, 5, 3, 1, 8, 7, 2, 4 }进行插入排序的实现过程如下　　　　 　　　　 　 　　具体算法如下： 　　 　　1 从第一个元素开始，该元素可以认为已经被排序 　　2 取出下一个元素，在已经排序的元素序列中从后向前扫描 　　3 如果已排序的元素大于新元素，就将该元素移到后面一个位置 　　4 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置 　　5 将新元素插入到该位置后 　　6 重复步骤2~5　　

// 分类 ------------- 内部比较排序 // 数据结构 ---------- 数组 // 最差时间复杂度 ---- 最坏情况为输入序列是降序排列的,此时时间复杂度O(n^2) // 最优时间复杂度 ---- 最好情况为输入序列是升序排列的,此时时间复杂度O(n) // 平均时间复杂度 ---- O(n^2) // 所需辅助空间 ------ O(1) // 稳定性 ------------ 稳定 public static void insertSort(int[] a){ for(int i=1;i<a.length;i++){//类似抓扑克牌排序 if(a[i]<a[i-1]){ int get = a[i]; //右手抓到一张扑克牌 int j = i-1; //拿在左手上的牌总是排序好的 while(j>=0 && a[j]> get){ //将抓到的牌与手牌从右向左进行比较 a[j+1] = a[j]; //如果该手牌比抓到的牌大，就将其右移 j--; } a[j+1] = get; //直到该手牌比抓到的牌小（或二者相等），将抓到的牌插入到该手牌右边(相等元素的相对次序未变，所以插入排序是稳定的) } } }

　　插入排序不适合对于数据量比较大的排序应用。但是，如果需要排序的数据量很小，比如量级小于千，那么插入排序还是一个不错的选择。 插入排序在工业级库中也有着广泛的应用，在STL的sort算法和stdlib的qsort算法中，都将插入排序作为快速排序的补充，用于少量元素的排序（通常为8个或以下）。

希尔排序

　　以n=10的一个数组49, 38, 65, 97, 26, 13, 27, 49, 55, 4为例 　　第一次 gap = 10 / 2 = 5

49 38 65 97 26 13 27 49 55 4 1A 1B 2A 2B 3A 3B 4A 4B 5A 5B

　　1A,1B，2A,2B等为分组标记，数字相同的表示在同一组，大写字母表示是该组的第几个元素， 每次对同一组的数据进行直接插入排序。即分成了五组(49, 13) (38, 27) (65, 49) (97, 55) (26, 4)这样每组排序后就变成了(13, 49) (27, 38) (49, 65) (55, 97) (4, 26)，下同。

　　第二次 gap = 5 / 2 = 2

　　排序后

13 27 49 55 4 49 38 65 97 26 1A 1B 1C 1D 1E 2A 2B 2C 2D 2E

　　第三次 gap = 2 / 2 = 1

4 26 13 27 38 49 49 55 97 65 1A 1B 1C 1D 1E 1F 1G 1H 1I 1J

　　第四次 gap = 1 / 2 = 0 排序完成得到数组：

4 13 26 27 38 49 49 55 65 97

　　希尔排序的实质就是分组插入排序，该方法又称缩小增量排序，是基于插入排序的以下两点性质而提出改进方法的： - 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率 - 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位　　 　　该方法的基本思想是：先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下（接近最好情况），效率是很高的，因此希尔排序在时间效率上有较大提高。

// 分类 -------------- 内部比较排序 // 数据结构 ---------- 数组 // 最差时间复杂度 ---- 根据步长序列的不同而不同。已知最好的为O(n(logn)^2) // 最优时间复杂度 ---- O(n) // 平均时间复杂度 ---- 根据步长序列的不同而不同。 // 所需辅助空间 ------ O(1) // 稳定性 ------------ 不稳定 public static void shellSort(int[] a){ int len = a.length; for(int step = len/2; step>0; step /=2){//步长从一半长度开始 for(int j =step; j< len;j +=step){//每次插入排序从step开始，（0位已经排好） if (a[j] < a[j-step]){ int get = a[j]; int k = j - step; while (k >= 0 && a[k]> get){ a[k + step] = a[k]; k = k - step; } a[k + step] = get; } } } }

选择排序 （Selection Sort）

　　对序列{ 8, 5, 2, 6, 9, 3, 1, 4, 0, 7 }进行选择排序的实现过程如右图： 　　简单选择排序的基本思想：比较+交换。 　　1 从待排序序列中，找到关键字最小的元素； 　　2 如果最小元素不是待排序序列的第一个元素，将其和第一个元素互换； 　　3 从余下的 N - 1 个元素中，找出关键字最小的元素，重复1、2步，直到排序结束。

// 分类 -------------- 内部比较排序 // 数据结构 ---------- 数组 // 最差时间复杂度 ---- O(n^2) // 最优时间复杂度 ---- O(n^2) // 平均时间复杂度 ---- O(n^2) // 所需辅助空间 ------ O(1) // 稳定性 ------------ 不稳定 public static void selectionSort(int[] a){ //遍历所有元素 for(int i=0;i<a.length-1;i++){//注意，此处为a.length -1 int min = i;//用min记录最小元素的位置 //将当前元素依次与余下的元素进行比较，如果当前元素不是最小元素，则与最小元素交换 for(int j= i+1;j<a.length;j++){//未排序序列 if(a[j] < a[min] ){//找出未排序序列中的最小值 min = j; } } if (min != i){//最小元素的位置发生改变则交换 int temp = a[i]; a[i] = a[min]; a[min] = temp; } } }

　　注意选择排序与冒泡排序的区别：冒泡排序通过依次交换相邻两个顺序不合法的元素位置，从而将当前最小（大）元素放到合适的位置；而选择排序每遍历一次都记住了当前最小（大）元素的位置，最后仅需一次交换操作即可将其放到合适的位置。 　 　　选择排序是不稳定的排序算法，不稳定发生在最小元素与A[i]交换的时刻。 　　比如序列：{ 5, 8, 5, 2, 9 }，一次选择的最小元素是2，然后把2和第一个5进行交换，从而改变了两个元素5的相对次序。

堆排序

　　完全二叉树(complete binary tree)有严格的形状要求：从根节点起每一层从左到右填充。一棵高度为d的完全二叉树除了d-1层以外，每一层都是满的。底层叶节点集中在左边的若干位置上。 　　堆实际上是一棵完全二叉树，其任何一非叶节点满足性质： 　a)任何一非叶节点的关键字不大于其左右孩子节点的关键字,称之为最小堆（堆顶的数最小）。 　b)任何一非叶节点的关键字不小于其左右孩子节点的关键字,称之为最大堆（堆顶的数最大）。 　　通常堆是通过一维数组来实现的，在起始位置为0的情形中： 　(1) 节点i的左子节点在位置(2*i+1); 　(2) 节点i的右子节点在位置(2*i+2); 　(3) 节点i的父节点在位置floor((i-1)/2);（(i-1)/2取整） 　　堆排序的过程： 　(1) 由输入的无序数组构造一个最大堆，作为初始的无序区 　(2) 把堆顶元素（最大值）和堆尾元素互换 　(3) 把堆（无序区）的尺寸缩小1，从新的堆顶元素开始进行堆调整 　(4) 重复步骤2，直到堆的尺寸为1 　其中堆调整的过程： 　

　　　　　　　 　　　　　　　

// 分类 -------------- 内部比较排序 // 数据结构 ---------- 数组 // 最差时间复杂度 ---- O(nlogn) // 最优时间复杂度 ---- O(nlogn) // 平均时间复杂度 ---- O(nlogn) // 所需辅助空间 ------ O(1) // 稳定性 ------------ 不稳定 public static void heapSort(int[] a){ if(a == null || a.length <=1){ return; } buildMaxHeap(a);//调整为最大堆 //将数组分为两部分，一部分为有序区，在数组末尾，另一部分为无序区，堆属于无序区。 for(int i=a.length -1;i>0;i--){ //1 将堆顶数字和最后一个数字交换，把堆的大小-1 // 此处交换操作很有可能把后面元素的稳定性打乱，所以堆排序是不稳定的排序算法 int temp = a[i]; a[i] = a[0]; a[0] = temp; //2 将新得到的堆调整为最大堆 adjustHeap(a,i,0); } } public static void buildMaxHeap(int[] a){ if(a == null || a.length <=1){ return; } int lastRoot = (a.length-1)/2;//从最后一个非叶子节点开始调整 for (int i=lastRoot;i>=0;i--){ adjustHeap(a,a.length,i); } } public static void adjustHeap(int[] a, int heapSize, int index) { int left = index*2 + 1 ; //左孩子 int right = index*2 + 2; //右孩子 int max = index;//存放最大值的所在的位置 //找出根节点和左右子节点中的最大值 if (left < heapSize && a[left] > a[max]){ max = left; } if(right < heapSize && a[right] > a[max]){ max = right; } if (index != max){//如果最大值不在根节点，则把最大值交换到根节点 int temp = a[index]; a[index] = a[max]; a[max] = temp; adjustHeap(a,heapSize,max); } }

　　堆排序是不稳定的排序算法，不稳定发生在堆顶元素与a[i]交换的时刻。

　　比如序列：{ 9, 5, 7, 5 }，堆顶元素是9，堆排序下一步将9和第二个5进行交换，得到序列 { 5, 5, 7, 9 }，再进行堆调整得到{ 7, 5, 5, 9 }，重复之前的操作最后得到{ 5, 5, 7, 9 }从而改变了两个5的相对次序。

冒泡排序

　　对{6，5，3，1，8，7，2，4}进行冒泡排序： 　　　 　　冒泡排序算法的运作如下： 　1 比较相邻的元素，如果前一个比后一个大，就把它们两个调换位置。 　2 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。 　3 针对所有的元素重复以上的步骤，除了最后一个。 　4 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

// 分类 -------------- 内部比较排序 // 数据结构 ---------- 数组 // 最差时间复杂度 ---- O(n^2) // 最优时间复杂度 ---- 如果能在内部循环第一次运行时,使用一个旗标来表示有无需要交换的可能,可以把最优时间复杂度降低到O(n) // 平均时间复杂度 ---- O(n^2) // 所需辅助空间 ------ O(1) // 稳定性 ------------ 稳定 public static void bubbleSort(int[] a){ boolean flag = true; while (flag == true){ flag = false; for (int j=0;j<a.length-1;j++){ // 依次比较相邻的两个元素,使较大的那个向后移 if(a[j]>a[j+1]){// 如果条件改成a[j] >= a[j + 1],则变为不稳定的排序算法 int temp = a[j]; a[j]=a[j+1]; a[j+1] = temp; flag = true;//如果一次循环没有交换数据，则flag=false退出循环 } } } }

快速排序

// 分类 ------------ 内部比较排序 // 数据结构 --------- 数组 // 最差时间复杂度 ---- 每次选取的基准都是最大（或最小）的元素，导致每次只划分出了一个分区，需要进行n-1次划分才能结束递归，时间复杂度为O(n^2) // 最优时间复杂度 ---- 每次选取的基准都是中位数，这样每次都均匀的划分出两个分区，只需要logn次划分就能结束递归，时间复杂度为O(nlogn) // 平均时间复杂度 ---- O(nlogn) // 所需辅助空间 ------ 主要是递归造成的栈空间的使用(用来保存left和right等局部变量)，取决于递归树的深度，一般为O(logn)，最差为O(n) // 稳定性 ---------- 不稳定 public int[] sort(int[] A, int n){ if (n == 0 || A == null) { return null; } quickSort(A, 0, n - 1); return A; } public void quickSort(int[] a,int left,int right){ int i,j,t,temp; if (left > right){ return; } temp = a[left]; i = left; j = right; while(i != j){ while (a[j]>=temp && i<j){ j--; } while (a[i]<=temp && i<j){ i++; } if (i<j){ t = a[i]; a[i]=a[j]; a[j]=t; } } a[left] = a[i]; a[i] = temp; quickSort(a,left,i-1); quickSort(a,i+1,right); }

归并排序

　　对序列{ 6, 5, 3, 1, 8, 7, 2, 4 }进行归并排序的实例如下： 　　 　　 　　算法如下： 　　 　　1 申请空间，使其大小为已经排序的两个序列的长度之和，用来存放归并后的序列 　　2 设置两个指针，分别指向两个已经排序的序列的起始位置 　　3 比较两个指针所指向的的元素，选择比较小的放入到合并空间，并移动指针到下一个位置 　　4 重复步骤3直到某一指针达到序列末尾 　　5 将另一序列剩下的所有元素直接复制到合并序列尾　　

// 分类 -------------- 内部比较排序 // 数据结构 ---------- 数组 // 最差时间复杂度 ---- O(nlogn) // 最优时间复杂度 ---- O(nlogn) // 平均时间复杂度 ---- O(nlogn) // 所需辅助空间 ------ O(n) // 稳定性 ------------ 稳定 public static void merge(int[] a,int low,int mid, int high){ int[] temp = new int[high - low + 1]; int i = low;//前一个数组起始 int j = mid + 1;//后一个数组起始 int index = 0; while (i <= mid && j <= high ){ if(a[i] <= a[j]){//带等号保证归并排序的稳定性 temp[index++] = a[i++]; }else{ temp[index++] = a[j++]; } } //当一组数据全部填充以后，将另一组剩余的数据一起添加到后面 while(i <= mid ){ temp[index++] = a[i++]; } while(j <= high){ temp[index++] = a[j++]; } //填充到原来的数组中 for(int k = 0; k < temp.length;k++){ a[low++] = temp[k]; } } public static void mergeSort(int[] a,int low,int high){ //当待排序列长度为1时，递归开始回溯，进行merge操作 if (low == high){ return; } int mid = (low + high)/2; mergeSort(a,low,mid); mergeSort(a,mid+1,high); merge(a,low,mid,high); }

Java系统提供的Arrays.sort函数。对于基础类型，底层使用快速排序。对于非基础类型，底层使用归并排序。请问是为什么？

　　答：这是考虑到排序算法的稳定性。对于基础类型，相同值是无差别的，排序前后相同值的相对位置并不重要，所以选择更为高效的快速排序，尽管它是不稳定的排序算法；而对于非基础类型，排序前后相等实例的相对位置不宜改变，所以选择稳定的归并排序。