VC++2012编程演练数据结构常规排序算法
排序是计算机内经常进行的一种操作，其目的是将一组“无序”的记录序列调整为“有序”的记录序列。分内部排序和外部排序。若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序。反之，若参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成，则称此类排序问题为外部排序。内部排序的过程是一个逐步扩大记录的有序序列长度的过程。
内排序的方法有许多种，按所用策略不同，可归纳为五类：插入排序、选择
排序、交换排序、归并排序和分配排序。
其中，插入排序主要包括直接插入排序和希尔排序两种；选择排序主要包括直接选择排序和堆排序；交换排序主要包括气（冒）泡排序和快速排序。
◆稳定排序：假设在待排序的文件中，存在两个或两个以上的记录具有相同的关键字，在
用某种排序法排序后，若这些相同关键字的元素的相对次序仍然不变，则这种排序方法
是稳定的。其中冒泡，插入，基数，归并属于稳定排序，选择，快速，希尔，堆属于不稳定排序。
◆就地排序：若排序算法所需的辅助空间并不依赖于问题的规模n，即辅助空间为O（1）,
则称为就地排序。
假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，ri=rj，且ri在rj之前，而在排序后的序列中，ri仍在rj之前，则称这种排序算法是稳定的；否则称为不稳定的。
常见排序算法
快速排序、希尔排序、堆排序、直接选择排序不是稳定的排序算法，而基数排序、冒泡排序、直接插入排序、折半插入排序、归并排序是稳定的排序算法。
排序算法实现
[cpp]
#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[i].key,L->r[i-1].key)){
L->r[0]=L->r[i];
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[i];
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[i];
L->r[i]=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[s];
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[s]=H->r[j];
s=j;}
H->r[s]=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[i];
H->r[i]=t;
HeapAdjust(H,1,i-1);}
}
调用实现
[cpp]
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[i].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[i].key;
cout<<endl;
}
getch();
}
效果
五种排序算法
