《算法导论课件第5讲排序算法》由会员分享，可在线阅读，更多相关《算法导论课件第5讲排序算法（30页珍藏版）》请在金锄头文库上搜索。
1、1,第三章 排序算法,基于相邻元素的比较排序算法 1 插入排序法 2 冒泡排序法 3 选择排序法 基于分治法策略的排序算法 1 融合（归并）排序法 2 快速排序法,2,排序问题,排序就是把一个无序集合中的元素按照一定顺序排列成线性结构。 例：将电话簿或字典的条目按字母表的顺序排列起来以便更有利于查找。 内部排序（internal sort）：所有的数据都存储在计算机的高速随机存取存储器中，数据的读取时间可以忽略不计。 外部排序（external sort）：对低速外存设备中存放的数据进行排序。,3,插入排序,算法思想：把待排序的数组中的元素一个个取出来并插入到适当的位置上。 对于一个有n个元素
2、的无序数组E，假设数组的前面部分放的是已经是排好序的元素（开始的时候这一部分由第一个元素组成）。 设x 是数组未排序部分的第一个元素，我们分三步来插入x：,4,插入排序,把x 取出来，在x原来位置上留出一个空位； 把x与空位前面的元素作比较，如果x比这个元素小，就把这个元素向后移到空位中。在这个元素原来的位置上出现一个新的空位，等价于将空位向前移动了一个位置。继续下去直到x大于或等于空位前面的元素，或者空位前面已经没有元素了为止。 最后把x插入到空位中。,5,i=0 1 2 3 4 5 6 7 42 20 17 13 13 13 13 13 20 42 20 17 17 14 14 14 17
3、 17 42 20 20 17 17 15 13 13 13 42 28 20 20 17 28 28 28 28 42 28 23 20 14 14 14 14 14 42 28 23 23 23 23 23 23 23 42 28 15 15 15 15 15 15 15 42,实例,6,插入排序算法,输入：包含n (n 0) 个元素的数组E = E0, E1, En-1 输出：元素按单调不减顺序排列的数组E void insertionSort(Element E, int n) int xindex; for (xindex = 1; xindex n; xindex+) Elemen
4、t current = Exindex; key x = current.key int xLoc = shiftVacRec(E, xindex, x); /向前移动空位 ExLoc = current; return;,7,shiftVacRec子程序,int shiftVacRec(Element E, int vacant, Key x) int xLoc; if (vacant = 0) xLoc = vacant; else if (Evacant-1.key = x) xLoc = vacant; else Evacant = Evacant-1; xLoc = shiftVac
5、Rec(E, vacant-1, x); return xLoc,8,算法复杂度分析,首先考虑最差情况复杂度。令Ei表示数组中第i个元素，那么对于每个Ei，在最差情况下算法需要做的比较次数是i次，即将Ei与它前面的每个元素进行一次比较，所以在最差情况下算法所做的全部比较次数W(n)为,9,平均复杂度分析,假设输入数组中的每个元素在数组的每个位置上出现的概率都是一样大。x可能插入的位置有i+1个，而x属于其中任何一个位置的概率都是1/(i+1)，所以为了找到x的插入位置，shiftVac的平均比较次数是： 将数组中所有元素（1 i n-1）全部插入到已排序部分的正确位置上的平均比较次数为：,10
6、,最优算法的条件,定理：任何用比较的方法进行排序的算法，如果经过一次比较最多可以去掉数组中的一个反序，那么在最差情况下该算法所需要的比较次数为n(n1)/2，而在平均情况下的比较次数等于n(n1)/4。 证明：算法的最差情况即输入数组是按逆序排列的时候，此时数组中的反序（即顺序颠倒的数对）数目等于1+2+(n1) = n(n1)/2。因为每次比较最多只能去掉一个反序，所以至少需要进行n(n1)/2次比较。对于平均情况下的比较次数可类似证明。,11,冒泡排序,算法的思想：从数组后面开始把每一个元素与前面的元素进行比较，如果发现是反序的数对就进行交换。当一轮比较结束后，数组中最小的元素就被提升到了
7、最前面。整个过程犹如一个气泡从水底逐渐升到水面，故此得名。,12,Algorithm BubbleSort Void Bubsort(ELEM* aray, int n) for(int i=0; i n-1; i+) / Bubble ith record for(int j=n-1; j i; j-) if (key(arrayj)key(arrayj-1) swap(arrayj,arrayj-1); ,算法描述,13,i=0 1 2 3 4 5 6 7 42 13 13 13 13 13 13 13 20 42 14 14 14 14 14 14 17 20 42 15 15 15 1
8、5 15 13 17 20 42 17 17 17 17 28 14 17 20 42 20 20 20 14 28 15 17 20 42 23 23 23 15 28 23 23 23 42 28 15 23 23 28 28 28 28 42,实例一,14,k = n ; / k is the number of elements to be compared flag = 1 ; / flag 0 need more comparison while flag 0 k = k 1 flag = 0 for i = 1 to k do begin if L i L i+1 then be
9、gin swap(Li, Li+1) flag = 1 end end for,改进的冒泡排序算法二,15,i=0 1 2 3 4 5 6 7 42 20 17 13 13 13 13 13 20 17 13 17 14 14 14 14 17 13 20 14 17 15 15 15 13 28 14 20 15 17 17 17 28 14 23 15 20 20 20 20 14 23 15 23 23 23 23 23 23 15 28 28 28 28 28 28 15 42 42 42 42 42 42 42,实例二,16,算法思想： 首先从数组未排序部分找出最小元素，然后把这个元
10、素和已排序部分的下一个位置（即未排序部分的第一个位置）进行交换，并且将已排序部分向后扩展一位以包含这个元素。继续下去直到所有的元素都被包含到已排序部分为止。,选择排序,17,Void Selsort(ELEM* aray, int n) for(int i=0; ii; j-) /Find the least if (key(arrayj)key(arraylowindex) lowindex = j swap(arrayj,arraylowindex); ,算法描述,18,i=0 1 2 3 4 5 6 7 42 13 13 13 13 13 13 13 20 20 14 14 14 14
11、14 14 17 17 17 15 15 15 15 15 13 42 42 42 17 17 17 17 28 28 28 28 28 20 20 20 14 14 20 20 20 28 23 23 23 23 23 23 23 23 28 28 15 15 15 17 42 42 42 42,实例,19,比较次数: 插入 冒泡 选择 最佳情况 (n) (n) (n) 平均情况 (n) (n) (n) 最差情况 (n) (n) (n) 交换次数: 最佳情况 0 0 (n) 平均情况 (n) (n) (n) 最差情况 (n) (n) (n) 三种最简单的排序算法比较。它们的共同之处是在相邻元
12、素之间依次进行比较并在必要时交换位置来排序。,交换排序算法复杂度比较,20,基于分治策略的排序算法,分治法思想：将问题分解成一些同类型的子问题，然后递归地求出这些子问题，最后把子问题的解合并得到原问题的解。 Solve(I) n = size(I) if (n = smallsize) solution = directlySolve(I); else divide I into I1, , Ik. for each i in 1, , k Si = solve(Ii); solution = combine(S1, , Sk); return solution;,21,归并排序（Merges
13、ort）,算法思想,22,算法描述,输入：数组E，索引值first, last。数组中的元素用Ei表示（first i last）。 输出：排好序的数组Efirst, , Elast void mergeSort(Element E, int first, int last) if (first last) int mid = (first+last)/2; mergeSort(E, first, mid); mergeSort(E, mid+1, last); merge(E, first, mid, last); return;,23,子程序Merge,如何将排好序的两部分进行融合得到一个长度为两部分之和的有序数组？ 对于两个有序的队列，每次将两个队列的第一个元素进行比较，并将较小的一个拿走，然后再将剩下的队列和另一个队列的第一个元素进行比较。如此继续下去，直到其中一个队列的所有元素都拿完了，最后将另一个队列的元素依次拿出来放到原来拿出的元素后面。这样按拿出来的顺序将两个队列的元素排成一列就得到了融合之后的有序队列。,24,子程序Merge描述,Merge(A, B, C) if (A is empty) rest of C = rest of B el
