数据结构讲义设计第10章-排序.ppt

第10章 排序 10.1 概述 10.1 概述 10.1 概述 10.1 概述 10.1 概述 10.1 概述 10.1 概述 10.2 插入排序 10.2 插入排序 10.2 插入排序 10.2 插入排序 10.2 插入排序 10.2 插入排序 10.2 插入排序 10.2 插入排序 10.2 插入排序 10.2 插入排序 10.2 插入排序 10.2 插入排序 void shellSort(rectype r[],int n,int d[],int k) { for (l=0;lk;l++) { dk＝d[l]; for (i=dk+1;i=n;i++) { r[0]＝r[i]; for(j=i-dk;(j0R[j].keyr[0].key);j-=dk) r[j+dk]＝r[j]; R[j+dk]＝r[0]; } } } 10.2 插入排序 10.3 交换排序 10.3 交换排序 10.3 交换排序 10.3 交换排序 10.3 交换排序 10.3 交换排序 10.3 交换排序 10.3 交换排序 10.3 交换排序 int Partition(rectypeR[],int n, int low,int high) { pivotkey=R[low].key; while(lowhigh){ while( (lowhigh)(R[high].key=pivotkey)) --high; r[low]=r[high]; while( (lowhigh)(R[low].key=pivotkey)) ++low; r[high]=r[low]; } r[low]=pivotkey; return low; } 10.3 交换排序 void QSort(rectype R[],int n, int low,int high) { if (lowhigh) { pivotloc=Partition(R,n,low,high); QSort(R,low, pivotloc-1); QSort(R, pivotloc+1,high); } } void QuickSort(rectype R[],int n) { QSort(R,n,1,n); } 10.3 交换排序 10.4 选择排序 10.4 选择排序 10.4 选择排序 10.4 选择排序 void SelectSort(rectype R[] ,int n) { for (i=1;i=n-1;i++) { k=i; for (j=i+1;j=n;j++) if (R[j].keyR[k].key) k=j; if (k!=i) { temp=R[i]; R[i]=R[k]; R[k]=temp; } } } 10.4 选择排序 10.4 选择排序 10.4 选择排序 10.4 选择排序 10.4 选择排序 10.4 选择排序 10.4 选择排序 10.4 选择排序 10.4 选择排序 10.4 选择排序 现在剩下两个问题： （1）如何由一个无序序列建成一个堆； （2）如何在输出堆顶元素后，调整剩余元素为 一个新的堆。 10.4 选择排序 10.4 选择排序 10.4 选择排序 10.4 选择排序 10.4 选择排序 10.4 选择排序 void Sift(rectype R[], int s; int m){//筛选算法 temp=R[s]; for(j=2*s;j=m;j*=2){ if ((jm)(R[j].keyR[j+1].key)) j++; if (temp.key=R[j].key) break; R[s]=R[j]; s=j; } R[s]=temp; } 10.4 选择排序 //堆排序算法 void HeapSort(rectype R[],int n){ for (i=n/2;i=1;i--)//初始建堆 Sift(R,i,n); for (i=n;i1;i--){ temp=R[1]; R[1]=R[i]; R[i]=temp; Sift(R,1,i-1); } } 10.4 选择排