九大排序法.doc

Forpersonaluseonlyinstudyandresearch;mercialuse膁一、插入排序肇羈特点:stablesort、In-placesort袂最优复杂度:当输入数组就是排好序的时候,复杂度为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)时间。莄膂递归版插入排序袀羀蚇薁二、冒泡排序薀螇特点:stablesort、In-placesort螅思想:通过两两交换,像水中的泡泡一样,小的先冒出来,大的后冒出来。芅最坏运行时间: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-placesort,unstablesort。螇思想:每次找一个最小值。螃最好情况时间: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]