数据结构（C语言版）程海英-上机8.docVIP

上机 排序 1.问题描述 2.数据结构设计 typedef struct { int key; char otherinfo; }RedType; typedf RedType Seqlist[L+l]; 3.函数说明 void HeapSort(int *array_sort,int *sorted_array,int length) //堆排序 4.编码实现 includecstdlib #include sort.h #include operate.h using namespace std; typedef struct { int key; char otherinfo; }RedType; typedf RedType Seqlist[L+l]; void ShellInsert(int r[],int n) { //希尔排序 int i,d,j,temp; for (d=n/2;d=l;d=d/2) { //以增量为d进行直接插人排序 for (i=d+1; in: i++) { temp= r[i]; //暂存被插入记录 for (j=i-d; j=0temp r [j];j=j-d) r[j+d]=r[j]; //记录后移d个位置 r[j+d]=temp; } } } void ShellSort(int *array_sort,int *sorted_ array, int length) { for (int i=0; i length; i++) sorted_array[i]=array_sort[i]; ShellInsert(sorted_array,length-1); } int Partition(int r[],int first,int end) { //快速排序一次划分 int i=first; //初始化 int j=end; int temp; while(ij) { while(ijr[i]=r[j]) //右侧扫描 j--; if (ij) { temp= r[i]; //将较小记录交换到前面 r[i]=r[j]; r[j]=temp; i++; } while(ijr[i]=r[j]) i++; //左侧扫描 if (ij){ temp=r[j]; //将较大记录交换到后面 r[j]=r[i]; r[i]= temp; j--; } } return i ; } void QSort(int r[],int first,int end) { //快速排序 if (firstend) { //递归结束 int pivot=Partition(r,first,end); //一次划分 QSort(r,first,pivot-1); //递归左侧子序列进行快速排序 QSort(r,pivot+l,end); //递归右侧子序列进行快速排序 } } void QuickSort(int *array_sort,int *sorted_array, int length) { for (int i=0; i length: i++) sorted_array[i]=array_sort[i]; QSort(sorted_array,0,length-1); } void Sift(int r[],int k, int m) { //筛选法调整堆 int i, j,temp; i=k; j=2*i+l; //置i为要筛的结点，j为i的左孩子 while(j=m) { //筛选还没有进行到叶子 if (jmr[j]r(j+1)) j++; //比较i的左右孩子，j为较大者 if (r[i]r[j]) break; //根结点已经大于左右孩子中的较大者 else { temp=r[i]; r[i]=r[j]; r[j]= temp; //将根结点与结点j交换 i=j; j=2* i+1; //被筛结点位于原来结点j的位置 } } } void Creatheap (int r[],int n) //堆排序建初堆 int i,temp;