排序总结

P.S:简书的latex数学公式好像有点问题。。。后续还会持续更新。

引入

在待排序的文件中，可能存在着多个具有相同排序码的记录。如果一个排序算法对于任意具有相同排序码的多个记录在排序之后，这些具有相同排序码的记录的相对次序仍保持不变，则称该排序算法为“稳定的”，否则称该排序算法是不稳定的。下面将介绍一些比较熟知的排序算法：

插入排序

基本思想：每次选择带排序的记录序列的第一个记录，按照排序码的大小将其插入已排序的记录序列中的适当位置，直到所有的记录全部排序完毕。

直接插入排序

//用直接插入排序法对A[i](i取0到n-1)进行排序
template <class T>
void DirectInsertionSort(T A[],int n)
{
int i,j;
T temp;
for(i=1;i<n;i++)
  {
//记录A[0]到A[i-1]已排序，当前要插入的记录是A[i]
  j=i-1;
  temp=A[i];
 //若temp的排序码小于A[j]的排序码且还未到记录A[0],则继续扫描
 while(j>=0&&temp.key<A[j].key)
     {
      //右移当前记录
      A[j+1]=A[j];
      j--;
     }
 //找到位置，将temp插入     
  A[j+1]=temp.key;
  }
}

算法复杂度为O($n^{2}$)，且排序是稳定的。

折半插入排序

//用折半插入排序法对A[i]进行排序
template <class T>
void BinayInsertSort(T A[],int n)
{
  int i,k,r;
  T temp;
  for(int i=1;i<n;i++)
   {
   temp=A[i];
   //采用折半法在已排序的A[0]~A[i-1]之间找A[i]的插入位置
   k=0;r=i-1;
   while(k<=r)
   {
   int m;
   m=(k+r)/2;
   if(temp.key<A[m].key)
     {
     //在前半部分继续找插入位置
     r=m-1;
     }
    else 
    {
    //在后半部分继续找插入位置
    k=m+1;
    }
   }
   // 找到插入位置k，先将A[k]~A[i-1]右移一个位置
   for(r=i;r>k;r--)
     {
     A[r]=A[r-1]；
     }
    //将temp插入
    A[k]=temp;
 }
}

使用折半插入排序时，需进行的比较次数与记录的初始状态无关，仅依赖与记录的个数。时间复杂度为O($nlog_{2}n$)

Shell排序(希尔排序法)

//用Shell排序法对A[0]~A[n-1]进行排序
template <class T>
void ShellSort(T A[],int n,int s)
{
 int i,j,k;
 T temp;
 //分组排序，初始增量为s，每循环一次增量减半，直到增量为0时结束
 for(k=s;k>0;k>>=1)  //k>>1即右移一位，等价于/2即减半。
 {
 //分组排序
 for(i=k;i<n;i++)
    {
    temp=A[i];
    j=i-k;
    //组内排序，将temp直接插入组内合适的记录位置
    while(j>=0&&temp.key<A[j].key)
     {
     A[j+k]=A[j];
     j-=k;
     }
    A[j+k]=temp;
    }
 }
}

时间复杂度为O($n^{3/2}$),且排序是不稳定的。

选择排序

基本思想：每次从待排序的记录中选出排序码最小的记录，然后在剩下的记录中选出次最小的记录，重复这个过程，直到完成全部排序。

直接选择排序

template <class T>
void DirectSelectSort(T A[],int n)
{
int i,j,k;
T temp;
for(i=0;i<n-1;i++)
  {
  k=i;
  //只负责找到位置，用k来记录位置
  for(j=i+1;j<n;j++)
    {
    if(A[j].key<A[k].key)
      k=j;
    }
    //这步才是交换的操作
   if(i!=k)
   {
    temp=A[k];
    A[k]=A[i];
    A[i]=temp;
   }
  }
}

时间复杂度为O($n^{2}$)，选择排序是不稳定的

树形选择排序

交换排序

基本思想：每次将排序文件中的两个记录的排序码进行比较，如果不满足排序要求，则交换这两个记录在文件中的顺序，直到文件中任意两个记录之间都满足排序要求未知。

冒泡排序

//用冒泡排序法对A[0]~A[n-1]排序
template <class T>
void BubbleSort(T A[],int n)
{
int i,j;
boolean flag;
T temp;
for(i=n-1,flag=(boolean)1;i>0&&flag;i--)
 {
//设置未交换标志
  flag=FALSE;
  for(j=0;j<i;j++)
  {
  if(A[j+1].key<A[j].key)
    {
    //有交换法神，置标志
    flag=TRUE;
    //交换
    temp=A[j+1];
    A[j+1]=A[j];
    A[j]=temp;
    }
  }
 }
}

冒泡排序是稳定的

快速排序

//用快速排序法对文件中的一组记录A[low]~A[high]进行排序
template <class T>
void QuickSort(T A[],int low,int high)
{
int i,j;
T temp;
if(low>=high) return;
i=low;j=high;temp=A[i];
while(i<j)
  {
  //从后往前进行比较，直到当前记录的排序码小于等于中心值
  while(i<j&&A[i].key<=temp.key) j--;
  if(i<j)
   {
   //将排序码小于等于中心值的记录，交换到前面当前空出来的记录位置
   A[i++]=A[j];
   }
  //从前往后进行比较，直到当前记录的排序码大于等于中心值
  while(i<j&&A[i].key<=temp.key) i++;
  if(i<j)
  {
  //将排序码大于中心值的记录交换到后面当前空出的记录位置
  A[j--]=A[i];
  }
 }
 //找到中心值对应的记录所在的位置，写入中心值对应的记录
 A[i]=temp;
 //递归处理排序码小于等于中心值的那组记录
 QuickSort(A,low,--j);
 //递归处理排序码大于等于中心值的那组记录
 QuickSort(A,++i,high);
}

时间复杂度为O($log_{2}n$)，快速排序算法是不稳定的。

分配排序

基本思想：先分配，后收集

基数排序

//用基数排序法对一单链表形式存储的文件中的一组记录进行排序
template <class T>
void RadixSort(T *pData,int Clow,int Chigh,int d)
{
typedef struct
  {
  T *pHead;
  T *pTail;
  }TempLink;
  int r=Chigh-Clow+1;
  //分配队列
  TempLink *tlink;
  T *p;
  //为分配队列分配内存
  tlink=new TempLink[r];
  for(int i=d-1;i>=0;i--)
   {
   //初始化分配队列指针
   for（int j=0;j<r;j++）
   {
   Tlink[j].pHead=tlink[j].pTail=NULL;
   }
   //将记录分配到r个队列中
   for(p=pData->next;p!=NULL;p=p->next)
   {
   j=p->key[i]-Clow;
   if(tlink[j].pHead==NULL)
    {
    Tlink[j].pHead=tlink[j].pTail=p;
    }
   else
   {
   Tlink[j].pTail->next=p;
   Tlink[j].pTail=p;
   }
   }
 //收集分配到r个队列中的记录
 for(j=0,p=pData;j<r;j++)
 {
 if(tlink[j].pHead!=NULL)
   {
   p->next=tlink[j].pHead;
   p=tlink[j].pTail;
   }
 }
 //将单链表尾部结点的指针置为空
 p->next=NULL;
}
//释放分配队列占用的内存
delete[]tlink;
}

时间复杂度为O($n$)，基数排序算法是稳定的。

归并排序

基本思想：将已经排序的子文件进行合并，得到完全排序的文件。合并是只要比较各自文件的第一个记录的排序码，排序码最小的那个记录就是排序后的第一个记录，去除这个记录，然后继续比较各自文件的第一个记录。便可找出排序后的第二个记录。如此反复，对每个字文件警告过一趟扫描，便可得到最终的排序结果。

//用二路归并排序对A[0]~A[n-1]进行排序
template <class T>
void MergeSort(T A[],int n)
{
int k;
T *B=new T[n];
//初始子文件长度为1
k=1;
while(k<n)
  {
  //将A中的子文件经过一趟归并存储到数组B中
  OnePassMerge(B,A,k,n);
  //归并后子文件长度增加1倍
  k<<=1;
  if(k>=n)
   {
   //一归并排序完毕，但结果在临时数组B中
   //调用标准函数memcpy()将其复制到A中
   //memcpy()包含在头文件<Mmemory.h>或<string.h>中
   
   memcpy(A,B,n*sizeof(T));
   }
   else
   {
   //将B中的子文件经过一趟归并存储到数组A中
   onePassMerge(A,B,k,n);
   //归并后子文件长度增加一倍
   k<<=1;
   }
  }
  //释放临时数组占用的内存空间
  delete []B;
}

//一趟归并函数，jiangSrc中部分排序的多个子文件鬼领导Dst中
//子文件的长度为Len
void OnePassMerge(T Dst[],T Src[],int Len,int n)
{
for(int i=0;i<n-2*Len;i+=2*Len)
  {
  //执行两两归并，将Src中长度为Len的子文件归并成长度为2*Len的子文件，结果存放在Dst中
  TwoWayMerge(Dst,Src,i,i+Len-1,n-1);
  }
  else
  {
  //尾部之多还有一个子文件，直接复制到Dst中
  memcpy(&Dst[i],&Src[i],(n-1)*sizeof(T));
  }
}

//两两归并函数，将Src中从s到e1的子文件和从e1+1到e2的子文件进行归并，结果存放到Dst中从s开始的位置
void TwoWayMerge(T Dst[],T Src[],int s,int e1,int e2)
{
for(int s1=s,s2=e1+1;s1<=e1&&s2<=e2;)
  {
   if(Src[s1].key<=Src[s2].key)
     {
     //第一个子文件的最前面的记录器排序码小，将其归并到Dst中
     Dst[s++]=Src[s1++];
     }
     else
     {
     //第二各自文件的最前面的记录其排序码小，将其归并到Dst中
      Dst[s++]=Src[s2++];
     }
  }
  if(s1<=e1)
  {
  //第一个子文件未归并完，将其直接复制到Dst中
  memcpy(&Dst[s],&Src[s1],(e1-s1+1)*sizeof(T));
  }
  else
  {
   //第二个子文件未归并完，将其直接复制到Dst中
  memcpy(&Dst[s],&Src[s2],(e2-s2+1)*sizeof(T));
  }
}

总的时间复杂度为O($n*log_{2}n$)，归并排序算法需要n个附加存储空间。