简单选择排序
简单选择排序不能再简单了,基本思想就是先外层循环n,作用是每循环一遍找出一个数最小的(分为无序区和有序区),在无序区中找到最小的那个数,再给到有序区。当然,找到无序区中最小的数那样也需要在无序区中在循环遍历一遍,这样时间复杂度就是o(n2),是稳定排序。
下面贴出教材的简单选择排序代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
void SelectSort(RecType R[],int n) { int i,j,k; RecType temp; for (i=0;i<n-1;i++) //做第i趟排序 { k=i; for (j=i+1;j<n;j++) //在当前无序区R[i..n-1]中选key最小的R[k] if (R[j].key<R[k].key) k=j; //k记下目前找到的最小关键字所在的位置 if (k!=i) //交换R[i]和R[k] { temp=R[i]; R[i]=R[k]; R[k]=temp; } printf(" i=%d: ",i); DispList(R,n); } } |
堆排序
下面贴出教材的堆排序代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 |
void sift(RecType R[],int low,int high) { int i=low,j=2*i; //R[j]是R[i]的左孩子 RecType temp=R[i]; while (j<=high) { if (j<high && R[j].key<R[j+1].key) //若右孩子较大,把j指向右孩子 j++; //变为2i+1 if (temp.key<R[j].key) { R[i]=R[j]; //将R[j]调整到双亲结点位置上 i=j; //修改i和j值,以便继续向下筛选 j=2*i; } else break; //筛选结束 } R[i]=temp; //被筛选结点的值放入最终位置 } void HeapSort(RecType R[],int n) { int i; RecType tmp; for (i=n/2;i>=1;i--) //循环建立初始堆,调用sift算法 n/2 次 sift(R,i,n); printf("初始堆:"); DispList1(R,n); for (i=n;i>=2;i--) //进行n-1趟完成推排序,每一趟堆排序的元素个数减1 { tmp=R[1]; //将最后一个元素与根R[1]交换 R[1]=R[i]; R[i]=tmp; printf("第%d趟: ",n-i+1); DispList1(R,n); sift(R,1,i-1); //对R[1..i-1]进行筛选,得到i-1个节点的堆 printf("筛选为:"); DispList1(R,n); } } int main() { int n=10; RecType R[MAXL]; KeyType a[]={15,18,29,12,35,32,27,23,10,20}; CreateList1(R,a,n); printf("排序前:"); DispList1(R,n); HeapSort(R,n); printf("排序后:"); DispList1(R,n); return 1; } |