关于排序的认识
排序总的可以分为插入排序，交换排序，选择排序，归并排序，基数排序等。
其中插入排序又可以细分为直接插入排序，折半排序，希尔排序。
直接排序的基本思想是：当插入第i （i>=1）个对象时，前面的v[0]，v[1]，…….v[i-1]已经排好序，这时，用v[i]的关键码与v[i-1],v[i-2]……的关键码顺序进行比较，找到插入位置即将v[i]插入，原来位置上的对象向后顺移。直接插入排序的时间复杂度为n2,直接插入排序是一种稳定的排序方法。
折半排序的基本思想是：设在顺序表中有一个对象序列v[0]，v[1]，….v[n-1]，其中，v[0]，v[1]，….v[i-1]是已经排好序的对象。在插入v[i]时，利用折半查找法寻找v[i]的插入位置。折半插入是一种稳定的排序方法。
希尔排序：当待排序的数列很长时，（即n很大时），关键码平均比较次数和对象平均移动次数大约在n1.25（即n的1.25次方，以下同样）到1.6n1.25范围内。
交换排序又可细分为冒泡排序，快速排序。
冒泡排序的基本思想是：设待排序的数列的大小为n，首先比较v[n-2]和v[n-1]的大小，如果v[n-2]>v[n-1],则交换v[n-2]和v[n-1]，然后对v[n-2]和v[n-3]作相同的处理，如此处理， 直到处理完v[0]和v[1],这个称为一趟冒泡，所以只要经过n-1 趟冒泡就可以排好所有对象。 在最坏情况下总的关键码比较次数为0.5n(n-1),对象移动次数为1.5n（n-1）
快速排序的基本思想是：取待排序的数列的某个对象（例如第一个对象）作为基准，将对象分为左右两个数列，左边的全都小于基准，右边的全都大于基准，然后对左右两个树列重复以上操作，直到全部完成。它是一种不稳定的方法，对于待排序的数列很大时，快速排序的确很快，但当待排序的数列很小时，它往往比其它简单的排序方法还要慢。
选择排序又可以细分为直接选择排序，堆排序。
直接选择排序的最坏情况是每一趟都要进行交换，总的对象移动次数是3(n-1)。
堆排序可以分为两个步骤：首先，根据初始输入数据，利用堆的调整算法FilterDown()形成初始堆， 第二步通过一系列的对象交换和重新调整堆进行排序。堆排序的是一个不稳定的排序方法，并且当待排序的数列很大时，堆排序不可取。
归并排序就是将两个或两个以上的有序表合并成一个新的有序表。
基数排序的基本思想是：待排序的对象按m个关键码key[0],…..key[m-1]排序，每个对象的关键码域用一个数组key[m]表示，对各关键码的排序采用箱排序。
从上面可以得出结论（本人观点），当待排序的数列很小时，可以采取直接插入排序，折半排序，希尔排序，直接选择排序，堆排序，归并排序，基数排序等众多排序方法，但当待排序的数列很大时，采用快速排序为优。
就平均性能而言，我认为快速排序最好。
冒泡排序：
void CSortDlg::bubble_sort(int x[]){
//对数组x[]逐趟进行比较 ，遇到逆序即交换
int i =1;int exchange=1;//当exchange为0时，则停止排序
while((i<10 )&&exchange){//
BubbleExchange( x, i, exchange);
i++;
}
}
void CSortDlg::BubbleExchange(int x[],int i,int exchange){
exchange = 0;//假定元素未交换
for(int j =9;j>=i;j--){
if(x[j-1]>x[j])//发生了逆序
{
int temp = x[j-1];//交换
x[j-1]=x[j];
x[j] = temp;
exchange = 1;//做“发生了交换”的标志
}
}
}
直接插入排序：
void CSortDlg::InsertionSort(int x[])
{
for(int i=1;i<10;i++)
{
Insert(x,i);
}
}
void CSortDlg::Insert(int x[],int i)
{
int temp=x[i]; int j=i;
while (j>0&&temp<x[j-1])
{
x[j]=x[j-1];
j--;
}
x[j]=temp;
}
希尔排序：
void CSortDlg::Shellsort(int x[])
{
int gap=10/2;//增量的初始值
while (gap)//循环条件是gap>=1
{
ShellInsert(x,gap);//按增量gap划分子序列，分别进行插入排序
gap=gap==2?1:(int)(gap/2);//缩小增量gap
}
}
void CSortDlg::ShellInsert(int x[],const int gap)
{
for(int i=gap;i<10;i++)//各子序列轮流执行插入排序
{
int temp=x[i];int j=i;//暂存待插入对象
while (j>=gap&&temp<x[j-gap]) {//当前插入元素比位于j-gap的元素小，则位于j-gap的元
//素后移
x[j]=x[j-gap];
j-=gap;//后移到第j个位置，j指标前指
}
x[j]=temp;//插入
}
}
归并排序：
void CSortDlg::MergeSort(int x[])
{
int temp_array[10];
int len=1;
while (len<10) { //归并排序
MergePass(x,temp_array,len);//一趟两路归并后归并项长度加倍
len*=2;
MergePass(temp_array,x,len);
len*=2;
}
// delete[] temp_array;
}
void CSortDlg::MergePass(int init_array[],int merge_array[],const int len)
{//一趟归并排序
int i=0;
while (i+2*len<=9) {//对长度为len的子表两两归并，直到表中剩余元素个数不足2*len为止
merge(init_array,merge_array,i,i+len-1,i+2*len-1);
i+=2*len;
}
if (i+len<=9)
merge(init_array,merge_array,i,i+len-1,9); else
for (int j=i;j<=9;j++) {//若不能做归并，就复制
merge_array[j]=init_array[j];
}
}
void CSortDlg::merge(int init_array[],int merge_array[],const int l,const int m,const int n)
{
int i=l,j=m+1,k=l;
while (i<=m&&j<=n)
if (init_array[i]<=init_array[j]) {
merge_array[k]=init_array[i];
i++;k++;
}
else
{
merge_array[k]=init_array[j];
j++;k++;
}
if (i<=m)
for (int n1=k,n2=i;n1<=n&&n2<=m;n1++,n2++) {
merge_array[n1]=init_array[n2];
}
else
for (int n1=k, n2=j;n1<=n&&n2<=n;n1++,n2++) {
merge_array[n1]= init_array[n2];
}
}
折半插入排序：
void CSortDlg::BinaryInsertSort(int x[])
{
for (int i=1;i<10;i++)
{
BinaryInsert(x,i);
}
}
void CSortDlg::BinaryInsert(int x[],int i)
{
int left=0,right=i-1;
int temp=x[i];
while (left<=right) //利用折半查找找插入位置
{
int middle=(left+right)/2;//取中点
if (temp<x[middle]) //插入值小于中点值
{
right=middle-1;//向左缩小区间
}
else //否则向右缩小区间
left=middle+1;
}
for (int k=i-1;k>=left;k--)//成块移动，空出插入位置
{
x[k+1]=x[k];
}
x[align=left]=temp;//插入
}
直接选择排序：
void CSortDlg::SelectSort(int x[])
{
for (int i=0;i<9;i++) {
SelectExchange(x,i);
}
}
void CSortDlg::SelectExchange(int x[],const int i)
{
int k=i;
for (int j=i+1;j<10;j++)
if(x[j]<x[k])
k=j;
if(k!=i)
{
int temp=x[i];
x[i]=x[k];
x[k]=temp;
}
}
基数排序：
int CSortDlg::digit(int data,int n)
{
int i = -1;
for (int k = 0; k <= n;++k)
{
i = data % RADIX;
data = data / RADIX;
}
return i;
}
void CSortDlg::SortOnDigit(int* data,int d,int left,int right)
{
int c[RADIX] = {0}; //c[i]记录d位上为i的元素个数
for (int i = left; i <= right ;i++ )
{
++c[digit(data[i],d)]; //记录d位上相同的数据个数
}
for (int j = 1;j < RADIX ;++j )
{
c[j] += c[j-1]; //很明显，d位上较大（就是j的值），元素越大
//c[j]记录d位上小于等于j的元素的个数
}
int len = right - left +1;
int* tmp = new int[len];
//知道了有多少元素在d位置上比自己小，则可以确定d位上的值的元素位置
for (int k = right; k >= left; k--)
{
tmp[--c[digit(data[k],d)]] = data[k];
}
for (int m = left;m <= right ;++m )
{
data[m] = tmp[m - left];
}
delete[] tmp;
}
void CSortDlg::RadixSort(int* data,int left,int right)
{
for (int i = 0;i < WIDTH; ++i)
{
SortOnDigit(data,i,left,right);
}
}
快速排序：
void CSortDlg::quick_sort(int x[], int low, int high) //快速排序函数的实现过程
{
int pivotkey;
if(low<high)
{
pivotkey=partition(x,low,high);
quick_sort(x,low,pivotkey-1);
quick_sort(x,pivotkey+1,high);
}
}
int CSortDlg::partition(int x[],int low,int high)
{
int pivotkey;
pivotkey=x[low];
while(low<high)
{
while(low<high&&x[high]>pivotkey)
--high;
x[low]=x[high];
while(low<high&&x[low]<pivotkey)
++low;
x[high]=x[low];
}
// x[low]=x[0];
x[low]=pivotkey;
return low;
}
堆排序：
void CSortDlg::HeapSort(int*list,int num)
{
for(int i=(num-2)/2;i>=0;i--)
FiltDown(list,i,num-1);
for(i=num-1;i>=1;i--)
{
int temps=list[0];
list[0]=list[i];
list[i]=temps;
FiltDown(list,0,i-1);
// if(m_mark==1)
// show(list);
}
}
void CSortDlg::FiltDown(int*list,int i,int end)
{
int c=i;int ch=2*i+1;
int temp=list[i];
while(ch<=end)
{
if(ch<end&&list[ch]<list[ch+1])
ch++;
if(temp>=list[ch])break;
else
{
list[c]=list[ch];
c=ch;ch=2*ch+1;
}
}
list[c]=temp;
}
