VC++2012编程演练数据结构《22》常规排序算法

大灰狼

排序是计算机内经常进行的一种操作，其目的是将一组“无序”的记录序列调整为“有序”的记录序列。分内部排序和外部排序。若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序。反之，若参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成，则称此类排序问题为外部排序。内部排序的过程是一个逐步扩大记录的有序序列长度的过程。
内排序的方法有许多种，按所用策略不同，可归纳为五类：插入排序、选择
　　  排序、交换排序、归并排序和分配排序。
　　其中，插入排序主要包括直接插入排序和希尔排序两种；选择排序主要包括直接选择排序和堆排序；交换排序主要包括气（冒）泡排序和快速排序。
◆稳定排序：假设在待排序的文件中，存在两个或两个以上的记录具有相同的关键字，在
　　用某种排序法排序后，若这些相同关键字的元素的相对次序仍然不变，则这种排序方法
　　是稳定的。其中冒泡，插入，基数，归并属于稳定排序，选择，快速，希尔，堆属于不稳定排序。
　　◆就地排序：若排序算法所需的辅助空间并不依赖于问题的规模n，即辅助空间为O（1）,
　　则称为就地排序。
　假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，ri=rj，且ri在rj之前，而在排序后的序列中，ri仍在rj之前，则称这种排序算法是稳定的；否则称为不稳定的。
常见排序算法

　　快速排序、希尔排序、堆排序、直接选择排序不是稳定的排序算法，而基数排序、冒泡排序、直接插入排序、折半插入排序、归并排序是稳定的排序算法。

打开IDE

排序算法实现

[cpp] view plaincopy

• #include<iostream>  
• #include<iomanip>  
• #include<conio.h>  
• #include<stdlib.h>  
• #include<time.h>  
• using namespace std;  
• #define MAXSIZE 20  
• #define LT(a,b) ((a)<(b))  
• typedef int KeyType;  
• typedef int InfoType;  
• typedef struct{  
•   KeyType key;  
•   InfoType otherinfo;  
• }RedType;  
• typedef struct{  
•   RedType r[MAXSIZE+1];  
•   int length;  
• }SqList;  
• //插入排序法  
• void InsertSort(SqList *L)  
• { int i,j;  
•   for(i=2;i<=L->length;++i)  
•     if(LT(L->r.key,L->r[i-1].key)){  
•       L->r[0]=L->r;  
•       for(j=i-1;LT(L->r[0].key,L->r[j].key);--j)  
•     L->r[j+1]=L->r[j];  
•       L->r[j+1]=L->r[0];}  
• }  
• //折半插入排序法  
• void BInsertSort(SqList *L)  
• { int i,j;  
•   int low,high,m;  
•   for(i=2;i<=L->length;++i){  
•     L->r[0]=L->r;  
•     low=1;high=i-1;  
•     while(low<=high){  
•       m=(low+high)/2;  
•       if (LT(L->r[0].key,L->r[m].key))  
•     high=m-1;  
•       else low=m+1;}  
•     for(j=i-1;j>=high+1;--j)  
•       L->r[j+1]=L->r[j];  
•     L->r[high+1]=L->r[0];}  
• }  
• //快速排序法  
• int Partition(SqList *L,int low,int high)  
• { int pivotkey;  
•   L->r[0]=L->r[low];  
•   pivotkey=L->r[low].key;  
•   while(low<high){  
•     while(low<high&&L->r[high].key>=pivotkey) --high;  
•     L->r[low]=L->r[high];  
•     while(low<high&&L->r[low].key<=pivotkey) ++low;  
•     L->r[high]=L->r[low];}  
•   L->r[low]=L->r[0];  
•   return low;  
• }  
• void QSort(SqList *L,int low,int high)  
• { int pivotloc;  
•   if(low<high){  
•     pivotloc=Partition(L,low,high);  
•     QSort(L,low,pivotloc-1);  
•     QSort(L,pivotloc+1,high);}  
• }  
• void QuickSort(SqList *L)  
• { QSort(L,1,L->length);}  
•   
• //选择排序法  
• int SelectMinKey(SqList L,int i)  
• {int k;int j;  
•   k=i;  
•   for(j=i;j<L.length+1;j++)  
•     if(L.r[k].key>L.r[j].key)  
•       k=j;  
•   return k;  
• }  
• void SelectSort(SqList *L)  
• { RedType t;  
•   int i,j;  
•   for(i=1;i<L->length;++i){  
•     j=SelectMinKey(*L,i);  
•     if(i!=j) {  
•       t=L->r;  
•       L->r=L->r[j];  
•       L->r[j]=t;}}  
• }  
• //堆排序法  
• typedef SqList HeapType;  
• void HeapAdjust(HeapType *H,int s,int m)  
• { RedType rc;  
•   int j;  
•   rc=H->r;  
•   for(j=2*s;j<=m;j*=2){  
•     if(j<m&<(H->r[j].key,H->r[j+1].key)) ++j;  
•     if(!LT(rc.key,H->r[j].key)) break;  
•     H->r=H->r[j];  
•     s=j;}  
•   H->r=rc;  
• }  
• void HeapSort(HeapType *H)  
• { RedType t;  
•   int i;  
•   for(i=H->length/2;i>0;--i)  
•     HeapAdjust(H,i,H->length);  
•   for(i=H->length;i>1;--i){  
•     t=H->r[1];  
•     H->r[1]=H->r;  
•     H->r=t;  
•     HeapAdjust(H,1,i-1);}  
• }  
  

调用实现

[cpp] view plaincopy

• void main()  
• { int a[11];  
•   int i,k,T=1;  
•   SqList s;  
•   cout<<"\运行结果:\n";  
•   srand(time(0));  
•   cout<<"排序前数组a:\n";  
•   for(i=1;i<11;i++)  
•     { s.r.key=a[i-1]=rand()%100;  
•       cout<<setw(4)<<a[i-1];}  
•   s.length=i-1;  
•   while(T){  
•    cout<<"    \n   请输入选择(1---6)：\n";  
•    cout<<"1:插入排序法   2:折半插入排序法\n";  
•    cout<<"3:快速排序法   4:选择排序法\n";  
•    cout<<"5:堆排序法     6:退出\n";  
•    cout<<"选择数k:";cin>>k;  
•    if(k<0||k>6) cout<<"输入选择错误，请重输!\n";  
•    switch(k){  
•     case 1:InsertSort(&s);break;  
•     case 2:BInsertSort(&s);break;  
•     case 3:QuickSort(&s);break;  
•     case 4:SelectSort(&s);break;  
•     case 5:HeapSort(&s);break;  
•     case 6:return;}  
•    cout<<"排序后数组a:\n";  
•    for(i=1;i<11;i++)  
•     cout<<setw(4)<<s.r.key;  
•    cout<<endl;  
•   }  
• getch();  
• }  
  

效果

五种排序算法