八大经典排序算法详解
我记得上大学的时候，老师一直跟我们强调：“算法才是编程的灵魂”，找工作面试的时候，算法和数据结构也是绝对不可避免的，面试官可能一言不合就让你手写一个排序算法。
我把最经典的八大排序算法原理和代码也都整理出来了，内容如下，希望对大家能有所帮助。
插入排序
•基本思想：每步将一个待排序的纪录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。•算法适用于少量数据的排序，时间复杂度为O(n^2)。是稳定的排序方法。•代码：
public static void insertionSort(int[] array){ int tmp; for(int i=1;i<array.length;i++){ tmp = array[i]; //将当前位置的数给tmp int j = i; for(;j>0&&array[j-1]>tmp;j--){ /* 往右移，腾出左边的位置, array[j-1]>tmp:大于号是升序排列，小于号是降序排列 */ array[j] = array[j-1]; } //将当前位置的数插入到合适的位置 array[j] = tmp; } }冒泡排序
•基本思想：持续比较相邻的元素。如果第一个比第二个大，就交换他们两个。直到没有任何一对数字需要比较。•冒泡排序最好的时间复杂度为O(n)。冒泡排序的最坏时间复杂度为O(n^2)。因此冒泡排序总的平均时间复杂度为O(n^2)。•算法适用于少量数据的排序，是稳定的排序方法。•代码：
public static void bubbleSort(int[] array){ int tmp; boolean flag = false; //设置是否发生交换的标志 for(int i = array.length-1;i >= 0;i--){ for(int j=0;j<i;j++){ //每一轮都找到一个最大的数放在右边 if(array[j]>array[j+1]){ tmp = array[j]; array[j] = array[j+1]; array[j+1] = tmp; flag = true; //发生了交换 } } if(!flag) break; //这一轮循环没有发生交换，说明排序已经完成，退出循环 } }选择排序
•基本思想：每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。•选择排序是不稳定的排序方法。时间复杂度 O(n^2)。•代码：
public static void selectSort(int[] array){ for(int i = 0;i<array.length-1;i++){ int min = array[i]; int minindex = i; for(int j = i;j<array.length;j++){ if(array[j]<min){ //选择当前最小的数 min = array[j]; minindex = j; } } if(i != minindex){ //若i不是当前元素最小的，则和找到的那个元素交换 array[minindex] = array[i]; array[i] = min; } } }希尔排序
•基本思想：先取一个小于n的整数d1作为第一个增量，把文件的全部记录分组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量dt=1(dt<dt-1…<d2<d1)，即所有记录放在同一组中进行直接插入排序为止。•在使用增量dk的一趟排序之后，对于每一个i，我们都有a[i]<=a[i+dk],即所有相隔dk的元素都被排序。•如图：增量序列为5，3，1，每一趟排序之后，相隔对应增量的元素都被排序了。当增量为1时，数组元素全部被排序。
希尔排序算法原理
•希尔排序不稳定，时间复杂度 平均时间 O(nlogn) 最差时间O(n^2)•代码：
public static void shellSort(int[] array){ int j; for(int gap = array.length/2; gap>0; gap /= 2){ //定义一个增长序列，即分割数组的增量,d1=N/2 dk=(d(k-1))/2 for(int i = gap; i<array.length;i++){ int tmp = array[i]; for( j =i; j>=gap&&tmp<array[j-gap]; j -= gap){ //将相距为Dk的元素进行排序 array[j] = array[j-gap]; } array[j] = tmp; } } }堆排序
•预备知识：
二叉堆是完全二元树（二叉树）或者是近似完全二元树（二叉树）。二叉堆有两种：最大堆和最小堆。大根堆：父结点的键值总是大于或等于任何一个子节点的键值；小根堆：父结点的键值总是小于或等于任何一个子节点的键值。二叉堆一般用数组来表示。例如，根节点在数组中的位置是0，第n个位置的子节点分别在2n+1和 2n+2。因此，第0个位置的子节点在1和2，1的子节点在3和4。以此类推。这种存储方式便於寻找父节点和子节点。例如初始要排序的数组为：49, 38, 65, 97, 76, 13, 27, 49 构造成大根堆之后的数组为：97 76 65 49 49 13 27 38 实际树形结构如图（最大堆）：
实际树形结构（最大堆）
•堆排序基本思想：在排序过程中，将R[l..n]看成是一棵完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系【参见二叉树的顺序存储结构】，在当前无序区中选择关键字最大(或最小)的记录。堆排序利用了大根堆(或小根堆)堆顶记录的关键字最大(或最小)这一特征，使得在当前无序区中选取最大(或最小)关键字的记录变得简单。•堆排序是一种选择排序,其时间复杂度为O(nlogn)。堆排序是不稳定的•代码：
```/* * 堆排序 * 调整最大堆，交换根元素和最后一个元素。 * 参数说明： * a -- 待排序的数组 */ public static void heapSort(int[] a) { int n = a.length; int i,tmp; // 从(n/2-1) --> 0逐次遍历。遍历之后，得到的数组实际上是一个(最大)二叉堆。 for (i = n / 2 - 1; i >= 0; i--) maxHeapDown(a, i, n-1); // 从最后一个元素开始对序列进行调整，不断的缩小调整的范围直到第一个元素 for (i = n - 1; i > 0; i--) { // 交换a[0]和a[i]。交换后，a[i]是a[0...i]中最大的。 tmp = a[0]; a[0] = a[i]; a[i] = tmp; // 调整a[0...i-1]，使得a[0...i-1]仍然是一个最大堆。 // 即，保证a[i-1]是a[0...i-1]中的最大值。 maxHeapDown(a, 0, i-1); } } /* * 注：数组实现的堆中，第N个节点的左孩子的索引值是(2N+1)，右孩子的索引是(2N+2)。 * 其中，N为数组下标索引值，如数组中第1个数对应的N为0。 * * 参数说明： * a -- 待排序的数组 * start -- 被下调节点的起始位置(一般为0，表示从第1个开始) * end -- 截至范围(一般为数组中最后一个元素的索引) */ public static void maxHeapDown(int[] a, int start, int end) { int c = start; // 当前(current)节点的位置 int l = 2*c + 1; // 左(left)孩子的位置 int tmp = a[c]; // 当前(current)节点的大小 for (; l <= end; c=l,l=2*l+1) { // "l"是左孩子，"l+1"是右孩子 if ( l < end && a[l] < a[l+1]) l++; // 左右两孩子中选择较大者，即m_heap[l+1] if (tmp >= a[l]) break; // 调整结束 else { // 交换值 a[c] = a[l]; a[l]= tmp; } } }```归并排序
•归并排序的原理•将待排序的数组分成前后两个部分，再递归的将前半部分数据和后半部分的数据各自归并排序，得到的两部分数据，然后使用merge合并算法（算法见代码）将两部分算法合并到一起。例如：如果N=1；那么只有一个数据要排序，N=2，只需要调用merge函数将前后合并，N=4，........... 也就是将一个很多数据的数组分成前后两部分，然后不断递归归并排序，再合并，最后返回有序的数组。•归并排序的时间复杂度•归并排序的最好、最坏和平均时间复杂度都是O(nlogn)，而空间复杂度是O(n)，比较次数介于(nlogn)/2和(nlogn)-n+1，赋值操作的次数是(2nlogn)。因此可以看出，归并排序算法比较占用内存，但却是效率高且稳定的排序算法。•代码：
public class MergeSort { private static void mergeSort(int[] array,int[] tmp,int left,int right){ if(left<right){ int center = ( left + right ) / 2;//取数组的中点 mergeSort(array,tmp,left,center);//归并排序数组的前半部分 mergeSort(array,tmp,center+1,right);//归并排序数组的后半部分 merge(array,tmp,left,center+1,right);//将数组的前后半部分合并 } } /* * 超简单的合并函数 */ private static void merge(int[] array, int[] tmp, int leftPos, int rightPos, int rightEnd) { // TODO Auto-generated method stub int leftEnd = rightPos - 1; int tmpPos = leftPos; int numElements = rightEnd - leftPos + 1; while(leftPos <= leftEnd && rightPos <= rightEnd){ if(array[leftPos]<=array[rightPos]){ tmp[tmpPos++] = array[leftPos++]; }else{ tmp[tmpPos++] = array[rightPos++]; } } while(leftPos <= leftEnd){ tmp[tmpPos++] = array[leftPos++]; } while(rightPos <= rightEnd){ tmp[tmpPos++] = array[rightPos++]; } for(int i=0;i<numElements;i++,rightEnd--){ array[rightEnd] = tmp[rightEnd]; } } public static void mergeSort(int[] array){ int[] tmp = new int[array.length];//声明一个用来合并的数组 mergeSort(array,tmp,0,array.length-1);//调用排序函数，传入数字的起点和终点 } }快速排序
•快速排序原理：1.如果数组S中元素是0或者1，则返回；2.区数组S中任一元素v，称之为枢纽元；3.将S-{v}（S中剩余的元素）划分成连个不相交的集合：S1={S-{v}|x<=v}和S2={S-{v}|x>=v};4.返回{quicksort(s1)}后跟v，继而返回{quicksort(S2)}。•选取枢纽元（三数中值分割法）•一般的做法是使用左端、右端和中心位置上的三个元素的中值作为基元。分割策略：在分割阶段吧所有小元素移到数组的左边，大元素移到数组右边。，大小是相对于枢纽元素而言的。当i在j的左边时，将i右移，移过哪些小于枢纽元的元素，并将j左移，已过那些大于枢纽元的元素，当i和j停止时，i指向一个大元素，而j指向一个小元素，如果i在j的左边，那么将这两个元素交换，其效果是把一个大元素推向右边，而把小元素推向左边。效果如图：
分割策略
•快速排序平均时间复杂度为O(nlogn)，最坏情况为O(n^2)，n越大，速度越快。不是稳定的排序算法。•代码：
/* * 快速排序 * 两个方向，左边的i下标一直往右走，当a[i] <= a[center_index]， * 其中center_index是中枢元素的数组下标，而右边的j下标一直往左走，当a[j] > a[center_index] * 如果i和j都走不动了，i <= j, 交换a[i]和a[j],重复上面的过程，直到i>j * 交换a[j]和a[center_index]，完成一趟快速排序 * 枢轴采用三数中值分割法可以优化 */ //递归快速排序 public static void quickSort(int a[]){ qSort(a, 0, a.length - 1); } //递归排序，利用两路划分 public static void qSort(int a[],int low,int high){ int pivot = 0; if(low < high){ //将数组一分为二 pivot = partition(a,low,high); //对第一部分进行递归排序 qSort(a,low,pivot); //对第二部分进行递归排序 qSort(a,pivot + 1,high); } } //partition函数，实现三数中值分割法 public static int partition(int a[],int low,int high){ int pivotkey = a[low]; //选取第一个元素为枢轴记录 while(low < high){ //将比枢轴记录小的交换到低端 while(low < high && a[high] >= pivotkey){ high--; } //采用替换而不是交换的方式操作 a[low] = a[high]; //将比枢轴记录大的交换到高端 while(low < high && a[low] <= pivotkey){ low++; } a[high] = a[low]; } //枢纽所在位置赋值 a[low] = pivotkey; //返回枢纽所在的位置 return low; }桶式排序
•桶式排序不再是一种基于比较的排序方法，它是一种比较巧妙的排序方式，但这种排序方式需要待排序的序列满足以下两个特征：待排序列所有的值处于一个可枚举的范围之类；待排序列所在的这个可枚举的范围不应该太大，否则排序开销太大。•排序的具体步骤如下：(1)对于这个可枚举范围构建一个buckets数组，用于记录“落入”每个桶中元素的个数；(2)将（1）中得到的buckets数组重新进行计算，按如下公式重新计算：
buckets[i] = buckets[i] +buckets[i-1] (其中1<=i<buckets.length);•桶式排序是一种非常优秀的排序算法，时间效率极高，它只要通过2轮遍历：第1轮遍历待排数据，统计每个待排数据“落入”各桶中的个数，第2轮遍历buckets用于重新计算buckets中元素的值，2轮遍历后就可以得到每个待排数据在有序序列中的位置，然后将各个数据项依次放入指定位置即可。•桶式排序的空间开销较大，它需要两个数组，第1个buckets数组用于记录“落入”各桶中元素的个数，进而保存各元素在有序序列中的位置，第2个数组用于缓存待排数据.•桶式排序是稳定的。如果待排序数据的范围在0~k之间，那么它的时间复杂度是O(k+n)的.•但是它的限制多，比如它只能排整形数组。而且当k较大，而数组长度n较小，即k>>n时，辅助数组C[k+1]的空间消耗较大。当数组为整形，且k和n接近时, 可以用此方法排序。•代码实现：
//min的值为0，max的值为待排序数组中最大值+1public static void bucketSort(int[] data, int min, int max) { // 缓存数组 int[] tmp = new int[data.length]; // buckets用于记录待排序元素的信息 // buckets数组定义了max-min个桶 int[] buckets = new int[max - min]; // 计算每个元素在序列出现的次数 for (int i = 0; i < data.length; i++) { buckets[data[i] - min]++; } // 计算“落入”各桶内的元素在有序序列中的位置 for (int i = 1; i < max - min; i++) { buckets[i] = buckets[i] + buckets[i - 1]; } // 将data中的元素完全复制到tmp数组中 System.arraycopy(data, 0, tmp, 0, data.length); // 根据buckets数组中的信息将待排序列的各元素放入相应位置 for (int k = data.length - 1; k >= 0; k--) { data[--buckets[tmp[k] - min]] = tmp[k]; } } 总结
•下面是一个总的表格，大致总结了我们常见的所有的排序算法的特点。
•性能测试
100000个随机数测试
腾讯云开发者
