排序函数(直接InsertSort，希尔ShellSort，选择SelectSort，快排QuickSort，堆排HeapSort，归并MergeSort)的实现（除基数排序），可以多点评论啊，有错火改
#include <iostream> using namespace std; typedef int Elm; struct node { Elm data;//数据域 int key;//标志符 }; //直接插入排序 void InsertSort(node *E,int n)//稳定的排序 时间复杂度O(n^2) { int i,j;node r; for(i=1;i<n;i++) { j=i-1;//保证 j 在要当前目标数值的前面 r=E[i]; while(j>=0&&E[j].key>r.key) { E[j+1]=E[j]; j--; } E[j+1]=r; } } //希尔排序 void ShellSort(node *E,int n) { int i,j,flag;node r; flag=n/2;//分两组 while(flag>0)//以细分为判定标准 { for(i=flag;i<n;i++) { r=E[i]; j=i-flag; while(j>=0&&r.key<E[j].key) { E[j+flag]=E[j]; j=j-flag; } E[j+flag]=r; } flag/=2; } } //冒泡排序_改良版 O(n^2) void BubbleSort(node *E,int n) { int i,j;node r; bool f=false;//标识符，用来标记，当没有交换的时候就是排序完成的时候 for(i=0;i<n-1;i++) { for(j=n-1;j>i;j--) { if(E[j].key<E[i-1].key) { r=E[j]; E[j]=E[j-1]; E[j-1]=r; f=true; } if(f==false) return ; } } } //快速排序 O(log_2n) void QuickSort(node *E ,int s,int t) { int i=s,j=t; node r; if(s<t) { r=E[s];//把这区间的第一元素给 r ,让 r 成为基准 while(i!=j) { while(j>i&&E[j].key>=r.key) j--;//从后面往前面遍历，直到找到比头 标准r 小的 E[i]=E[j]; while(i<j&&E[i].key<r.key) i++; //从前面往前面遍历，直到找到比头 标准r 大的 E[j]=E[i]; } E[i]=r; QuickSort(E,s,i-1);//对左区间递归排序 QuickSort(E,i+1,t); //对右区间递归排序 } } //选择排序 O(n^2) void SelectSort(node *E,int n) { int i,j,k; node temp; for (i=0;i<n-1;i++) //做第i趟排序 { k=i; for (j=i+1;j<n;j++) //在[i..n-1]中选key最小的R[k] if (E[j].key<E[k].key) k=j; //k记下的最小关键字所在的位置 if (k!=i) //交换R[i]和R[k] { temp=E[i]; E[i]=E[k]; E[k]=temp; } } } //堆排序 O(nlog_2n) 特别声明，数组开始从1开始，非0开始，否则代码实现会出错 void sift(node* E,int low,int high) //调整堆的算法 { int i=low,j=2*i; //E[j]是E[i]的左孩子 node temp=E[i]; while (j<=high) { if (j<high && E[j].key<E[j+1].key) j++;//比较两个孩子，标记数值大的下标 if (temp.key<E[j].key) { E[i]=E[j]; //将E[j]调整到双亲结点位置上 i=j; //修改i和j值,以便继续向下筛选 j=2*i; } else break; } E[i]=temp; } void HeapSort(node* E,int n) { int i; node temp; for (i=n/2;i>=1;i--) //循环建立初始堆 sift(E,i,n); for (i=n;i>=2;i--) //进行n-1次循环,完成推排序 { temp=E[1]; //将第一个元素同当前区间内E[1]对换 E[1]=E[i]; E[i]=temp; sift(E,1,i-1); //筛选E[1]结点,得到i-1个结点的堆 } } //归并排序 O(nlog_2n) void Merge(node *R,int low,int mid,int high) { node *R1; int i=low,j=mid+1,k=0; //k是R1的下标,i、j分别为第1、2段的下标 R1=new node[high-low+1]; while (i<=mid && j<=high) if (R[i].key<=R[j].key) //将第1段中的记录放入R1中 { R1[k]=R[i]; i++;k++; } else //将第2段中的记录放入R1中 { R1[k]=R[j]; j++;k++; } while (i<=mid) //将第1段余下部分复制到R1 { R1[k]=R[i]; i++;k++; } while (j<=high) //将第2段余下部分复制到R1 { R1[k]=R[j]; j++;k++; } for (k=0,i=low;i<=high;k++,i++) //将R1复制回R中 R[i]=R1[k]; delete []R1; } void MergePass(node *R,int length,int n) { int i; for (i=0;i+2*length-1<n;i=i+2*length) //归并length长的两相邻子表 Merge(R,i,i+length-1,i+2*length-1); if (i+length-1<n) //余下两个子表,后者长度小于length Merge(R,i,i+length-1,n-1); //归并这两个子表 } void MergeSort(node *R,int n) { int length; for (length=1;length<n;length=2*length) MergePass(R,length,n); }