计算机软件基础-第七章 排序.ppt

 排序: 使一组任意排列的对象变成一组按关键字线性有序的对象。 关键字: 作为排序依据的数据对象。 内排序与外排序：排序过程是否全部在内存进行。 7.2.1 直接插入排序 总结： 27 38 38 13 65 97 49 76 76 13 97 65 27 49 49 49 e.g: 将序列 49、38、65、97、76、13、27、49 用 快速排序的方法进行排序。 0 1 2 3 4 5 6 7 界点 快速排序示例 high low temp 27 38 38 13 65 97 49 76 76 13 97 65 27 49 49 49 high low e.g: 将序列 49、38、65、97、76、13、27、49 用 快速排序的方法进行排序。 0 1 2 3 4 5 6 7 界点 快速排序示例 temp 27 38 38 13 65 97 49 76 76 13 97 65 27 49 49 49 e.g: 将序列 49、38、65、97、76、13、27、49 用 快速排序的方法进行排序。 0 1 2 3 4 5 6 7 界点 快速排序示例 high low temp 27 38 38 13 65 97 49 76 76 13 97 65 27 49 49 49 high low e.g: 将序列 49、38、65、97、76、13、27、49 用 快速排序的方法进行排序。 0 1 2 3 4 5 6 7 界点 快速排序示例 temp 91 88 42 23 24 16 05 13 （a）初始堆R[0]到R[7] 91 88 42 23 24 16 05 13 91 23 13 88 42 24 16 05 （b）第一趟排序之后 13 88 42 23 24 16 05 91 88 24 42 23 13 16 05 91 （c）重建的堆R[0]到R[6] 88 24 42 23 13 16 05 91 05 24 42 23 13 16 88 91 （d）第二趟排序之后 05 24 42 23 13 16 88 91 42 24 16 23 13 05 88 91 （e）重建的堆R[0]到R[5] 42 24 16 23 13 05 88 91 05 24 16 23 13 42 88 91 （f）第三趟排序之后 05 24 16 23 13 42 88 91 24 23 16 05 13 42 88 91 （g）重建的堆R[0]到R[4] 24 23 16 05 13 42 88 91 13 23 16 05 24 42 88 91 （h）第四趟排序之后 13 23 16 05 24 42 88 91 23 13 16 05 24 42 88 91 （i）重建的堆R[0]到R[3] 23 13 16 05 24 42 88 91 05 13 16 23 24 42 88 91 （j）第五趟排序之后 05 13 16 23 24 42 88 91 16 13 05 23 24 42 88 91 （k）重建的堆R[0]到R[2] 16 13 05 23 24 42 88 91 05 13 16 23 24 42 88 91 （l）第六趟排序之后 05 13 16 23 24 42 88 91 13 05 16 23 24 42 88 91 （m）重建的堆R[0]到R[2] 13 05 16 23 24 42 88 91 05 13 16 23 24 42 88 91 （n）第七趟排序之后 05 13 16 23 24 42 88 91 // 对a[0]到a[n-1]进行堆排序 void HeapSort(DataType a[],int n) { int i; DataType temp; for(i=(n-1)/2; i=0;i- -) CreatHeap(a,n,i); for(i=n-1; i0;i- -) { temp=a[0]; a[0]=a[i]; a[i]=temp; CreatHeap(a,i,0); } } 堆排序算法 //建初始堆 //进行n-1趟堆排序 //当前堆顶记录和最后一个记录交换 // a[0]到a[i-1]重建成堆 CreatHeap(DataType a[],int n,int h); 为在数组a[h]到