QuickSort(R,pivotpos+1,high); //对右区间递归排序 } }
//======直接选择排序======== void SelectSort(SeqList R) {
int i,j,k;
for(i=1;i for(j=i+1;j<=n;j++) //在当前无序区R[i‥n]中选key最小的记录R[k] if(R[j].key k=j; //k记下目前找到的最小关键字所在的位置 if(k!=i) { // //交换R[i]和R[k] R[0]=R[i]; R[i]=R[k]; R[k]=R[0]; } //endif } //endfor } //==========大根堆调整函数======= void Heapify( SeqList R,int low,int high) { // 将R[low..high]调整为大根堆，除R[low]外，其余结点均满足堆性质 int large; //large指向调整结点的左、右孩子结点中关键字较大者 RecType temp=R[low]; //暂存调整结点 for(large=2*low; large<=high;large*=2){ //R[low]是当前调整结点 //若large>high,则表示R[low]是叶子，调整结束；否则先令large指向R[low]的左孩子 if(large large++; //若R[low]的右孩子存在且关键字大于左兄弟，则令large指向它 //现在R[large]是调整结点R[low]的左右孩子结点中关键字较大者 if(temp.key>=R[large].key) //temp始终对应R[low] break; //当前调整结点不小于其孩子结点的关键字，结束调整 R[low]=R[large]; //相当于交换了R[low]和R[large] low=large; //令low指向新的调整结点，相当于temp已筛下到large的位置 } R[low]=temp; //将被调整结点放入最终位置上 } //==========构造大根堆========== void BuildHeap(SeqList R) { //将初始文件R[1..n]构造为堆 int i; for(i=n/2;i>0;i--) Heapify(R,i,n); //将R[i..n]调整为大根堆 } //==========堆排序=========== void HeapSort(SeqList R) { //对R[1..n]进行堆排序，不妨用R[0]做暂存单元 int i; BuildHeap(R); //将R[1..n]构造为初始大根堆 for(i=n;i>1;i--){ //对当前无序区R[1..i]进行堆排序，共做n-1趟。 R[0]=R[1]; R[1]=R[i];R[i]=R[0]; //将堆顶和堆中最后一个记录交换 Heapify(R,1,i-1); //将R[1..i-1]重新调整为堆，仅有R[1]可能违反堆性质。 } } //=====将两个有序的子序列R[low..m]和R[m+1..high]归并成有序的序列R[low..high]== void Merge(SeqList R,int low,int m,int high) { int i=low,j=m+1,p=0; //置初始值 RecType *R1; //R1为局部量 R1=(RecType *)malloc((high-low+1)*sizeof(RecType)); //申请空间 while(i<=m && j<=high) //两个子序列非空时取其小者输出到R1[p]上 R1[p++]=(R[i].key<=R[j].key)? R[i++]:R[j++]; while(i<=m) //若第一个子序列非空，则复制剩余记录到R1 R1[p++]=R[i++]; while(j<=high) //若第二个子序列非空，则复制剩余记录到R1中 R1[p++]=R[j++]; for(p=0,i=low;i<=high;p++,i++) R[i]=R1[p]; //归并完成后将结果复制回R[low..high] } //=========对R[1..n]做一趟归并排序======== void MergePass(SeqList R,int length) { int i; for(i=1;i+2*length-1<=n;i=i+2*length) Merge(R,i,i+length-1,i+2*length-1); //归并长度为length的两个相邻的子序列 if(i+length-1 //注意：若i≤n且i+length-1≥n时，则剩余一个子序列轮空，无须归并 } //========== 自底向上对R[1..n]做二路归并排序=============== void MergeSort(SeqList R) { int length; for(length=1;length MergePass(R,length); //有序长度≥n时终止 } //==========输入顺序表======== void input_int(SeqList R) { int i; printf(\ scanf(\ printf(\ for(i=1;i<=n;i++) scanf(\} //==========输出顺序表======== void output_int(SeqList R) { int i; for(i=1;i<=n;i++) printf(\} //==========主函数====== void main() { int i; SeqList R; input_int(R); printf(\ printf(\ printf(\ printf(\ printf(\ printf(\ printf(\ printf(\ printf(\ scanf(\输入整数1-7，选择排序方式 switch (i){ case 1: InsertSort(R); break; //值为1，直接插入排序 case 2: BubbleSort(R); break; //值为2，冒泡法排序 case 3: QuickSort(R,1,n); break; //值为3，快速排序 case 4: SelectSort(R); break; //值为4，直接选择排序 case 5: HeapSort(R); break; //值为5，堆排序 case 6: MergeSort(R); break; //值为6，归并排序 case 7: exit(0); //值为7，结束程序 } printf(\ output_int(R); } 实验结果： Please input num(int):10 Plase input 10 integer:265 301 751 129 937 863 742 694 76 438 ******** Select ********** 1: Insert Sort 2: Bubble Sort 3: Quick Sort 4: Straight Selection Sort 5: Heap Sort 6: Merge Sort 7: Exit *************************** 1 129, 265, 301, 751, 937, 863, 742, 694, 76, 438, 129, 265, 301, 751, 863, 937, 742, 694, 76, 438, 129, 265, 301, 742, 751, 863, 937, 694, 76, 438, 129, 265, 301, 694, 742, 751, 863, 937, 76, 438, 76, 129, 265, 301, 694, 742, 751, 863, 937, 438, 76, 129, 265, 301, 438, 694, 742, 751, 863, 937, Sort reult: 76, 129, 265, 301, 438, 694, 742, 751, 863, 937, 2 76,265,301,751,129,937,863,742,694,438, 76,129,265,301,751,438,937,863,742,694, 76,129,265,301,438,751,694,937,863,742, 76,129,265,301,438,694,751,742,937,863, 76,129,265,301,438,694,742,751,863,937, Sort reult: 76, 129, 265, 301, 438, 694, 742, 751, 863, 937, 3 76,129,265,751,937,863,742,694,301,438, 76,129,265,751,937,863,742,694,301,438, 76,129,265,438,301,694,742,751,863,937, 76,129,265,301,438,694,742,751,863,937, 76,129,265,301,438,694,742,751,863,937, 76,129,265,301,438,694,742,751,863,937, Sort reult: 76, 129, 265, 301, 438, 694, 742, 751, 863, 937, 4 76,301,751,129,937,863,742,694,265,438, 76,129,751,301,937,863,742,694,265,438, 76,129,265,301,937,863,742,694,751,438, 76,129,265,301,438,863,742,694,751,937, 76,129,265,301,438,694,742,863,751,937, 76,129,265,301,438,694,742,751,863,937, Sort reult: 76, 129, 265, 301, 438, 694, 742, 751, 863, 937, 5 863,694,751,265,438,301,742,129, 76,937, 751,694,742,265,438,301, 76,129,863,937, 742,694,301,265,438,129, 76,751,863,937, 694,438,301,265, 76,129,742,751,863,937, 438,265,301,129, 76,694,742,751,863,937, 301,265, 76,129,438,694,742,751,863,937, 265,129, 76,301,438,694,742,751,863,937, 129, 76,265,301,438,694,742,751,863,937, 76,129,265,301,438,694,742,751,863,937, Sort reult: 76, 129, 265, 301, 438, 694, 742, 751, 863, 937, 6 265,301,129,751,863,937,694,742, 76,438, 129,265,301,751,694,742,863,937, 76,438, 129,265,301,694,742,751,863,937, 76,438, 76,129,265,301,438,694,742,751,863,937, Sort reult: 76, 129, 265, 301, 438, 694, 742, 751, 863, 937, 7 Press any key to continue 运行速度比较： 直接排序 冒泡排序 直接插入 冒泡排序 快速排序 时间复杂度 O(n2)，其中快速排序效率较高 其它的效率差不多 堆排序 归并排序 时间复杂度 (nlogn) ,平均效率都很高 心得体会： 此次试验了解了各种排序的基本思想，在分析各种排序的程序代码，对程序进行调试执行等等过程中，锻炼了自己分析数据结构的能力。此次试验然我知道排序的多种方法，也让我知道要编写好一个程序，首先要掌握其基本的思想及算法。