剑指Offer——排序算法小结
前言
毕业季转眼即到，工作成为毕业季的头等大事，必须得认认真真进行知识储备，迎战笔试、电面、面试。
许久未接触排序算法了。平时偶尔接触到时自己会不假思索的百度，然后就是Ctrl+C、Ctrl+V，好点的话封装为一个排序工具供以后使用。这样的学习方法百害而无一益，只因自己缺少了思索，未能真正理解到算法的核心精髓所在。下面系统的对快速排序、堆排序、冒泡排序、插入排序、选择排序、归并排序、桶排序部分排序算法做一小结。望大家有所受益。
快速排序
介绍
快速排序采用的思想是分治思想。
快速排序是找出一个元素（理论上可以随便找一个）作为基准(pivot),然后对数组进行分区操作,使基准左边元素的值都不大于基准值,基准右边的元素值都不小于基准值，如此作为基准的元素调整到排序后的正确位置。递归快速排序，将其他n-1个元素也调整到排序后的正确位置。最后每个元素都是在排序后的正确位置，排序完成。所以快速排序算法的核心算法是分区操作，即如何调整基准的位置以及调整返回基准的最终位置以便分治递归。
举例
移步博文《Java进阶(三十八)快速排序》。
编码
移步博文《Java进阶(三十八)快速排序》。
时间复杂度
最差O(N2),平均NlogN。
空间复杂度
N+1
堆排序
构建最大堆
介绍
利用大顶堆(小顶堆)堆顶记录的是最大关键字(最小关键字)这一特性，使得每次从无序中选择最大记录(最小记录)变得简单。
操作过程如下：
1)初始化堆：将R[0..n-1]构造为堆；
2)将当前无序区的堆顶元素R[0]同该区间的最后一个记录交换，然后将新的无序区调整为新的堆。
因此对于堆排序，最重要的两个操作就是构造初始堆和调整堆，其实构造初始堆事实上也是调整堆的过程，只不过构造初始堆是对所有的非叶节点都进行调整。
注意使用最小堆排序后是递减数组，要得到递增数组，可以使用最大堆。
举例
public class HeapSortTest {
public static void main(String[] args) {
int[] data5 = new int[] { 5, 3, 6, 2, 1, 9, 4, 8, 7 };
print(data5);
heapSort(data5);
System.out.println("排序后的数组：");
print(data5);
}
public static void swap(int[] data, int i, int j) {
if (i == j) {
return;
}
data[i] = data[i] + data[j];
data[j] = data[i] - data[j];
data[i] = data[i] - data[j];
}
public static void heapSort(int[] data) {
for (int i = 0; i < data.length; i++) {
createMaxdHeap(data, data.length - 1 - i);
swap(data, 0, data.length - 1 - i);
print(data);
}
}
public static void createMaxdHeap(int[] data, int lastIndex) {
for (int i = (lastIndex - 1) / 2; i >= 0; i--) {
// 保存当前正在判断的节点
int k = i;
// 若当前节点的子节点存在
while (2 * k + 1 <= lastIndex) {
// biggerIndex总是记录较大节点的值,先赋值为当前判断节点的左子节点
int biggerIndex = 2 * k + 1;
if (biggerIndex < lastIndex) {
// 若右子节点存在，否则此时biggerIndex应该等于 lastIndex
if (data[biggerIndex] < data[biggerIndex + 1]) {
// 若右子节点值比左子节点值大，则biggerIndex记录的是右子节点的值
biggerIndex++;
}
}
if (data[k] < data[biggerIndex]) {
// 若当前节点值比子节点最大值小，则交换2者得值，交换后将biggerIndex值赋值给k
swap(data, k, biggerIndex);
k = biggerIndex;
} else {
break;
}
}
}
}
public static void print(int[] data) {
for (int i = 0; i < data.length; i++) {
System.out.print(data[i] + "\t");
}
System.out.println();
}
}
时间复杂度
O(nlogn)
空间复杂度
O(1)
稳定性
不稳定
所属类别
简单选择排序的增强版，同属选择排序。
冒泡排序
介绍
临近的数字两两进行比较,按照从小到大或者从大到小的顺序进行交换,这样一趟过去后,最大或最小的数字被交换到了最后一位,然后再从头开始进行两两比较交换,直到倒数第二位时结束。
例子为从小到大排序,原始待排序数组| 6 | 2 | 4 | 1 | 5 | 9 |
第一趟排序(外循环)
第一次两两比较6 > 2交换(内循环)
交换前状态| 6 | 2 | 4 | 1 | 5 | 9 |
交换后状态| 2 | 6 | 4 | 1 | 5 | 9 |
第二次两两比较,6 > 4交换
交换前状态| 2 | 6 | 4 | 1 | 5 | 9 |
交换后状态| 2 | 4 | 6 | 1 | 5 | 9 |
第三次两两比较,6 > 1交换
交换前状态| 2 | 4 | 6 | 1 | 5 | 9 |
交换后状态| 2 | 4 | 1 | 6 | 5 | 9 |
第四次两两比较,6 > 5交换
交换前状态| 2 | 4 | 1 | 6 | 5 | 9 |
交换后状态| 2 | 4 | 1 | 5 | 6 | 9 |
第五次两两比较,6 < 9不交换
交换前状态| 2 | 4 | 1 | 5 | 6 | 9 |
交换后状态| 2 | 4 | 1 | 5 | 6 | 9 |
第二趟排序(外循环)
第一次两两比较2 < 4不交换
交换前状态| 2 | 4 | 1 | 5 | 6 | 9 |
交换后状态| 2 | 4 | 1 | 5 | 6 | 9 |
第二次两两比较,4 > 1交换
交换前状态| 2 | 4 | 1 | 5 | 6 | 9 |
交换后状态| 2 | 1 | 4 | 5 | 6 | 9 |
第三次两两比较,4 < 5不交换
交换前状态| 2 | 1 | 4 | 5 | 6 | 9 |
交换后状态| 2 | 1 | 4 | 5 | 6 | 9 |
第四次两两比较,5 < 6不交换
交换前状态| 2 | 1 | 4 | 5 | 6 | 9 |
交换后状态| 2 | 1 | 4 | 5 | 6 | 9 |
第三趟排序(外循环)
第一次两两比较2 > 1交换
交换后状态| 2 | 1 | 4 | 5 | 6 | 9 |
交换后状态| 1 | 2 | 4 | 5 | 6 | 9 |
第二次两两比较,2 < 4不交换
交换后状态| 1 | 2 | 4 | 5 | 6 | 9 |
交换后状态| 1 | 2 | 4 | 5 | 6 | 9 |
第三次两两比较,4 < 5不交换
交换后状态| 1 | 2 | 4 | 5 | 6 | 9 |
交换后状态| 1 | 2 | 4 | 5 | 6 | 9 |
第四趟排序(外循环)无交换
第五趟排序(外循环)无交换
排序完毕,输出最终结果1 2 4 5 6 9
举例
package cn.edu.ujn.sort;
public class bubbleSort {
public static void main(String[] args) {
int[] a = { 6, 2, 4, 1, 5, 9 };
int n = a.length;
for(int i = 0; i < n; i++)
System.out.print(a[i] + " ");
bubble_sort(a,n);
System.out.println("");
for(int i = 0; i < n ;i++)
System.out.print(a[i] + " ");
}
static void bubble_sort(int[] unsorted, int n)
{
for (int i = 0; i < n; i++)
{
for (int j = i; j < n; j++)
{
if (unsorted[i] > unsorted[j])
{
int temp = unsorted[i];
unsorted[i] = unsorted[j];
unsorted[j] = temp;
}
}
}
}
}
结果如下:
时间复杂度
最坏情况O(N2),平均O(N2)。
空间复杂度
O(1)
插入排序
介绍
插入排序非常类似于整扑克牌。
在开始摸牌时，左手是空的，牌面朝下放在桌上。接着，一次从桌上摸起一张牌，并将它插入到左手一把牌中的正确位置上。为了找到这张牌的正确位置，要将它与手中已有的牌从右到左地进行比较。无论什么时候，左手中的牌都是排好序的。
如果输入数组已经是排好序的话，插入排序出现最佳情况，其运行时间是输入规模的一个线性函数。如果输入数组是逆序排列的，将出现最坏情况。平均情况与最坏情况一样，其时间代价是O(n2)。
也许你没有意识到，但其实你的思考过程是这样的：现在抓到一张7，把它和手里的牌从右到左依次比较，7比10小，应该再往左插，7比5大，好，就插这里。为什么比较了10和5就可以确定7的位置？为什么不用再比较左边的4和2呢？因为这里有一个重要的前提：手里的牌已经是排好序的。现在我插了7之后，手里的牌仍然是排好序的，下次再抓到的牌还可以用这个方法插入。编程对一个数组进行插入排序也是同样道理，但和插入扑克牌有一点不同，不可能在两个相邻的存储单元之间再插入一个单元，因此要将插入点之后的数据依次往后移动一个单元。
与选择排序不同的是，插入排序将数据向右滑动，并且不会执行交换。
稳定
最差情况：反序，需要移动n*(n-1)/2个元素
最好情况：正序，不需要移动元素
数组在已排序或者是“近似排序”时，插入排序效率的最好情况运行时间为O(n)；
插入排序最坏情况运行时间和平均情况运行时间都为O(n2)。
通常，插入排序呈现出二次排序算法中的最佳性能。
对于具有较少元素（如n<=15）的列表来说，二次算法十分有效。
在列表已被排序时，插入排序是线性算法O(n)。
在列表“近似排序”时，插入排序仍然是线性算法。
在列表的许多元素已位于正确的位置上时，就会出现“近似排序”的条件。
通过使用O(nlog2n)效率的算法（如快速排序）对数组进行部分排序，
然后再进行选择排序，某些高级的排序算法就是这样实现的。
举例
public static void InsertSort(int[] arr)
{
int i, j;
int n = arr.Length;
int target;
// 假定第一个元素被放到了正确的位置上
// 这样，仅需遍历1 - (n-1)
for (i = 1; i < n; i++)
{
j = i;
target = arr[i];
while (j > 0 && target < arr[j - 1])
{
arr[j] = arr[j - 1];
j--;
}
arr[j] = target;
}
}
时间复杂度
O(n2)
空间复杂度
O(1)
选择排序
介绍
选择排序的思想非常直接，不是要排序么？那好，我就从所有序列中先找到最小的，然后放到第一个位置。之后再看剩余元素中最小的，放到第二个位置……以此类推，就可以完成整个的排序工作了。可以很清楚的发现，选择排序是固定位置，找元素。相比于插入排序的固定元素找位置，是两种思维方式。不过条条大路通罗马，两者的目的是一样的。
举例
public static void selectSort(int[] arr)
{
int index, tmp, i, j, min;
int len = arr.length;
for(i = 0; i < len; i++){
index = i;
min = arr[i];
for(j = i + 1; j < len; j++){
if(min > arr[j]){
min = arr[j];
index = j;
}
}
tmp = arr[i];
arr[i] = min;
arr[index] = tmp;
}
}
时间复杂度
O(n2)
从选择排序的思想或者是上面的代码中，我们都不难看出，寻找最小的元素需要一个循环的过程，而排序又是需要一个循环的过程。因此显而易见，这个算法的时间复杂度也是O(n*n)的。这就意味值在n比较小的情况下，算法可以保证一定的速度，当n足够大时，算法的效率会降低。并且随着n的增大，算法的时间增长很快。因此使用时需要特别注意。
空间复杂度
O(1)
归并排序
介绍
归并排序是建立在归并操作上的一种有效排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
首先考虑下如何将二个有序数列合并。这个非常简单，只要从比较二个数列的第一个数，谁小就先取谁，取了后就在对应数列中删除这个数。然后再进行比较，如果有数列为空，那直接将另一个数列的数据依次取出即可。
归并排序和堆排序、快速排序的比较
若从空间复杂度来考虑：首选堆排序，其次是快速排序，最后是归并排序。
若从稳定性来考虑，应选取归并排序，因为堆排序和快速排序都是不稳定的。
若从平均情况下的排序速度考虑，应该选择快速排序。
举例
//将有二个有序数列a[first...mid]和a[mid...last]合并。
private static void mergearray(int a[], int first, int mid, int last, int temp[])
{
int i = first, j = mid + 1;
int m = mid, n = last;
int k = 0;
while (i <= m && j <= n)
{
if (a[i] <= a[j])
temp[k++] = a[i++];
else
temp[k++] = a[j++];
}
while (i <= m)
temp[k++] = a[i++];
while (j <= n)
temp[k++] = a[j++];
for (i = 0; i < k; i++)
a[first + i] = temp[i];
}
private static void mergesort(int a[], int first, int last, int temp[])
{
if (first < last)
{
int mid = (first + last) / 2;
mergesort(a, first, mid, temp); // 左边有序
mergesort(a, mid + 1, last, temp); // 右边有序
mergearray(a, first, mid, last, temp); // 再将二个有序数列合并
}
}
public static void mergeSort(int a[])
{
int len = a.length;
int[] p = new int[len];
mergesort(a, 0, len - 1, p);
}
时间复杂度
O(nlog2n)
归并排序的形式就是一棵二叉树，它需要遍历的次数就是二叉树的深度，而根据完全二叉树可以得出它的时间复杂度是O(nlog2n)。
空间复杂度
O(n)
算法处理过程中，需要一个大小为n的临时存储空间用以保存合并序列。
桶排序
介绍
1,桶排序是稳定的
2,桶排序是常见排序里最快的一种,比快排还要快…大多数情况下
3,桶排序非常快,但是同时也非常耗空间,基本上是最耗空间的一种排序算法
希尔排序
介绍
希尔排序的实质就是分组插入排序，该方法又称缩小增量排序，它是直接插入排序算法的一种威力加强版。因DL．Shell于1959年提出而得名。
该方法的基本思想是：把记录按步长 gap 分组，对每组记录采用直接插入排序方法进行排序。随着步长逐渐减小，所分成的组包含的记录越来越多，当步长的值减小到1时，整个数据合成为一组，构成一组有序记录，则完成排序。
举例
public static void shellSort(int a[])
{
int j, gap;
int n = a.length;
for (gap = n / 2; gap > 0; gap /= 2)
for (j = gap; j < n; j++) // 从数组第gap个元素开始
if (a[j] < a[j - gap]) // 每个元素与自己组内的数据进行直接插入排序
{
int temp = a[j];
int k = j - gap;
while (k >= 0 && a[k] > temp)
{
a[k + gap] = a[k];
k -= gap;
}
a[k + gap] = temp;
}
}
附 常用排序算法的时间复杂度、空间复杂度对比
附 内排序和外排序
内排序：指在排序期间数据对象全部存放在内存的排序。
外排序：指在排序期间全部对象太多，不能同时存放在内存中，必须根据排序过程的要求，不断在内，外存间移动的排序。
根据排序元素所在位置的不同,排序分: 内排序和外排序。
内排序：在排序过程中，所有元素调到内存中进行的排序，称为内排序。内排序是排序的基础。内排序效率用比较次数来衡量。按所用策略不同，内排序又可分为插入排序、选择排序、交换排序、归并排序及基数排序等几大类。
外排序：在数据量大的情况下，只能分块排序，但块与块间不能保证有序。外排序用读/写外存的次数来衡量其效率。
对于内排序来说，排序算法的性能主要是受3个方面影响：
1．时间性能
排序是数据处理中经常执行的一种操作，往往属于系统的核心部分，因此排序算法的时间开销是衡量其好坏的最重要的标志。在内排序中，主要进行两种操作：比较和移动。比较指关键字之间的比较，这是要做排序最起码的操作。移动指记录从一个位置移动到另一个位置，事实上，移动可以通过改为记录的存储方式来予以避免（这个我们在讲解具体的算法时再谈）。总之，高效率的内排序算法应该是具有尽可能少的关键字比较次数和尽可能少的记录移动次数。
2．辅助空间
评价排序算法的另一个主要标准是执行算法所需要的辅助存储空间。辅助存储空间是除了存放待排序所占用的存储空间之外，执行算法所需要的其他存储空间。
3．算法的复杂性
注意这里指的是算法本身的复杂度，而不是指算法的时间复杂度。显然算法过于复杂也会影响排序的性能。
根据排序过程中借助的主要操作，我们把内排序分为：插入排序、交换排序、选择排序和归并排序。可以说，这些都是比较成熟的排序技术，已经被广泛地应用于许许多多的程序语言或数据库当中，甚至它们都已经封装了关于排序算法的实现代码。因此，我们学习这些排序算法的目的更多并不是为了去在现实中编程排序算法，而是通过学习来提高我们编写算法的能力，以便于去解决更多复杂和灵活的应用性问题。
参考资料
[经典排序算法][集锦]
1.http://www.cnblogs.com/kkun/archive/2011/11/23/2260312.html
常用的排序算法的时间复杂度和空间复杂度
2.http://blog.csdn.net/wuxinyicomeon/article/details/5996675
堆排序
3.http://www.cnblogs.com/dolphin0520/archive/2011/10/06/2199741.html
排序算法对比(动画延时，有创新)
4.http://www.cs.usfca.edu/~galles/visualization/Algorithms.html