10.9、10.10、10.11选择排序

选择排序 Selection Sorting 选择排序的基本思想：每次从待排序记录中选出关键字最小的记录，顺序放在已排序的记录后面，直到全部排完为止。 （1）简单选择排序 Simple Selection Sort 不稳定的排序方法 时间复杂度：T(n)=O(n^2) 空间复杂度：S(n)=O(1) 程序如下：

#include<stdio.h> #include<iostream> using namespace std; typedef struct{ int key; }ElemType; #define MAXSIZE 20 typedef struct{ ElemType r[MAXSIZE+1]; int length; }SqList; SqList L; void SimpleSelectionSort(SqList &L) { int i,j,k; for(i=1;i<L.length;i++) { k=i; for(j=i+1;j<=L.length;j++) { if(L.r[j].key<=L.r[k].key) k=j; } if(i!=k) { L.r[0]=L.r[i]; L.r[i]=L.r[k]; L.r[k]=L.r[0]; } } } int main() { cout<<"请输入表长："<<endl; cin>>L.length; cout<<"请依次输入表中元素："<<endl; for(int i=1;i<=L.length;i++) cin>>L.r[i].key; cout<<"简单选择排序后的次序为："<<endl; SimpleSelectionSort(L); for(int j=1;j<=L.length;j++) cout<<L.r[j].key<<" "; }

（2）堆排序 Heap Sort 不稳定的排序方法 时间复杂度：T(n)=O(nlog(2(n))) 空间复杂度：S(n)=O(1) 下面以小顶堆为例：小顶堆的元素按照层次遍历的顺序存放在顺序表中，怎样利用小顶堆得到降序序列

void HeapSort(SqList &H) { for(int i=H.length;i>1;--i)//顺序表的序列已经是小顶堆 { H.r[0]=H.r[1]; H.r[1]=H.r[i]; H.r[i]=H.r[0]; HeapAdjust(H,1,i-1); } }

如果随意输入小顶堆的元素的话，又该如何得到降序序列呢

void HeapSort(SqList &H) { for(int k=H.length/2;k>0;--k) HeapAdjust(H,k,H.length); }

方法：H.length/2是无序序列对应完全二叉树的最后一个非叶子结点，从此结点开始到最后一个结点反复筛选 完整的程序代码：

#include<stdio.h> #include<iostream> using namespace std; typedef struct{ int key; }ElemType; ElemType rc; #define MAXSIZE 20 typedef struct{ ElemType r[MAXSIZE+1]; int length; }SqList; SqList H; void HeapAdjust(SqList &H,int s,int m) { rc=H.r[s]; for(int i=2*s;i<=m;i=i*2) { if(i<m && H.r[i].key>H.r[i+1].key) i++; if(rc.key<H.r[i].key) break; else { H.r[s]=H.r[i]; s=i; } } H.r[s]=rc; } void HeapSort(SqList &H) { for(int k=H.length/2;k>0;--k) HeapAdjust(H,k,H.length); for(int i=H.length;i>1;--i)//顺序表的序列已经是小顶堆 { H.r[0]=H.r[1]; H.r[1]=H.r[i]; H.r[i]=H.r[0]; HeapAdjust(H,1,i-1); } } int main() { cout<<"请输入顺序表的长度："<<endl; cin>>H.length; cout<<"请输入堆的元素："<<endl; for(int i=1;i<=H.length;i++) cin>>H.r[i].key; cout<<"堆元素的降序序列为："<<endl; HeapSort(H); for(int j=1;j<=H.length;j++) cout<<H.r[j].key<<" "; } //13 38 27 50 76 65 49 97 //按照层次遍历的顺序存放在顺序表中 //76 97 13 27 38 50 49 65 //随机存放在顺序表中

随机存放的运行结果为：