主要排序算法性能对比
冒泡排序
各位同学接触最早的排序算法应该就是冒泡排序了，他的过程如下图所示：
拿图中升序举例他每次小循环都会从0开始在遍历的过程中将遇到的最大的数像冒泡泡一样一路冒到有序区间，一次大循环让有序区间增加一，大循环执行完毕全部区间就有序了。下面是它的代码：
import java.util.Arrays;
public class BubbleSort {
//升序
public static void bubbleSort(int[] array){
for (int i = 0; i < array.length - 1; i++){
//优化冒泡排序的变量
boolean judge = true;
for (int j = 0; j < array.length - i - 1; j++){
//若要降序将 > 改为 < 即可
if (array[j] > array[j + 1]){
int t = array[j];
array[j] = array[j + 1];
array[j + 1] = t;
judge = false;
}
}
if (judge)
return;
}
}
public static void main(String[] args) {
int[] array = { 1, 7, 6, 5, 2};
bubbleSort(array);
System.out.println(Arrays.toString(array));
}
}
运行结果：
选择排序
选择排序和冒泡排序最像，但是选排是每次大循环选出一个最值，记住它的下标，最后和无序区间的最后一个数交换，依次来让有序区间加一，而冒泡排序是在遍历的过程中换。
选择排序过程：
可以看上图，在每次遍历无序区间的时候都会选出一个最大值记住下标，在遍历结束后拿下标和无序区间最后一个交换。
代码实现：
public class SelectSort {
/*
选择排序是每次遍历序列选出最大（小）放到无序区间最后一个
*/
//升序
public static void selectSort(int[] array){
for (int i = 0; i < array.length; i++){
int minVal = array[0];
int minIdex = 0;
for (int j = 1; j < array.length - i; j++){
//若要降序将 > 改为 < 即可
if (array[j] > minVal){
minIdex = j;
minVal = array[j];
}
}
array[minIdex] = array[array.length - i - 1];
array[array.length - i - 1] = minVal;
}
}
public static void main(String[] args) {
int[] array = { 1, 2, 6, 5, 7};
selectSort(array);
System.out.println(Arrays.toString(array));
}
}
运行结果：
插入排序
插入排序相比上面两种排序会稍微复杂一些，开始的时候他把第一个元素看做有序区间，然后每次拿无序区间第一个数去依次和有序区间的数作比较，找到自己的位子，然后插入。下面这个图就很明了了：
下面是代码实现：
//升序
public static void insertSort(int[] array){
for (int i = 1; i < array.length; i++){
int index = 0;
int val = array[i];
for (int j = i - 1; j >= 0; j--){
//若要降序将 > 改为 < 即可
if (val > array[j]){
index = j + 1;
break;
}
array[j + 1] = array[j];
}
array[index] = val;
}
}
public static void main(String[] args) {
int[] array = { 1, 5, 6, 7, 2 };
insertSort(array);
System.out.println(Arrays.toString(array));
}
}
运行结果：
堆排序
堆排序中用到了建立大小堆和向下调整的内容，对这些内容有些不了解的同学可以去补一补专门写堆的博客，方便更好的理解堆排序数据结构之堆（Heap），堆的相关操作，用堆模拟优先级队列。
如果把待排序序列分为未排序区间和有序区间，堆排序大的思想是每次选一个数放到有序区间，没经历一个循环有序区间就会加一，无序区间减一，循环结束序列也就有序了，像这样：
可以发现堆排序的思路和选择排序很像，没错，思路确实一样，只不过选择排序每次要遍历无序区间去找当前无序区间的最大值（升序找最大值，降序找最小值），而堆排序呢是吧无序区间看做一个堆，堆顶自然是这个堆的最值了，每次循环只需要将堆顶元素取出来和无序区间最后一个数交换以达到有序区间加一的目的，然后在对这个堆（注意此时堆的size减一）向下调整，这样做之后下次循环继续取堆顶元素和无序区间最后一个元素交换然后继续循环。。。。。。直到无序区间就剩一个元素，此时整个序列就有序了。下面是图解（图中无序区间是堆，右下角红色是有序区间注意观察）：
好了知道了原理之后我们来介绍具体实现。
对于堆排序在实现的时候要知道：
- 待排序序列需要升序排列那么要建大堆
- 待排序序列需要降序排列那么要建小堆
为什么要有上面的两条规定呢？要升序排列就不能建小堆，要降序排列就不能建大堆吗？这个问题大家先自己思考一下，我们先讨论代码实现之后在对这个问题进行讨论：
升序大堆
//建大堆升序
public static void heapSort1(int[] array){
createHeap1(array);
for (int i = 1; i < array.length; i++){
int t = array[0];
int lastIndex = array.length - i;
array[0] = array[lastIndex];
array[lastIndex] = t;
shiftDown1(array, lastIndex, 0);
}
}
//建大堆
public static void createHeap1(int[] array){
int size = array.length;
int parent = (size - 2) / 2;
for (int i = parent; i >= 0; i--){
shiftDown1(array, size, i);
}
}
//大堆向下调整
public static void shiftDown1(int[] array, int size, int index){
while (true){
int leftChild = index * 2 + 1;
if (leftChild >= size){
return;
}
int rightChild = leftChild + 1;
int bigIndex = leftChild;
int bigVal = array[leftChild];
if (rightChild < size && array[rightChild] > bigVal){
bigIndex = rightChild;
bigVal = array[rightChild];
}
if (array[index] >= bigVal){
return;
}
array[bigIndex] = array[index];
array[index] = bigVal;
index = bigIndex;
}
}
降序小堆：
//降序建小堆
public static void heapSort2(int[] array){
createHeap2(array);
for (int i = 1; i < array.length; i++){
int lastIndex = array.length - i;
int t = array[0];
array[0] = array[lastIndex];
array[lastIndex] = t;
shiftDown2(array, lastIndex, 0);
}
}
//建小堆
public static void createHeap2(int[] array){
int size = array.length;
int parent = (size - 2) / 2;
for (int i = parent; i >= 0; i--){
shiftDown2(array, size, i);
}
}
//小堆向下调整
public static void shiftDown2(int[] array, int size, int index){
while (true){
int leftChild = index * 2 + 1;
if (leftChild >= size){
return;
}
int rightChild = leftChild + 1;
int minIndex = leftChild;
int minVal = array[minIndex];
if (rightChild < size && array[rightChild] < minVal){
minIndex = rightChild;
minVal = array[rightChild];
}
if (array[index] <= minVal){
return;
}
array[minIndex] = array[index];
array[index] = minVal;
index = minIndex;
}
}
同学们不要看见两大篇代码就烦哈，其实代码基本一样就是在个别地方有了调整，看懂一个第二个很容易就能明白。
最后我们来讨论刚才的问题：
为什么要有上面的两条规定呢？要升序排列就不能建小堆，要降序排列就不能建大堆吗？
答案是可以，但是不推荐，请看下图：
相反如果要通过建小堆完成让数组升序排列的话，因为小堆堆顶元素是最小值，而堆顶这个位置也是排序之后最小值的位置就是说堆顶元素不用在移动了，那么我们的堆要从后面一位重新建立，在建立一个小堆，找出最小值，在往后面一位找出最小值直到整个数组成升序排列，乍一看好像没有问题，但是和建大堆不同的是建小堆每次都要从下一位重新建堆才能选出最值，这个操作的复杂度为O(nlogn)，要比建大堆每次只用将堆顶元素向下调整的时间复杂度为O(logn)满很多，所以虽然可以升序建小堆但是因为相对没有建大堆速度快所以我们选择建大堆。
对应的降序建小堆也是同理。
希尔排序
希尔排序(Shell’s Sort)是插入排序的一种又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因 D.L.Shell 于 1959 年提出而得名。
插入排序将第一个数（也可以识别的）看为有序区间开展，从第二个数开始依次拿着每个数去到有序区间依次比较，最终插入到合适他的地方。
希尔排序做了升级，遵循下面这个循环：
- 按照一个规则将待排序序列分组（分组规则有很多，我们这里介绍一种：开始将序列分成序列长度除以二组，比如一共十个数，除以二等于五，就先分成5组，两个为一组，然后每次循环都会重新除以二分组，第二次就是 5 / 2向下取整为2组，第三次是一组）
- 然后对同一组做组内插入排序，我们做升序
- 组数除以二，现在就是2组，就是五个为一组
- 回到2循环
一直到所有数为同一组，再做最后一次排序。最后一次就是我们理解的对整个序列插入排序，这次排序结束序列也就有序了，下面看一下动图演示：
可以清楚地看到最后一次就是我们原来学的插入排序，那么有些人就有疑问了，为什么要大费周章的先从分组做插入排序开始？因为这样做会让每个数字更快的接近他排好序的位置，从而节省了时间，可以直白的理解为这么做就是更快了。。。
下面是代码实现：
public static void insertSort(int[] array, int size){
for (int i = size; i < array.length; i++){
int j;
int val = array[i];
for (j = i - size; j >= 0 && val < array[j]; j -= size){
array[j +size] = array[j];
}
array[j + size] = val;
}
}
public static void shellSort(int[] array){
int size = array.length / 2;
while (true){
insertSort(array, size);
if (size == 1){
break;
}
size /= 2;
}
}
快速排序
Hoare版
快速排序是一种相对比较快的排序，Hoare版快排的思想为：
选取待排序元素序列中的一个元素作为基准值，然后（以升序为例）比基准值小的元素放在基准值左边，比基准值大的元素放在基准值右边，这样的话，原先待排序序列就被分为了左子序列，右子序列，基准值，三个部分，，然后把左子序列看做新的待排序序列进行上述操作，左子序列又被分为新的左右子序列（递归的思想），当左子序列处理完之后再去处理右子序列，最后着呢个待排序序列就有序了。
下面是动图演示过程：
public static void quickSort(int[] array){
//把基准值选在待排序序列的最左边，第一次就是 0 的位置。
quickSortRange(array, 0, array.length - 1);
}
private static void quickSortRange(int[] array, int from, int to) {
int size = to - from + 1;
//递归结束条件
if (size <= 1)
return;
//先处理传入序列，返回值为一次单趟排序之后的基准值的位置，
//基准值左边为左子序列，基准值右边为右子序列
int index = partition(array, from, to);
//处理左子序列
partition(array, from, index - 1);
//处理右子序列
partition(array, index + 1, to);
}
/*这是一次单趟排序：
1、选出一个key，一般是最左边或是最右边的。
?2、定义一个L和一个R，L从左向右走，R从右向左走。
（需要注意的是：若选择最左边的数据作为key，则需要R先走；若选择最右边的数据作为key，则需要L先走）。
?3、在走的过程中，若R遇到小于key的数，则停下，L开始走，
直到L遇到一个大于key的数时，将L和R的内容交换，R再次开始走，如此进行下去，
直到L和R最终相遇，此时将相遇点的内容与key交换即可。（选取最左边的值作为key）
经过一次单趟排序，最终使得key左边的数据全部都小于key，key右边的数据全部都大于key。
*/
private static int partition(int[] array, int from, int to) {
int left = from;
int right = to;
int key = array[from];
while (left < right){
while (array[right] >= key && right > left)
right--;
while (array[left] <= key && right > left)
left++;
swap(array, left, right);
}
//走到这里说明 left == right了,
//让基准值到中间，方便后续处理左子序列
swap(array, from, left);
return left;
}
挖坑版
挖坑版partition单次过程：
- 选一个基准值，一般选最左或者最右面，把该基准值存在val变量中，因为值存到了变量里，所以可以视为这个位置能放其他值了。
- 定义一个left和一个right引用，left从序列左向右走，right相反（如果基准值在左边则right先走，如果基准值在右边，left先走）
- 走的过程中，如果right遇到小于val的数，则把个数放在坑中，并在次形成坑位，然后left向右走，如果遇到大于val的数，则将值填入坑中，此处形成一个坑位，循环下去，直到left和right相遇，这个时候把val的值放到坑中。
下面是单次partition动图演示（图是借的哈哈）
经过单次partition，让val左边的数据全部小于val，右边的数据全部大于val。
然后在去处理val左边子序列和val右边子序列，思路在Hoare版里面已经讲了，这里就不再重复了。
public static void quickSort(int[] array){
//把基准值选在待排序序列的最左边，第一次就是 0 的位置。
quickSortRange(array, 0, array.length - 1);
}
private static void quickSortRange(int[] array, int from, int to) {
int size = to - from + 1;
//递归结束条件
if (size <= 1)
return;
//先处理传入序列，返回值为一次单趟排序之后的基准值的位置，
//基准值左边为左子序列，基准值右边为右子序列
int index = partition(array, from, to);
//处理左子序列
quickSortRange(array, from, index - 1);
//处理右子序列
quickSortRange(array, index + 1, to);
}
public static int partition(int[] array, int from, int to) {
int left = from;
int right = to;
int val = array[left];
while (left < right) {
while (array[right] >= val && right > left)
right--;
array[left] = array[right];
while (array[left] <= val && right > left)
left++;
array[right] = array[left];
}
array[left] = val;
return left;
}
前后指针法
快速排序的前后指针法相比于Hoare版和挖坑版在思路上有点不同，前后指针版的思路是引入两个指针cur和prev，在开始的时候先规定一个基准值val（一般为最右边或者最左边的那个数据），然后让两个指针指向基准值的下一个数，开始下面循环：
若cur指向的内容小于key，则prev先向后移动一位，然后交换prev和cur指向的数，然后cur++；如果cur指向的内容大于val，则cur++。
直到cur走完整个序列，此时为了让基准值在中间，只需val和prev交换单次排序就完成了。下面是单次排序的动图：
在循环的过程中整个除了基准值的序列被prev和cur分成三个部分（拿升序举例）：
(from, prev) ：这是这个区间的数都是小于等于基准值的；
[s, i)：这个区间都是大于基准值的
[i, to]： 是还没有被比较过的
下面是代码：
public static void quickSort(int[] array){
//把基准值选在待排序序列的最左边，第一次就是 0 的位置。
quickSortRange(array, 0, array.length - 1);
}
private static void quickSortRange(int[] array, int from, int to) {
int size = to - from + 1;
//递归结束条件
if (size <= 1)
return;
//先处理传入序列，返回值为一次单趟排序之后的基准值的位置，
//基准值左边为左子序列，基准值右边为右子序列
int index = partition(array, from, to);
//处理左子序列
quickSortRange(array, from, index - 1);
//处理右子序列
quickSortRange(array, index + 1, to);
}
public static int partition(int[] array, int from, int to){
int val = array[from];
int s = from + 1;
for (int i = from + 1; i <= to; i++){
if (array[i] < val){
swap(array, i, s);
s++;
}
}
swap(array, from, s - 1);
return s - 1;
}
归并排序
归并排序是分治算法一个非常典型的例子，归并排序的思想是将待排序序列递归分为左右两个子序列，递归到子序列只有一个数的时候，停下来，这就是分治算法的分的意思，将问题化简，当子序列只有一个元素的时候是不是可以认为这个序列为有序序列了，然后再将左右有序子序列通过递归合并起来，最终让整个序列有序，这是分治算法治的过程，下面我们通过图片来理解这个过程：
通过动图理解就是：
下面看代码：
public class MergeSort {
public static void mergeSort(long[] array) {
mergeSortRange(array, 0, array.length);
}
// [from, to)
private static void mergeSortRange(long[] array, int from, int to) {
int size = to - from;
if (size <= 1) {
return;
}
//int mid = (from + to) / 2;
int mid = from + (to - from) / 2;
// 左半边: [from, mid)
// 右半边: [mid, to)
// 先让左右区间各自有序
mergeSortRange(array, from, mid);
mergeSortRange(array, mid, to);
// 合并两个有序区间 [from, mid) [mid, to)
merge(array, from, mid, to);
}
private static void merge(long[] array, int from, int mid, int to) {
// 需要额外空间，需要两个区间的大小之和
int size = to - from;
long[] array2 = new long[size];
int k1 = from; // array
int k2 = mid; // array
int k3 = 0; // array2
while (k1 < mid && k2 < to) {
if (array[k1] <= array[k2]) { // 加等号是为了保证稳定性
array2[k3++] = array[k1++];
} else {
array2[k3++] = array[k2++];
}
}
// 有一个区间内的元素全部取完了
if (k1 < mid) {
// 左边区间还有元素
while (k1 < mid) {
array2[k3++] = array[k1++];
}
} else {
// 右边区间还有元素
while (k2 < to) {
array2[k3++] = array[k2++];
}
}
// 我们还需要把数据搬回原数组中
for (int i = 0; i < size; i++) {
array[from + i] = array2[i];
}
}
}
归并排序的说简单也很简单，说难他不好理解的点就是将待排序序列一直分解到只含一个数据的子序列然后在依次合并这个递归操作上。
计数排序
前面七种基于比较的排序中最好的算法其时间复杂度都达到了O(nlogn)这个级别，要达到O(n)级别的时间复杂度，我们就要换一种思路，不能再用基于比较的排序算法。我们要用非基于比较的排序算法，虽然这种思想的算法在时间复杂度上得到了提升，但是这些算法的使用范围没有上面七种算法的适用范围广，而且空间复杂度也都普遍比上面七种高，可以说是空间换时间的一个策略吧。下面介绍非基于比较排序的计数排序。
计数排序用于待排序序列中数的范围小，但是总的量很大的情况，比如说某企业有员工上万名，请根据员工的年龄排序，上面描述的这个待排序序列就是量很大，但是作为一个员工年龄范围区间能有多大，18 - 60 也不过42个数，计数排序的核心思想是创建一个该范围大小的中间数组，该数组下标代表待排序数组中的数，下标内存该下标数一共在待排序区间中出现了多少次，例如：
然后在创建一个新的数组，依次将中间数组的值填进去：
下面是代码：
public static int[] countSort(int[] array){
//找出待排序数组最大最小值，
//找出最大最小值才能确定范围
int small = array[0];
int big = array[0];
for (int i = 1; i < array.length; i++){
if (array[i] > big)
big = array[i];
if (array[i] < small)
small = array[i];
}
int size = big - small + 1;
int[] midArray = new int[size];
int[] arrayReturn = new int[array.length];
for (int i = 0; i < array.length; i++)
midArray[array[i]]++;
for (int i = 0, j = 0; i < midArray.length; i++)
while (midArray[i]-- > 0)
arrayReturn[j++] = i;
return arrayReturn;
}
海量数据的排序问题
这里补充一个点，关于海量数据的排序问题。
外部排序：排序过程需要在磁盘外部存储进行的排序。
前提：内存只有1G，需要排序的数据有100G
因为内存中无法放下所有数据，所以需要外部排序，而并归排序是最常用的外部排序：
- 先把文件分成200份，每份512M
- 分别对每份文件排序，因为内存可以放得下512M，所以用合适的上述其中排序算法都可以
- 进行200路归并，同时对200份有序文件做归并过程，最终200G数据就都有序了。