这三种算法非常容易理解，因为我们生活当中经常在用。比如，班上的MM搞选美活动，有人叫我给所有MM排个名。我们通常会用选择排序，即先找出自己认为最漂亮的，然后找第二漂亮的，然后找第三漂亮的，不断找剩下的人中最满意的。打扑克牌时我们希望抓完牌后手上的牌是有序的，三个8挨在一起，后面紧接着两个9。这时，我们会使用插入排序，每次拿到一张牌后把它插入到手上的牌中适当的位置。什么时候我们会用冒泡排序呢？比如，体育课上从矮到高排队时，站队完毕后总会有人出来，比较挨着的两个人的身高，指挥到：你们俩调换一下，你们俩换一下。
这是很有启发性的。这告诉我们，什么时候用什么排序最好。当人们渴望先知道排在前面的是谁时，我们用选择排序；当我们不断拿到新的数并想保持已有的数始终有序时，我们用插入排序；当给出的数列已经比较有序，只需要小幅度的调整一下时，我们用冒泡排序。
最坏情况下三种算法各需要多少次比较和赋值操作
（the runing time of a sorting algoritm is proportional to the number of comparisons that the algorithm uses, to the number of times that items are moved or exchanged, or to both）
选择排序在第i次选择时赋值和比较都需要n-i次（在n-i+1个数中选一个出来作为当前最小值，其余n-i个数与当前最小值比较并不断更新当前最小值），然后需要一次赋值操作。总共需要n(n-1)/2次比较与n(n-1)/2+n次赋值(它的复杂度是“死”的，对于选择排序没有什么“好”的情况)。
插入排序在第i次寻找插入位置时需要最多i-1次比较（从后往前找到第一个比待插入的数小的数，最坏情况发生在这个数是所有已经取出的数中最小的一个的时候），在已有数列中给新的数腾出位置需要i-1次赋值操作来实现，还需要两次赋值借助临时变量把新取出的数搬进搬出。也就是说，最坏情况下比较需要n(n-1)/2次，赋值需要n(n-1)/2+2n次。
冒泡排序第i趟排序需要比较n-i次，n-1趟排序总共n(n-1)/2次。给出的序列逆序排列是最坏的情况，这时每一次比较都要进行交换操作。一次交换操作需要3次赋值实现，因此冒泡排序最坏情况下需要赋值3n(n-1)/2次。
按照渐进复杂度理论，忽略所有的常数，三种排序的最坏情况下复杂度都是一样的：O(n^2)。实践证明，插入排序是最快的（虽然最坏情况下与选择排序相当甚至更糟），因为每一次插入时寻找插入的位置多数情况只需要与已有数的一部分进行比较（你可能知道这还能二分）。你或许会说冒泡排序也可以在半路上完成，还没有跑到第n-1趟就已经有序。但冒泡排序的交换操作更费时，而插入排序中找到了插入的位置后移动操作只需要用赋值就能完成（你可能知道这还能用move）。
我们证明了，三种排序方法在最坏情况下时间复杂度都是O(n^2)。但大家想过吗，这只是最坏情况下的。在很多时候，复杂度没有这么大，因为插入和冒泡在数列已经比较有序的情况下需要的操作远远低于n^2次（最好情况下甚至是线性的）。抛开选择排序不说（因为它的复杂度是“死”的，对于选择排序没有什么“好”的情况），我们下面探讨插入排序和冒泡排序在特定数据和平均情况下的复杂度。
你会发现，如果把插入排序中的移动赋值操作看作是把当前取出的元素与前面取出的且比它大的数逐一交换，那插入排序和冒泡排序对数据的变动其实都是相邻元素的交换操作。下面我们说明，若只能对数列中相邻的数进行交换操作，如何计算使得n个数变得有序最少需要的交换次数。
我们定义逆序对的概念。假设我们要把数列从小到大排序，一个逆序对是指的在原数列中，左边的某个数比右边的大。也就是说，如果找到了某个i和j使得iAj，我们就说我们找到了一个逆序对。比如说，数列3,1,4,2中有三个逆序对，而一个已经有序的数列逆序对个数为0。我们发现，交换两个相邻的数最多消除一个逆序对，且冒泡排序（或插入排序）中的一次交换恰好能消除一个逆序对。那么显然，原数列中有多少个逆序对冒泡排序（或插入排序）就需要多少次交换操作，这个操作次数不可能再少。
若给出的n个数中有m个逆序对，插入排序的时间复杂度可以说是O(m+n)的，而冒泡排序不能这么说，因为冒泡排序有很多“无用”的比较（比较后没有交换），这些无用的比较超过了O(m+n)个。从这个意义上说，插入排序仍然更为优秀，因为冒泡排序的复杂度要受到它跑的趟数的制约。一个典型的例子是这样的数列：8, 2, 3, 4, 5, 6, 7, 1。在这样的输入数据下插入排序的优势非常明显，冒泡排序只能哭着喊上天不公。
然而，我们并不想计算排序算法对于某个特定数据的效率。我们真正关心的是，对于所有可能出现的数据，算法的平均复杂度是多少。不用激动了，平均复杂度并不会低于平方。下面证明，两种算法的平均复杂度仍然是O(n^2)的。
我们仅仅证明算法需要的交换次数平均为O(n^2)就足够了。前面已经说过，它们需要的交换次数与逆序对的个数相同。我们将证明，n个数的数列中逆序对个数平均O(n^2)个。
计算的方法是十分巧妙的。如果把给出的数列反过来（从后往前倒过来写），你会发现原来的逆序对现在变成顺序的了，而原来所有的非逆序对现在都成逆序了。正反两个数列的逆序对个数加起来正好就是数列所有数对的个数，它等于n(n-1)/2。于是，平均每个数列有n(n-1)/4个逆序对。忽略常数，逆序对平均个数O(n^2)。
Insertion sort is slow because the only exchange it does involve adjacent items, so items can move through the array only one place at a time.
Shell sort is a simple extension of insertion sort that gains speed by allowing exchanges of elements that are far apart;
希尔排序（Shell Sort）：又称增量排序，不断把待排序的对象根据增量d分成若干个小组，对同一小组内的对象采用直接插入法排序，当d=1时，完成了所有对象都分在一个组内的排序后，排序过程结束。每次比较指定间距为d的两个数据项，若左边的值小于右边的值，则交换它们的位置。
不同的增量将导致不同的效率，增量(1，4,13,40，121，...,3*h+1)是使用最广泛的增量序列之一,时间复杂度为O(n3/2)；增量1, 2, 3, 4, 6, 8, 9, 12, 16, ..., 2^p*3^q，既d=2x+3y,时间复杂度为O(n*(log n)^2);增量1,，8，37,7,281,1073,1493,16577，.....， ， 时间复杂度为O(N4/3)
Shell Sort的一个简单代码：
void ShellSort(int A[],int l,int u){
int h;
int x;
for(h=1;h<(u-1)/9;h=h*3+1);
for(;h>0;h/=3){
for(int i=l+h;i<=u;i++){
x=A[i];
int j=i;
for(;j>=l+h&&A[j-h]>x;j-=h)
A[j] = A[j-h];
A[j] = x;
}
}
}
|
