几种常见的排序运用
排序算法是数据结构学科经典的内容，其中内部排序现有的算法有很多种，究竟各有什么特点呢？本文力图设计实现常用内部排序算法并进行比较。分别为起泡排序，直接插入排序，简单选择排序，快速排序，堆排序，针对关键字的比较次数和移动次数进行测试比较。
问题分析和总体设计
ADT OrderableList
{
数据对象：D={ai| ai∈IntegerSet,i=1,2,…,n,n≥0}
数据关系：R1={〈ai-1，ai〉|ai-1, ai∈D, i=1,2,…,n}
1、起泡排序
算法：核心思想是扫描数据清单，寻找出现乱序的两个相邻的项目。当找到这两个项目后，交换项目的位置然后继续扫描。重复上面的操作直到所有的项目都按顺序排好。
//冒泡排序函数
void bsort::bubblesort(double *y, int m)
{
for(i=(m-1);i>0;i--)
{
flag=0;
for(j=1;j<=i;j++)
{
if(y[j-1]>y[j])
{
temp=y[j-1];
y[j-1]=y[j];
y[j]=temp;
flag=1;
}
if(flag==0) break;
}
}
2、直接插入排序
算法：经过i-1遍处理后,L[1..i-1]己排好序。第i遍处理仅将L[i]插入L[1..i-1]的适当位置，使得L[1..i]又是排好序的序列。要达到这个目的，我们可以用顺序比较的方法。首先比较L[i]和L[i-1]，如果L[i-1]≤ L[i]，则L[1..i]已排好序，第i遍处理就结束了；否则交换L[i]与L[i-1]的位置，继续比较L[i-1]和L[i-2]，直到找到某一个位置j(1≤j≤i-1)，使得L[j] ≤L[j+1]时为止。
//插入排序函数
void isort::insertion_sort(double *x, int m)
{
for(i=1;i<m;i++)
{
temp=x[i];
j=i;
while((j>0)&&(x[j-1]>temp))
{
x[j]=x[j-1];
j--;
}
x[j]=temp;
}
3、简单选择排序
算法：首先找到数据清单中的最小的数据，然后将这个数据同第一个数据交换位置；接下来找第二小的数据，再将其同第二个数据交换位置，以此类推。
//shell排序函数
void ssort::shell_sort(double *x, int m)
{
h=3;
while(h>0)
{
for(i=1;i<m;i++)
{
temp=x[i];
j=i;
while((j>=h)&&(x[j-h]>temp))
{
cout<<"排序成功"<<endl;
x[j]=x[j-h];
j-=h;
}
x[j]=temp;
}
if((h/2)!=0) {h/=2;}
else if(h==1) {h=0;}
else{h=1;}
}
4、快速排序
算法：首先检查数据列表中的数据数，如果小于两个，则直接退出程序。如果有超过两个以上的数据，就选择一个分割点将数据分成两个部分，小于分割点的数据放在一组，其余的放在另一组，然后分别对两组数据排序。通常分割点的数据是随机选取的。这样无论你的数据是否已被排列过，你所分割成的两个字列表的大小是差不多的。而只要两个子列表的大小差不多。
//快速排序函数
void quicksort1::quicksort(double *x, int left, int right)
{
l_h=left;
r_h=right;
pivot=x[left];
while(left<right)
{
while((x[right]>=pivot)&&(left<right))
{
right--;
}
if(left!=right)
{
x[left]=x[right];
left++;
}
while((x[right]<=pivot)&&(left<right))
{
left++;
}
if(left!=right)
{
x[right]=x[left];
right--;
}
}
x[left]=pivot;
pivot_loc=left;
left=l_h;
right=r_h;
if(left<pivot_loc){quicksort(x, left, (pivot_loc-1));}
if(right>pivot_loc){quicksort(x,(pivot_loc+1),right);}
}