第九章 排序 插入排序 交换排序 选择排序 归并排序 基数排序

排序问题 定义 给定一组纪录 R1,R2,········,Rn其关键码分别为k1,k2,········,kn,将这组纪录重新排成顺序为Rp1,Rp2,········,Rpn的一个序列，使其关键码具有不减顺序kp1 ≤ kp2 ≤ ········ ≤ kpn. 不同的纪录可以具有相同的关键码。 稳定的排序：关键码相同的纪录在排序前和排序后的次序保持不变。 约定：关键码用整数代替

排序的基本操作 比较 比较关键码的大小。 移动 将纪录从一个位置移到另一个位置。

排序方法的分类 内部排序 不用外设 外部排序 插入，交换，选择，归并，计数等排序法 复杂度 O(n2) O(nlogn) 等排序法 内部排序 不用外设 外部排序 插入，交换，选择，归并，计数等排序法 复杂度 O(n2) O(nlogn) 等排序法 静态排序， 动态排序

原始记录 #define MaxDataSize 100 template<class T> struct Data { T element; int key; Data<T>& operator=(const Data<T>& a); int operator<(const Data<T>& a,const Data<T>& b) {return a.key<b.key;} istream& operator<<(istream&, const Data<T>&); };

template <class T> class Array //array.h 通用数组 抽象数组类型 { T *alist; int size; public: Array(int s=50)； //构造函数 Array(const Array<T>&X); //拷贝构造函数 ~Array( ){delete[ ] element;} //析构函数 Array<T>&operator=(const Array<T>&X); T& operator[ ](int i)； operator T*( )const; int ArraySize( )const; //取数组长 void Resize(int sz); //数组长重定义 friend ostream& operator<<(ostream&, const Array<T>&); }；

待排序原始记录数组的输入 template<class T> void InputDataList(Array<T>&L,int n) for(int i=1;i<n;i++) { cout<<“Please enter L[”<<i<<“]:”; cin>>L[i];} Array<Data<T>> L; InputDataList(L,50);

一、插入排序 逐个将纪录插入到已排好次序的有序表中 得到一个新的有序表。

1.直接插入排序 49 38 65 97 76 13 27 49 49 38 49 65 49 65 97 38 49 65 76 97 13 38 49 65 76 97 27 38 49 65 76 97 13 27 38 49 49 65 76 97 最大时间复杂度 O(n2)=O(n2/2)+O(n2/2) n-1 比较 ∑i=n(n-1)/2 次 i=1 移动∑(i+2)=(n+4)(n-1)/2 最小时间复杂度 O(n) 不移动 元素个数n越小越好，源序列排序度越高越好

2.折半插入排序 用折半法比较查找到适当的位置再插入 减少比较次数 不减少移动次数 最坏时间复杂度 O(nlogn)+O(n2/2)=O(n2)

当第一个数据序列中间位置时 减少移动次数 不减少比较次数 3. 2路插入排序 49 38 65 97 76 13 27 49 49 49 38 49 65 38 49 65 97 38 49 65 76 97 38 49 65 76 97 13 38 49 65 76 97 13 27 38 49 49 65 76 97 13 27 38 复杂性 O(n2) Final First

4. 表插入排序 静态链表 不移动 0 1 2 3 4 5 6 7 8 Maxint 49 38 65 97 76 13 27 1 Maxint 49 38 65 97 76 13 27 2 1 Maxint 49 38 65 97 76 13 27 2 3 1 Maxint 49 38 65 97 76 13 27 2 3 1 4

Maxint 49 38 65 97 76 13 27 2 3 1 4 Maxint 49 38 65 97 76 13 27 2 3 1 5 4 Maxint 49 38 65 97 76 13 27 6 3 1 5 4 2 Maxint 49 38 65 97 76 13 27 6 3 1 5 4 7 2 Maxint 49 38 65 97 76 13 27 6 8 1 5 4 7 2 3

5. 链表插入排序 动态链表 不移动 13 27 38 49 49 65 76 97 ∧

6.希尔排序Shell Sort 缩小增量排序Diminishing Increment Sort 基本思想：先将待排纪录分成若干子列分别用直 接插入法排序，再对全体纪录用直接插入法排序。 理论根据：直接排序序列越短越好，源序列的排序度越好效率越高。

Shell Sort 取 dlta[k]=5，3，2，1 49 38 65 97 76 13 27 49 55 4 一趟排序结果： 13 27 49 55 4 49 38 65 97 76 二趟排序结果： 13 4 49 38 27 49 55 65 97 76 三趟排序结果： 4 13 27 38 49 49 55 65 76 97

//一趟Shell Sort 算法 直接插入 template<class T> void ShellInsert(Array<Data<T>>&L, int dk) { for(int i=dk+1;i<=L.length;++i) if(L[i]<L[i-dk]) { L[0]=L[i]; for(int j=i-dk;j>0&&L[0]<L[j];j-=dk) L[j+dk]=L[j]; L[j+dk]=L[0]; }

Shell Sort 算法 template<class T> void ShellSort(Array<Data<T>>&L, int *dlta, int t) { for(int k=0;k<t;k++) ShellInserrt(L,dlta[k]); } 取dlta[k]=2t-k+1-1 dlta[k]=······9，5，3，2，1 时间复杂度O(n3/2)

二. 交换排序 起泡排序Bubble Sort 49 38 65 97 76 13 27 49 一趟排序结果： 38 49 65 76 13 27 49 97 二趟排序结果： 38 49 65 13 27 49 76 97 三趟排序结果： 38 49 13 27 49 65 76 97 四趟排序结果： 38 13 27 49 49 65 76 97 五趟排序结果： 13 27 38 49 49 65 76 97 最快 正序 比较n-1次 不交换 最慢 逆序 n(n-1)/2次比较 同样多次交换

2.快速排序 基本思想：通过一趟排序将待排纪录分成上下两个子列，上子列大于下子列。再对两个子列继续排序。 理论依据：排序序列越短越好，源序列的排序度越好效率越高。

快速排序 49 38 65 97 76 13 27 49 一次交换后： 27 38 65 97 76 13 49 将pivot和high 比较下行找到 小于pivot的纪 录交换 快速排序 pivot 49 38 65 97 76 13 27 49 low high 一次交换后： 27 38 65 97 76 13 49 将pivot和low比较上行找到大于pivot的纪录交换 二次交换后： 27 38 97 76 13 65 49 high 三次交换后： 27 38 13 97 76 65 49 low 四次交换后： 27 38 13 49 76 97 65 49 Low和high相遇结束 low high

由pivot49分成两个子列，分别再进行快速排序 快速排序 27 38 13 49 76 97 65 49 第一轮后 由pivot49分成两个子列，分别再进行快速排序 27 38 13 49 76 97 65 49 一次 13 38 49 49 97 65 二次 13 38 49 49 65 97 三次 13 27 38 49 49 65 76 97 时间复杂性O(knlogn)

一趟快速排序算法的实现 时间复杂度cn template<class T> int Partition(Array<Data<T>>&L,const int low, const int high) { Data<T> pivot=L[low]; L[0]=L[low]; while(low<high) {while(low<high&&L[high]>=pivot) high--; L[low]=L[high]; while(low<high&&L[low]<=pivot) low++; L[high]=L[low]; } L[low]=L[0]; return low; }

快速排序算法的实现 template<class T> void QickSort(Array<Data<T>>&L, int low, int high) { if(low<high) { int pivotpos=Patition(L,low,high); QickSort(L,low,pivotpos-1); QickSort(L,pivotpos+1,high); }

快速排序算法复杂性分析 假设T(n)为对n个纪录进行快速排序所需时间， 对n个纪录进行一趟快速排序Patition(L,1,n)所需时间为cn, 则 T(n)=cn+T(k-1)+T(n-k) =cn+2T(n/2) //理想化每次都分成相等的两部分 =2cn+2(cn/2+2T(n/4))=3cn+4T(n/4) =4cn+8T(n/8)=········ =cnlog2n+nT(1)=O(nlog2n) 最坏 O(n2) 平均O(nlog2n)

比较排序算法的下界 n个元素排成一个序列，共有n!种不同的排法。 从一个序列出发排序，总共就会有n!种不同的变换次序。 每一次比较交换可以得到两种不同的次序，可以将不同的比较排成判定二叉树。

比较排序算法的下界log(n!) log((n/2)n/2)<log(n!)<log(nn) (n/2)log(n/2)<log(n!)<nlogn (n/2)log(n/2)=(n/2)(logn-1) =(n/2)logn-n/2=O(nlogn) log(n!)=O(nlogn)

三. 选择排序 1.简单选择排序 基本思想 一趟选择排序 选出最小纪录排在首位L[0] 第i+1趟选择排序 从纪录L[i+1]到L[n]选出 一趟比较n-i+1次共比较n(n-1)/2次 最少移动0次，最多移动3(n-1)次 时间复杂度O(n2)

2. 竞标赛排序 也叫树型排序 两两比较[n/2]次选出最小值 13 13 38 27 38 65 13 76 13 27 49 49 38 97 两两比较[n/2]次选出最小值

选次最小值 先将最小值由顶向下去掉，最底层换上Maxint 再比较log2n次。 重复这一过程n-1次得到全排序序列 27 27 38 76 27 38 65 76 27 49 49 38 65 97 先将最小值由顶向下去掉，最底层换上Maxint 再比较log2n次。 重复这一过程n-1次得到全排序序列 时间复杂性O(nlog2n) 空间开销大 可以改进

3.堆排序Heap Sort (改进了的树型排序） （极小）堆的定义： n个元素的完全二叉树，每个结点都小于其子结点。 13 27 49 76 97 65 38

用一维数组表示极小堆 0 1 2 3 4 5 6 7 13 49 27 97 65 38 76 A[i] ≤A[2i], A[i] ≤A[2i+1], 13 27 49 76 97 65 38

堆排序 堆排序的过程 1.将一个无序序列建成堆， 2. 入出顶点元素后，调整并重建堆， 3. 重复2.直至全部元素都输出完毕。

先作第二步：输出并调整重建堆 输出堆顶元素13，用堆末元素取代， 将元素76下移与子结点中较小的一个交换，向下过滤， 27 76 13 76 76 27 38 27 76 49 76 76 38 76 97 65 38 76 输出堆顶元素13，用堆末元素取代， 将元素76下移与子结点中较小的一个交换，向下过滤， 直至叶结点，重复第2步直至全部输出。

第一步 建堆 从最末一个非叶结点A[n/2]开始向下过滤 直至堆顶 49 13 27 13 65 49 38 65 49 27 49 97 第一步 建堆 从最末一个非叶结点A[n/2]开始向下过滤 直至堆顶 49 13 27 13 65 49 38 65 49 27 49 97 76 13 49 97

向下过滤的实现（极大堆） template<class T> void FilterDown(Array<Data<T>>&H,int s,int m) { Data<T> item=H[s]; for(int j=2*s;j<m;j*=2) { if(j+1<m&&H[j+1]>H[j])j++; if(item>H[j])break; H[s]=H[j]; s=j; } H[s]=item; }

堆排序的实现(由极大堆实现） template<class T> void HeapSort(Array<Data<T>&H) { for(int i=H.ArraySize( )/2;i>0;i--) FilterDown(H, i, H.ArraySize( )); for( i=H.ArraySize( );i>1;i--) {swap(H[1],H[i]); FilterDown(H,1,i-1); }

四. 归并排序 Merge Sort 将两个或两个以上有序表组合成一个新的有序表 叫做归并排序 复杂性O(m+n) 2路归并

2路归并算法 38 65 97 76 13 27 49 38 49 65 97 13 76 27 49 38 49 65 97 13 27 49 76 13 27 38 49 49 65 76 97 时间复杂性O(nlogn)

归并算法的实现 template<class T> void Merge(Array<Data T>> *L, Array<Data T>> *S, int i, int m, int n) { int j,k; for( j=m+1, k=i; i<m&&j<=n; k++) if(L[i]<L[j])S[k]=L[i++]; else S[k]=L[j++]; if(i<=m)for(;i<=m;k++)L[k]=L[i++]; if(j<=n)for(;j<=n;k++)L[k]=L[j++]; }

2路归并算法的实现 template<class T> void Msort(Array<Data <T>> *L, int i, int j) { Array<Data T>> * ST； ST=new Data<T>[L.ArraySize( )]； if(i == j)S[i]=L[i] else{ m=(i+ j)/2; Msort(L,ST,i,m); Msort(L,ST,m+1,j); Merge(ST,L,i,m,j); }

template<class T> void MergeSort(Array<Data <T>> *L) { Msort(L, L,1,L.ArraySize( )); }

2< 3 < ···< k< A< 五、基数排序---多关键字排序 例。扑克牌排序 2< 3 < ···< k< A< 2<  3< ···< K< A<  2<  3< ···<  K<  A<  2<  3 < ···<  k<  A <<< 两种排序法： 1。先排花色 2。先排面值 

例. 多位数排序 278 109 063 930 589 184 505 269 008 083 第一遍：按个位数放入10个箱子（队列） 例. 多位数排序 278 109 063 930 589 184 505 269 008 083 第一遍：按个位数放入10个箱子（队列） 按0-9的顺序从10个箱子中取出数字 930 063 083 184 505 278 008 109 589 269 0 1 2 3 4 5 6 7 8 9 269 0 1 2 3 4 5 6 7 8 9 008 0 1 2 3 4 5 6 7 8 9 083 0 1 2 3 4 5 6 7 8 9 505 0 1 2 3 4 5 6 7 8 9 589 0 1 2 3 4 5 6 7 8 9 278 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 109 0 1 2 3 4 5 6 7 8 9 063 0 1 2 3 4 5 6 7 8 9 930 0 1 2 3 4 5 6 7 8 9 184

例. 多位数排序 278 109 063 930 589 184 505 269 008 083 930 063 083 184 505 278 008 109 589 269 第二遍：再将所得数列按十位依次入箱 再按0-9的顺序从10个箱子中取出数字 505 008 109 930 063 269 278 083 184 589 0 1 2 3 4 5 6 7 8 9 109 0 1 2 3 4 5 6 7 8 9 589 0 1 2 3 4 5 6 7 8 9 269 0 1 2 3 4 5 6 7 8 9 008 0 1 2 3 4 5 6 7 8 9 184 0 1 2 3 4 5 6 7 8 9 930 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 063 0 1 2 3 4 5 6 7 8 9 083 0 1 2 3 4 5 6 7 8 9 505 0 1 2 3 4 5 6 7 8 9 278

例. 多位数排序 278 109 063 930 589 184 505 269 008 083 930 063 083 184 505 278 008 109 589 269 505 008 109 930 063 269 278 083 184 589 第三遍：再将所得数列按百位依次入箱 再按0-9的顺序从10个箱子中取出数字 008 063 083 109 184 269 278 505 589 930 0 1 2 3 4 5 6 7 8 9 083 0 1 2 3 4 5 6 7 8 9 589 0 1 2 3 4 5 6 7 8 9 278 0 1 2 3 4 5 6 7 8 9 184 0 1 2 3 4 5 6 7 8 9 930 0 1 2 3 4 5 6 7 8 9 505 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 008 0 1 2 3 4 5 6 7 8 9 109 0 1 2 3 4 5 6 7 8 9 063 0 1 2 3 4 5 6 7 8 9 269