九大排序法.doc

一、插入排序
特点:stable sort、In-place sort
最优复杂度:当输入数组就是排好序的时候,复杂度为O(n),而快速排序在这种情况下会产生O(n^2)的复杂度。
最差复杂度:当输入数组为倒序时,复杂度为O(n^2)
插入排序比较适合用于“少量元素的数组”。
其实插入排序的复杂度和逆序对的个数一样,当数组倒序时,逆序对的个数为n(n-1)/2,因此插入排序复杂度为O(n^2)。
在算法导论2-4中有关于逆序对的介绍。
伪代码:
证明算法正确性:
循环不变式:在每次循环开始前,A[1...i-1]包含了原来的A[1...i-1]的元素,并且已排序。
初始:i=2,A[1...1]已排序,成立。
保持:在迭代开始前,A[1...i-1]已排序,而循环体的目的是将A[i]插入A[1...i-1]中,使得A[1...i]排序,因此在下一轮迭代开      始前,i++,因此现在A[1...i-1]排好序了,因此保持循环不变式。
终止:最后i=n+1,并且A[1...n]已排序,而A[1...n]就是整个数组,因此证毕。
-6中还问是否能将伪代码第6-8行用二分法实现?
实际上是不能的。因为第6-8行并不是单纯的线性查找,而是还要移出一个空位让A[i]插入,因此就算二分查找用O(lgn)查到了插入的位置,但是还是要用O(n)的时间移出一个空位。
问:快速排序(不使用随机化)是否一定比插入排序快?
答:不一定,当输入数组已经排好序时,插入排序需要O(n)时间,而快速排序需要O(n^2)时间。
递归版插入排序
二、冒泡排序
特点:stable sort、In-place sort
思想:通过两两交换,像水中的泡泡一样,小的先冒出来,大的后冒出来。
最坏运行时间:O(n^2)
最佳运行时间:O(n^2)(当然,也可以进行改进使得最佳运行时间为O(n))
算法导论思考题2-2中介绍了冒泡排序。
伪代码:
证明算法正确性:
运用两次循环不变式,先证明第4-6行的内循环,再证明外循环。
内循环不变式:在每次循环开始前,A[j]是A[j...n]中最小的元素。
初始:j=n,因此A[n]是A[n...n]的最小元素。
保持:当循环开始时,已知A[j]是A[j...n]的最小元素,将A[j]与A[j-1]比较,并将较小者放在j-1位置,因此能够说明A[j-1]是A[j-1...n]的最小元素,因此循环不变式保持。
终止:j=i,已知A[i]是A[i...n]中最小的元素,证毕。
接下来证明外循环不变式:在每次循环之前,A[1...i-1]包含了A中最小的i-1个元素,且已排序:A[1]<=A[2]<=...<=A[i-1]。
初始:i=1,因此A[1..0]=空,因此成立。
保持:当循环开始时,已知A[1...i-1]是A中最小的i-1个元素,且A[1]<=A[2]<=...<=A[i-1],根据内循环不变式,终止时A[i]是A[i...n]中最小的元素,因此A[1...i]包含了A中最小的i个元素,且A[1]<=A[2]<=...<=A[i-1]<=A[i]
终止:i=n+1,已知A[1...n]是A中最小的n个元素,且A[1]<=A[2]<=...<=A[n],得证。
在算法导论思考题2-2中又问了”冒泡排序和插入排序哪个更快“呢?
一般的人回答:“差不多吧,因为渐近时间都是O(n^2)”。
但是事实上不是这样的,插入排序的速度直接是逆序对的个数,而冒泡排序中执行“交换“的次数是逆序对的个数,因此冒泡排序执行的时间至少是逆序对的个数,因此插入排序的执行时间至少比冒泡排序快。
递归版冒泡排序
改进版冒泡排序
最佳运行时间:O(n)
最坏运行时间:O(n^2)
三、选择排序
特性:In-place sort,unstable sort。
思想:每次找一个最小值。
最好情况时间:O(n^2)。
最坏情况时间:O(n^2)。
伪代码:
证明算法正确性:
循环不变式:A[1...i-1]包含了A中最小的i-1个元素,且已排序。
初始:i=1,A[1...0]=空,因此成立。
保持:在某次迭代开始之前,保持循环不变式,即A[1...i-1]包含了A中最小的i-1个元素,且已排序,则进入循环体后,程序从        A[i...n]中找出最小值放在A[i]处,因此A[1...i]包含了A中最小的i个元素,且已排序,而i++,因此下一次循环之前,保持      循环不变式:A[1..i-1]包含了A中最小的i-1个元素,且已排序。
终止:i=n,已知A[1...n-1]包含了A中最小的i-1个元素,且已排序,因此A[n]中的