九大排序法.docVIP

一、插入排序 特点：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]就是整个数组，因此证毕。而在算法导论2.3-6中还问是否能将伪代码第6-8行用二分法实现？实际上是不能的。因为第6-8行并不是单纯的线性查找，而是还要移出一个空位让A[i]插入，因此就算二分查找用O(lgn)查到了插入的位置，但是还是要用O(n)的时间移出一个空位。问：快速排序（不使用随机化）是否一定比插入排序快？答：不一定，当输入数组已经排好序时，插入排序需要O(n)时间，而快速排序需要O(n^2)时间。特点：stable sort、In-place sort证明算法正确性：运用两次循环不变式，先证明第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]，得证。 一般的人回答：“差不多吧，因为渐近时间都是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]中的元素是最大的，因此A[1...n]已排序，证毕。 算法导论2.2-2中问了为什么伪代码中第3行只有循环n-1次而不是n次？ 在循环不变式证明中也提到了，如果A[1...n-1]已排序，且包含了A中最小的n-1个元素，则A[n]肯定是最大的，因此肯定是已排序的。 特点：stable sort、Out-place sort思想：运用分治法思想解决排序问题。最坏情况运行时间：O(nlgn)最佳运行时间：O(nlgn)分治法介绍：分治法就是将原问题分解为多个独立的子问题，且这些子问题的形式和原问题