老邱排序分册讲解

1、实验十 排序实验题 1. 分别用直接插入排序、折半插入排序、希尔排序、冒泡排序、快速排序和简单选择排序 算法对相同的待排序列进行排序，输出排序结果； 2. 统计排序过程中“比较”操作的执行次数和记录“移动”的次数。 【存储结构】 #defi ne MAXSIZE 20顺序表的最大长度 typedef struct int key;II关键字项 In foTypeotheri nfo;II 其他数据项 DataType; typedef struct DataType rMAXSIZE+1;r0闲置或用作哨兵单元 int len gth; SqList; 分别用直接插入排序、折半插入排序、希尔排

2、序、冒泡排序、快速排序和简单选择排序算 法对相同的待排序列进行排序，输出排序结果 II直接插入排序 #i nclude #in elude #i nclude #defi ne MAXSIZE 20 typedef int KeyType; typedef char In foType ; typedef struct KeyType key; In foType otherType ; RedType ; typedef struct RedType rMAXSIZE+1; int len gth; SqList; void In sertSort(SqList for(i=2;i=Len

3、gth ;+i) if(L.r i.key L.r i-1.key ) L.r 0=L.r i; L.r i=L.r i-1; for(j=i-2;L.r 0.key L.r j.key ;-j) L.r j+1=L.r j; L.r j+1=L.r 0; void In put(SqList cinL.len gth ; for(i nt i=1;i L.r i.key ; void Prin tList(SqList iL .len gth ;i+) coutL.r i+1.key ; coute ndl; void mai n() SqList L; L.le ngth =0; In p

4、ut(L); Prin tList(L); coutI nsertSo比e ndl; In sertSort(L); Prin tList(L); /* in put n: 13 23 11 67 98 43 76 90 56 13 23 11 67 98 43 76 90 56 In sertS o比 11 13 23 43 56 67 76 90 98 Press any key to con ti nue */ 分别用直接插入排序、折半插入排序、希尔排序、冒泡排序、快速排序和简单选择排序算 法对相同的待排序列进行排序，输出排序结果 折半插入排序 #i nclude #in clude #

5、i nclude #defi ne MAXSIZE 20 typedef int KeyType; typedef char In foType ; typedef struct KeyType key; In foType otherType ; RedType ; typedef struct RedType rMAXSIZE+1; int len gth; SqList; void In sertSort(SqList for(i=2;i=L .len gth ;+i) if(L.r i.key L.r i-1.key ) L.r O=L.r i; L.r i=L.r i-1; for(

6、j=i-2;L.r O.key L.r j.key ;-j) L.r j+1=L.r j; L.r j+1=L.r 0; void In put(SqList cinL.len gth ; for(i nt i=1;i L.r i.key ; void Prin tList(SqList iL .len gth ;i+) coutL.r i+1.key ; coute ndl; void Bin arySort(SqList int low,high,mid; for(i=2;i=L .len gth ;+i) L.r 0=L.r i; low=1; high=i-1; while(low=h

7、igh) mid=(low+high)/2; if(L.r 0.key =high+1;_-j) L.r j+1=L.r j; L.r high+1=L.r0; void mai n() SqList L; L.le ngth =0; In put(L); Prin tList(L); coutB in arySort:e ndl; Bin arySort(L); Prin tList(L); /* in put n: 9 13 23 11 67 98 43 76 90 56 13 23 11 67 98 43 76 90 56 Bin arySort: 11 13 23 43 56 67 7

8、6 90 98 Press any key to con ti nue */ 分别用直接插入排序、折半插入排序、希尔排序、冒泡排序、快速排序和简单选择排序算 法对相同的待排序列进行排序，输出排序结果 /希尔排序 #i nclude #in clude #i nclude #defi ne MAXSIZE 20 typedef int KeyType; typedef char In foType ; typedef struct KeyType key; In foType otherType ; RedType ; typedef struct RedType rMAXSIZE+1; int

9、 len gth; SqList; void In sertSort(SqList for(i=2;i=L .len gth ;+i) if(L.r i.key L.r i-1.key ) L.r 0=L.r i; L.r i=L.r i-1; for(j=i-2;L.r 0.key L.r j.key ;-j) L.r j+1=L.r j; L.r j+1=L.r 0; void ShellI nsert(SqList for(i=dk+1;i=L .len gth ;+i) if(L.r i.key 0j-=dk) L.r j+dk=L.r j; L.r j+dk=L.r 0; void

10、ShellSort(SqList kt;+k) Shelll nsert(L,dltak); void In put(SqList cinL.len gth ; for(i nt i=1;i L.r i.key ; void Prin tList(SqList iL .len gth;i+) coutL.r i+1.key coute ndl; void mai n() SqList L; L.le ngth =0; In put(L); Prin tList(L); int dlta3=5,3,1; int t=3; coutShellSort:e ndl; ShellSort(L,dlta

11、,t); Prin tList(L); /* in put n: 9 13 23 11 67 98 43 76 90 56 13 23 11 67 98 43 76 90 56 ShellSort: 11 13 23 43 56 67 76 90 98 Press any key to con ti nue */ 分别用直接插入排序、折半插入排序、希尔排序、冒泡排序、快速排序和简单选择排序算 法对相同的待排序列进行排序，输出排序结果 II冒泡排序 #i nclude #in elude #i nclude #defi ne MAXSIZE 20 typedef int KeyType; typ

12、edef char In foType ; typedef struct KeyType key; In foType otherType ; RedType ; typedef struct RedType rMAXSIZE+1; int len gth; SqList; void In sertSort(SqList for(i=2;i=L .len gth ;+i) if(L.r i.key L.r i-1.key ) L.r 0=L.r i; L.r i=L.r i-1; for(j=i-2;L.r 0.key L.r j.key ;-j) L.r j+1=L.r j; L.r j+1

13、=L.r 0; void Swap(SqList temp=L.r a.key ; L.r a.key =L.r b.key ; L.r b.key =temp; void BubbleSort(SqList int flag; for(i=1;i=i+1;j_) if(L.r j-1.key L.r j.key ) Swap(L,j-1,j); flag=0; if(flag) return ; void In put(SqList cinL.len gth ; for(i nt i=1;i L.r i.key ; void Prin tList(SqList iL .len gth;i+)

14、 coutL.r i+1.key ; coute ndl; void mai n() SqList L; L.le ngth =0; In put(L); Prin tList(L); coutBubbleSo rt: e ndl; BubbleSort(L); Prin tList(L); /* in put n: 9 13 23 11 67 98 43 76 90 56 13 23 11 67 98 43 76 90 56 BubbleSort: 11 13 23 43 56 67 76 90 98 Press any key to con ti nue */ 分别用直接插入排序、折半插入

15、排序、希尔排序、冒泡排序、快速排序和简单选择排序算 法对相同的待排序列进行排序，输出排序结果 快速排序 #i nclude #in clude #i nclude #defi ne MAXSIZE 20 typedef int KeyType; typedef char In foType ; typedef struct KeyType key; In foType otherType ; RedType ; typedef struct RedType rMAXSIZE+1; int len gth; SqList; void In sertSort(SqList for(i=2;i=Le

16、n gth ;+i) if(L.r i.key L.r i-1.key ) L.r 0=L.r i; L.r i=L.r i-1; for(j=i-2;L.r 0.key L.r j.key ;-j) L.r j+1=L.r j; L.r j+1=L.r 0; void In put(SqList cinL.len gth ; for(i nt i=1;i L.r i.key ; void Prin tList(SqList iL .len gth;i+) coutL.r i+1.key ; coute ndl; int Partitio n(SqList int pivokey=L.r lo

17、w.key ; while(lowhigh) while(low=pivokey) -high; L.r low=L.r high; while(lowhigh L.r high=L.r low; L.r low=L.r 0; return low; void Qsort(SqList if(lowhigh) pivoloc=Partitio n( L,low,high); Qsort(L,low,pivoloc); Qsort(L,pivoloc+1,high); void QuickSort(SqList void mai n() SqList L; L.le ngth =0; In pu

18、t(L); Prin tList(L); coutQuickSo rt: e ndl; QuickSort(L); Prin tList(L); /* in put n: 9 13 23 11 67 98 43 76 90 56 13 23 11 67 98 43 76 90 56 QuickS ort: 11 13 23 43 56 67 76 90 98 Press any key to con ti nue */ 分别用直接插入排序、折半插入排序、希尔排序、冒泡排序、快速排序和简单选择排序算 法对相同的待排序列进行排序，输出排序结果 II简单选择 #i nclude #in elude

19、#i nclude #defi ne MAXSIZE 20 typedef int KeyType; typedef char In foType ; typedef struct KeyType key; In foType otherType ; RedType ; typedef struct RedType rMAXSIZE+1; int len gth; SqList; void In sertSort(SqList for(i=2;i=L .len gth ;+i) if(L.r i.key L.r i-1.key ) L.r 0=L.r i; L.r i=L.r i-1; for

20、(j=i-2;L.r 0.key L.r j.key ;-j) L.r j+1=L.r j; L.r j+1=L.r 0; void In put(SqList cinL.len gth ; for(i nt i=1;i L.r i.key ; void Prin tList(SqList iL .len gth;i+) coutL.r i+1.key coute ndl; void Swap(SqList temp=L.r a.key ; L.r a.key =L.r b.key ; L.r b.key =temp; intSelectMi nKey(SqList int a=i; for(

21、i nt t=i;tL .len gth +1;t+) if(L.r t.key temp) temp=L.r t.key; a=t; return a; void SelectSort(SqList for(i=1;iL.le ngth ;+i) j=SelectMi nKey(L,i); if(i!=j) Swap(L,i,j); void mai n() SqList L; L.le ngth =0; In put(L); Prin tList(L); coutSelectS ort: e ndl; SelectSort(L); Prin tList(L); /* in put n: 9

22、 13 23 11 67 98 43 76 90 56 13 23 11 67 98 43 76 90 56 SelectSo rt: 11 13 23 43 56 67 76 90 98 Press any key to con ti nue */ 分别用直接插入排序、折半插入排序、希尔排序、冒泡排序、快速排序和简单选择排序算 法对相同的待排序列进行排序，输出排序结果 /希尔排序 #i nclude #in clude #i nclude #defi ne MAXSIZE 20 typedef int KeyType; typedef char In foType ; typedef str

23、uct KeyType key; In foType otherType ; RedType ; typedef struct RedType rMAXSIZE+1; int len gth; SqList; void In put(SqList cinL.len gth ; for(i nt i=1;i L.r i.key ; void Prin tList(SqList iL .len gth;i+) coutL.r i+1.key ; coute ndl; void In sertSort(SqList L) int i,j; for(i=2;i=L .len gth ;+i) if(L

24、.r i.key L.r i-1.key ) L.r 0=L.r i; L.r i=L.r i-1; for(j=i-2;L.r 0.key L.r j.key ;-j) L.r j+1=L.r j; L.r j+1=L.r 0; Prin tList(L); / void ShellI nsert(SqList for(i=dk+1;i=Len gth ;+i) if(L.r i.key 0j-=dk) L.r j+dk=L.r j; L.r j+dk=L.r 0; void ShellSort(SqList L,i nt dlta,i nt t) for(i nt k=0;kt;+k) S

25、hellI nsert(L,dltak); Prin tList(L); / void Bin arySort(SqList int low,high,mid; for(i=2;i=L .len gth ;+i) L.r 0=L.r i; low=1; high=i-1; while(low=high) mid=(low+high)/2; if(L.r 0.key =high+1;_-j) L.r j+1=L.r j; L.r high+1=L.rO; Prin tList(L); void Swap(SqList temp=L.r a.key ; L.r a.key =L.r b.key ;

26、 L.r b.key =temp; void BubbleSort(SqList int flag; for(i=1;i=i+1;j_) if(L.r j-1.key L.r j.key ) Swap(L,j-1,j); flag=0; if(flag) return ; void Bubble(SqList L) BubbleSort(L); Prin tList (L); / int Partitio n(SqList int pivokey=L.r low.key ; while(lowhigh) while(low=pivokey) -high; L.r low=L.r high; w

27、hile(lowhigh L.r high=L.r low; L.r low=L.r 0; return low; void Qsort(SqList if(lowhigh) pivoloc=Partitio n( L,low,high); Qsort(L,low,pivoloc); Qsort(L,pivoloc+1,high); void QuickSort(SqList L) Qsort(L,1,L.le ngth ); Prin tList(L); / int SelectMi nKey(SqList int a=i; for(i nt t=i;tLen gth +1;t+) if(L.r t.key temp) temp=L.r t.key; a=t; return a; void SelectSort(SqList L) int i,j; for(i=1;iL.le ngth ;+i) j=