我们来总结一下那些耳熟能详的排序算法并对其中几种算法使用Java进行实现

基于比较的排序算法

最常用的排序算法都是基于元素之间的两两比较来进行。这样的算法适用性强，它不关心元素的类型，元素的取值范围等，它只关心元素之间如何比较。而这之中，又有两类排序算法：简单排序算法和高效排序算法。

简单排序算法

1、插入排序

插入排序几乎是人们最自然去使用的一种排序算法，它尤其体现在扑克牌从牌堆摸牌的过程中。我们每次从牌堆摸一张牌到手上，就把牌插入相应的位置。

这样的排序怎么写呢？我们来列一个框架：

for (int i = 0; i < a.length; i++) { 
    // 循环不变式 
}

插入排序的性质：

2、选择排序

选择排序也是比较常用的方法。我们考虑桌上有一堆面相上的明牌，我们要排序的话，通常会先选择A，然后选择2,3…K，完成排序。选择排序就是这样，每次从数组中剩下的元素中选择最小的那个即可。

要完成这个选择，每一轮for里面，就要在a[i, i+1, …]一直到结束的这些数里面，挑出最小的那个数，并且将它和a[i]交换。

选择排序的性质：

3、冒泡排序

冒泡排序可能是因为其名称和独特的方法，所以很多同学一说排序就是冒泡排序。但其实它的性能并不优秀，理解上也不是太直接。 冒泡排序的外层循环其实跟选择排序一样：

for (int i = 0; i < a.length; i++) { 
    // a[0...i)为原数组中最小的i个元素排序完成的结果 
}

for (int i = 0; i < a.length; i++) { 
    for (int j = a.length - 1; j > i; j--) {
        if (a[j] < a[j - 1]) { 
            swap(a, j, j - 1); 
        } 
    } 
}

冒泡排序的性质：

• 时间复杂度：平均和最坏都是O(n2)。最好情况呢？我上述的实现当然也是O(n2)。不过对于已经排好序的数组，很容易优化到O(n)，这个就交给同学们了。因此我们说冒泡排序的最好情况是O(n)。
• 空间复杂度：O(1)。
• 稳定性：冒泡排序是稳定的。相邻的数最终会被换到相邻位置，我们只在a[j]<a[j-1]的情况下才进行交换就能保证其稳定性。
• 应用：冒泡排序对于已经排好序或者基本有序的数组（同学可以尝试简单优化我上述代码）的表现非常好，因此在数据量不大又基本有序的情况下可以使用。比如图形学中检测数据错误等。

4、高效排序算法

可以证明，基于比较的排序算法平均复杂度的上限是O(nlogn)。那么我们就来看看这些平均复杂度为O(nlogn)的算法。其中快速排序和归并排序更是“分治”思想方法的典型体现。

快速排序

快速排序是应用最为广泛的。大部分的基础库里面都会或多或少的使用快速排序。快速排序是一个递归的算法，我们可以这样来

实现

void sort(int[] a) { 
    // 分组：扫描a，把比a[0]小的数移到左边，把比a[0]大的数移到a[0]右边。 
    // 递归：对于左右两半边分别递归调用sort 
}

在实现上，我们主要的难度在于分组这一步。通常我们教科书上会见到有左右两个指针分别从0和n-1两端开始扫描，这是一种编码技巧，但并非理解快速排序的核心。我们也可以选择很朴素的扫描两边的方法来实现分组。

快速排序的性质：

• 平均时间复杂度：我们观察sort函数里面，分组需要花O(n)的时间，每次递归平均的来说，左右两半的大小都分别是n/2。那么快速排序的时间复杂度递推式就是：T(n)=2T(n/2)+O(n)。得出快速排序的平均复杂度是O(nlogn)。
• 最坏，最好时间复杂度：最坏情况有些讽刺的发生在已经排好序的数组上，以及完全倒序的数组上。这两种情况由于无法把问题的规模有效平分，导致上述时间递推式变成T(n)=T(0)+T(n-1)+O(n)，所以反而需要O(n2）的时间。那么我们思考，为啥一定要选择a[0]作为分界点呢？我们也叫做pivot item。的确我们可以选择任何一个元素作为pivot。但理论上，不论我们选择哪个元素作为pivot，都有可能很不幸的成为最坏情况。不过对于最好情况下的时间复杂度，我们容易理解它也是O(nlogn)。
• 空间复杂度：快速排序需要使用递归，递归会产生一个调用栈，这个栈的深度是logn，所以空间复杂度为O(logn)。当然，根据上述最坏情况时间复杂度的分析，最坏情况的空间复杂度也为O(n2)
• 稳定性：“正统”的快速排序，分组的过程会打乱元素的顺序，因此快速排序是不稳定的。但我们在分组的时候如果小心的保留元素的顺序，还是可以写出稳定的快速排序的。

5、归并排序

实现

void sort(int[] a) { 
    // 分组：把a分成左右两边，这次我们不管数据大小，直接中间切一刀，分组就完成了 
    // 递归：把左右两边分别递归调用归并排序，获得两个排好序的子数组 
    // 归并：把两个排好序的子数组进行归并 
}

归并排序有一个非常优秀的特点：把问题分成（若干个）互相独立的子问题，分别解决它们，并把子问题的解合成最终解。有了这个特点，我们就可以把归并排序的算法应用到并行计算，把超大的数据分给一个集群来处理。

归并排序的性质：

• 时间复杂度：这次，我们分组是立刻完成的，也就是O(1)。递归的问题规模是固定的n/2，归并这一步时间复杂度是O(n)。因此归并排序的时间复杂度递推式也是T(n)=2T(n/2)+O(n)，因此也是O(nlogn)。最好，最坏时间复杂度也都是O(nlogn)，因为我们分组是直接中间一刀切，不存在快速排序这种分偏掉的情况。
• 空间复杂度：归并这一步是需要额外空间的。是O(n)。
• 稳定性：归并排序是稳定的。归并的过程是保持稳定性的。

6、堆排序

堆排序使用了“堆”这样一个数据结构来进行排序。“堆”我们在各教科书和慕课网的其它课程中都有很好的介绍，我在这里就不详述了。堆排序类似选择排序，但是把所有剩下的数装在“堆”里面，效率更高。

它的实现是： 所有数据建堆 不断从堆中取出一个元素，重复n次。由于堆中取出的总是最小元素，因此排序完成。 堆排序的性质：

• 时间复杂度：建堆需要O(n)，取出一个元素需要O(logn)，重复n此也是O(nlogn)，两个加起来，是O(nlogn)。最坏最好情况也是O(nlogn)。
• 空间复杂度：堆是可以用数组实现的，我们可以把数组中的元素直接组成一个堆的结构。因此堆排序的空间复杂度是O(1)。
• 稳定性：堆排序是不稳定的。

非基于比较的排序算法

我们考虑一个问题，如果我告诉你我们所有的数据都是0-100的范围内的整数，但是数据的个数非常大，我们如何来排序呢？

我们这样来做

7、桶排序

我们的数据可能不是那么巧正好在0-100里面，那我们如何利用数据的值来进行排序呢？桶排序就是其中一种方法。 比如，我们分别建立几个“桶”：

我们扫描一遍数据，就把他们分别放在各自的“桶”里。那每个“桶”自己里面的那些数据如何排序呢？可以使用上面各种基于比较的排序方法，也可以继续细分为更小的“桶”来进行排序。

像归并排序一样，桶排序也非常适合用在并行计算上。我们把数据源根据“桶”分配给不同的工作机即可。

桶排序的性质：

8、基数排序的性质：

• 时间复杂度：每一次排序我们都使用上述的计数排序，由于计数数值的个数是固定的10个，所以每次排序的复杂度为O(n)，一共重复的位数我们记为d，那么就是O(dn)。
• 空间复杂度：计数排序需要O(n)的空间.
• 稳定性：基数排序可以保证其稳定性。

总结

我们在本文中总结了简单的排序算法，高效的排序算法以及非基于比较的排序算法。那么我们以一个表格来作总结吧