数据结构实验六 内部排序(2)

while(low=R[0].key) { cn[5]++;high--; } if(low

void Quick_Sort(datatype R[],long s, long t)//快速排序 { long i; if(s

void prin(datatype R[], long n) { long i; printf(\排序结果为 ：\\n\ for(i=1;i<=n;i++) {

printf(\ } printf(\}

void suiji() {

long i,n;

datatype R[MAXNUM]={0};////定义结构数组 printf(\请输入你要输入d个数\\n\ scanf(\ if(n>500000) { printf(\超出范围重新输入\\n\ scanf(\ }

for(i=1;i<=n;i++)

R[i].key=rand()00; printf(\排序前的元素顺序\\n\ for(i=1;i

int main() { suiji();

printf(\ 比较结果 \\n\ printf(\ 排序方式 比较次数 移动次数\\n\ printf(\ 直接 %d %d \\n\ printf(\ 简单选择 %d %d \\n\ printf(\ 冒泡 %d %d \\n\ printf(\ 推排序 %d %d \\n\ printf(\ 快速排序 %d %d \\n\ return 0; }

7、总结：

理论分析可以得出各种排序算法的时间复杂度和空间复杂度，如下

排序方法 直接插入排序 起泡排序 快速排序 简单选择排序 希尔排序 平均情况 O(n2) O(n2) O(nlog2n) O(n2) 最好情况 O(n) O (n) O(nlog2n) O(n2) O（n1..3） 最坏情况 O(n2) O(n2) O(n2) O(n2) 辅助空间 O(1) O(1) O(log2n) ~O(n) O(1) O（1）