10.6、10.7、10.8交换排序

交换排序 Exchange Sorting 交换排序的基本思想： 两两比较待排序记录的关键值，交换不满足顺序要求的记录，知道全部满足顺序要求为止 （1）冒泡排序：每次比较相邻的两个记录 存储结构为：

typedef struct//数据元素类型 { int key;//关键字域 ......//其他域 }ElemType; #define MAXSIZE 20 typedef struct//表的顺序存储结构 { ElemType r[MAXSIZE+1];//r[0]为监视哨 int length;//表长 }SqList;

全部程序为：

#include<stdio.h> #include<iostream> using namespace std; typedef struct{ int key; }ElemType; #define MAXSIZE 20 typedef struct{ ElemType r[MAXSIZE+1]; int length; }SqList; SqList L; void BubbleSort(SqList &L,int length) { int flag=1; int m=length-1; while((m>0) && (flag==1)) { for(int i=1;i<=m;i++) { flag=0; if(L.r[i].key>L.r[i+1].key) { flag=1; L.r[0]=L.r[i]; L.r[i]=L.r[i+1]; L.r[i+1]=L.r[0]; }//if }//fori m--; }//while cout<<"冒泡排序后序列为："<<endl; for(int k=1;k<=length;k++) cout<<L.r[k].key<<" "; }//BubbleSort int main() { int length; cout<<"请输入元素个数："<<endl; cin>>length; cout<<"请依次输入元素："<<endl; for(int i=1;i<=length;i++) cin>>L.r[i].key; BubbleSort(L,length); }

（2）快速排序：每次比较不相邻的两个记录 存储结构与上面冒泡排序的存储结构相同 程序如下：

#include<stdio.h> #include<iostream> using namespace std; typedef struct{ int key; }ElemType; #define MAXSIZE 20 typedef struct{ ElemType r[MAXSIZE+1]; int length; }SqList; SqList L; int Partition(SqList &L,int low,int high) { L.r[0]=L.r[low]; int pivotkey=L.r[low].key; while(low<high) { while(low<high && L.r[high].key>=pivotkey) --high; L.r[low]=L.r[high]; while(low<high && L.r[low].key<=pivotkey) ++low; L.r[high]=L.r[low]; } L.r[low]=L.r[0]; return low; } void Sort(SqList &L,int low,int high) { int pivotloc; if(low<high) { pivotloc=Partition(L,low,high);//将L.r[low...high]一分为二 Sort(L,pivotloc+1,high);//对高子表递归排序 Sort(L,low,pivotloc-1); //对低子表递归排序 } } void QuickSort(SqList &L) { Sort(L,1,L.length); } int main() { cout<<"请输入元素个数："<<endl; cin>>L.length; cout<<"请依次输入元素："<<endl; for(int i=1;i<=L.length;i++) cin>>L.r[i].key; QuickSort(L); cout<<"快速排序后的序列为："<<endl; for(int j=1;j<=L.length;j++) cout<<L.r[j].key<<" "; }

对于Partition函数还有另外一种写法（道理是一个道理，都是利用检查哨）

int Partition(SqList &L,int low,int high) { int pivotkey; pivotkey=L.r[low].key; while(low<high) { while((low<high)&&(L.r[high].key>=pivotkey)) --high; L.r[0]=L.r[low]; L.r[low]=L.r[high]; L.r[high]=L.r[0]; while((low<high)&&(L.r[low].key<=pivotkey)) ++low; L.r[0]=L.r[high]; L.r[high]=L.r[low]; L.r[low]=L.r[0]; } return low; }

时间复杂度及空间复杂度 （1）冒泡排序 时间复杂度：T(n)=O(n^2) 最好情况：（正序） 比较次数 n-1 ；移动次数0 。 最坏情况：（逆序） 比较次数每次n-i 即1/2(n^2-n) ；移动次数为比较次数的3倍 即3/2(n^2-n) 。 空间复杂度：S(n)=O(1) 利用监视哨 （2）快速排序 时间复杂度：最好情况：T(n)=O(n^2log(2(n))) 最坏情况：T(n)=O(n^2) 主定理：设问题规模为n，利用分治法得到a个规模为n/b的问题，每次递归带来的额外计算为c*(n^d) 即T(n)=aT(n/b)+c(n^d) 若a=b^d， T(n)=O(n^dlog(2(n))) //以2为底 若a<b^d， T(n)=O(n^d) 若a>b^d， T(n)=O(n^log(b(a))) 快速排序中a=b=2,d=1 空间复杂度：最坏情况：S(n)=O(n) 一般情况：S(n)=O(log(2(n)))

稳定性: 冒泡排序是稳定的排序方法 快速排序是不稳定的排序方法 就平均时间而言，快速排序算法被认为是内部排序方法中最好的一种。快速排序不适合对小规模的序列进行排序。