分析10第十章排序

1、2017年8月第十章 排序SortingData structures10.1 排序的基本概念排序：將數(shù)據(jù)元素按關(guān)鍵字遞增或遞減的次序排列內(nèi)排序：待排序的數(shù)據(jù)全部在內(nèi)存中外排序：待排序的數(shù)據(jù)不全在內(nèi)存中排序的方法： 插入排序 交換排序 選擇排序 歸并排序 基數(shù)排序排序算法的性能指標： 時間復(fù)雜度 空間復(fù)雜度 算法的穩(wěn)定性排序前：12,45,123,67,45,89穩(wěn)定排序后：12,45, 45,67, 89, 123不穩(wěn)定排序后：12, 45,45, 67, 89, 123排序用的數(shù)據(jù)元素的類型定義 typedef int KeyType; / 關(guān)鍵字類型 typedef struct Key

2、Type key; / 關(guān)鍵字項 InfoType data; / 其他數(shù)據(jù)項 RecType; / 數(shù)據(jù)元素類型10.2 插入排序 基本思想每次將一個待排序的元素,按其關(guān)鍵字大小插入到前面已經(jīng)排好序的子表中的適當位置,直到全部元素都排好序為止。R0R1Ri-1RiRi+1Rn-1有序部分無序部分1、直接插入排序R0R1Ri-1RiRi+1Rn-1j=i-1/ 直接插入排序算法(非降序和升序)void InsertSort(RecType R , int n) int i, j; RecType temp; for (i=1; i=0 & temp.keyRj.key) Rj+1=Rj; /

3、將關(guān)鍵字大于Ri.key的記錄后移 j-; Rj+1=temp; / 在j+1處插入Ri Ri0) for (i=gap;i=0 & tmp.key0; i-) / 將第i大的元素冒泡至Ri, for ( j=0; jRj+1.key) temp=Rj; Rj=Rj+1; Rj+1=temp; / 改進的冒泡排序算法(非降序和升序)void BubbleSort(RecType R , int n) int i, j, exchanged; RecType temp; for (i=n-1; i0; i-) / 將第i大的元素冒泡至Ri, exchanged=0; for ( j=0; jRj

4、+1.key) temp=Rj; Rj=Rj+1; Rj+1=temp; exchanged=1; if( !exchanged ) return; 最好情況（原始數(shù)據(jù)順序有序）比較次數(shù)0交換次數(shù)時間復(fù)雜度復(fù)雜度O(n)最壞的情況（原始數(shù)據(jù)逆序有序）比較次數(shù)交換次數(shù)復(fù)雜度O(n2)n-1平均情況復(fù)雜度O(n2)空間復(fù)雜度 O(1)穩(wěn)定性穩(wěn)定2、快速排序基本思想a1:j-1ajajaj+1:naja1aian無序表劃分49386597761327485541338448274976975565例. 無序表以 49 作為劃分值，一趟劃分后的部分有序表對a1:j-1快速排序aj對aj+1:n 快速排

5、序?qū)ψ颖砜炫艅澐衷貏澐?部分排序)的原理4938659776132748554jkr=R0r=R0; j=1; k=n-1;while(j=k) while( j=k & Rj=r.key) j+; while( j=r.key) k-; if(jk) tmp=Rj; Rk=Rj; Rk=temp; j+; k-; R0=Rk; Rk=r; 掃描方向1338448274976975565劃分結(jié)果/ 快速排序算法(非降序和升序)void QuickSort(RecType R , int s, int t) int j, k;RecType r, temp; if (st) / 區(qū)間內(nèi)至少存在

6、2個元素的情況 r=Rs; j=s+1; k=t; / 用區(qū)間的第1個記錄作為劃分值 while(j=k) while( j=k & Rj=r.key) j+; / 找下一個大于劃分值的Rj while( j=r.key) k-; / 找下一個小于劃分值的Rk if(jk) / 交換Rj, Rk tmp=Rj; Rk=Rj; Rk=temp; j+; k-; Rs=Rk; Rk=r; / 通過交換Rs, Rk，將劃分元素存儲到Rk QuickSort(R, s, k-1); / 對左區(qū)間遞歸快排 QuickSort(R, k+1, t); / 對右區(qū)間遞歸快排 最好情況時間復(fù)雜度最壞情況平均情

7、況空間復(fù)雜度 O(log2n)穩(wěn)定性不穩(wěn)定O(nlog2n)O(n2)O(nlog2n)10.4 選擇排序1、直接選擇排序/ 直接選擇排序算法(非降序和升序)void SelectSort(RecType R , int n) int i, j; RecType temp; for (i=0; in-1; i+) for (j=i+1; jn; j+) if (Rj.keyRi.key) temp=Ri; Ri=Rj; Rj=temp; 每次從待排序的數(shù)據(jù)中選出關(guān)鍵字最小(最大)的元素，順序地放在已排序的子表的最后，直到完成全部排序。最好情況時間復(fù)雜度最壞情況平均情況空間復(fù)雜度 O(1)穩(wěn)定性

8、不穩(wěn)定O(n2)O(n2)O(n2)2、堆排序 n 個關(guān)鍵字 K1, K2, Kn 的順序表可看成是一棵完全二叉樹的順序存儲表， 最小堆：KiK2i, KiK2i+1; 最大堆：KiK2i, KiK2i+1;這樣的完全二叉樹的根節(jié)點稱為堆頂元素。顯然，堆頂元素為順序表的最大值或最小值。68790132459876513240無序表初始最大堆0876513249選擇排序后重構(gòu)堆并選擇6879013245無序表9876513240初始最大堆/ 節(jié)點往二叉樹根節(jié)點方向遷移一步的算法void Shift(RecType R , int low, int high) int i=low, j=2*i;

9、RecType temp=Ri; while (j=high) if(jhigh & Rj.keyRj+1.key) j+; if (tem.keys) / i 的初值為最后一個非終端節(jié)點 for ( i=s+(t-s+1)/2-1; i=1; i-) Shift(R, i, t);/ 最大堆排序算法(非降序和升序)void HeapSort(RecType R , int n) int i; RecType temp; CreateMaxHeap (R, 1, n); / 建立初始最大堆 for(i=n; i=2; i-) / 將堆頂元素交換到位置 i tmp=R1; R1=Ri; Ri=t

10、mp; Shift(R, 1, i-1); / 對R1:i-1重構(gòu)最大堆 時間復(fù)雜度最壞情況平均情況空間復(fù)雜度 O(1)穩(wěn)定性不穩(wěn)定O(nlog2n)O(nlog2n)10.5 歸并排序 將兩個相鄰的有序表子合并成單一有序表。二路歸并排序過程示例：初始18 2 20 34 12 32 6 16 1 52 18 20 34 12 32 6 16 1 5第1趟2 18 20 34 6 12 16 32 1 5第2趟2 6 12 16 18 20 32 34 1 5第3趟1 2 5 6 12 16 18 20 32 34 第4趟第一個問題：怎樣將相鄰的兩個有序表歸并成單個有序表？void Merge

11、 (RecType R , int low, int mid, int high) / 非降序 RecType bn; int l=low, h=mid+1, k=l; while (l=mid) & (h=high) / 部分合并 if (Rl.keymid) while (h=high) bk+=Rh+; / 轉(zhuǎn)儲剩余部分 else while(llow 時,分割：MergeSort(low, (low+high)/2)Rlow R(low+high)/2R(low+high)/2+1 RhighR low R highMergeSort( (low+high)/2+1, high)有序子

12、表有序子表Merge(low, (low+high)/2, high)有序表/ 歸并排序算法void MergeSort (low, high) int mid; if (lowhigh) mid=(low+high)/2; MergeSort(low, mid); MergeSort(mid+1, high); Merge(low, mid, high); 時間復(fù)雜度： O(nlog2n).空間復(fù)雜度： O(n).穩(wěn)定性：穩(wěn)定.10.6 基數(shù)排序每個關(guān)鍵字的值拆分成位，每位的取值個數(shù)稱為基數(shù) r，關(guān)鍵字的位數(shù)用 d 表示。如十進制 276，可拆分成三位 2, 7, 6, r=10, d=3.

13、對關(guān)鍵字的每一位（從低位到高位，反之亦然）： 將 n 個關(guān)鍵字按位的值“分配” 到 r 個隊列； 按位值的大小順序?qū)?r 個隊列中的元素進行“收集” ，構(gòu)成包含全部關(guān)鍵字的部分有序表；5200例：114, 179, 572, 835, 309, 141, 646, 520141157221144835564663091799按第一位（最低位）做第一趟分配第一趟收集結(jié)果: 520, 141, 572, 114, 835, 646, 179, 309309011415202835364614141795727第二趟收集結(jié)果: 309, 114, 520, 835, 141, 646, 572, 1

14、79按第二位做第二趟分配第一趟收集結(jié)果: 520, 141, 572, 114, 835, 646, 179, 30917914111413093572520564668358最后的收集結(jié)果: 114, 141, 179, 309, 520, 572, 646, 835第二趟收集結(jié)果: 309, 114, 520, 835, 141, 646, 572, 179按第三位做第三趟分配時間復(fù)雜度： O(d(n+r).空間復(fù)雜度： O(n).穩(wěn)定性：穩(wěn)定.設(shè)初始線性表和最終有序表均用隊列表示，則按平均時間將排序方法分為三類： （1）平方階O(n2)排序，一般稱為簡單排序，例如直接插入、直接選擇和冒泡排序； （2）線性對數(shù)階O(nlog2n)排序，如快速、堆和歸并排序； （3）線性階O(n)排序，如基數(shù)排序（假設(shè)r、d為常量）。 本章小結(jié)排序方法時間復(fù)雜度空間復(fù)雜度穩(wěn)定性平均情況最壞情況最好情況直接插入排序O(n2)O(n2)O(n)O(1)穩(wěn)定希爾排序O(n1.3)O(1) 不穩(wěn)定冒泡排序O(n2)O(n2)O(n)O(1) 穩(wěn)定快速排序O(nlog2n)O(n2)O(