排序

　所谓排序，就是要整理文件中的记录，使之按关键字递增(或递减)次序排列起来。

　　排序是数据处理中经常使用的一种重要运算。在计算机及其应用系统中，花费在排序上的时间在系统运行时间中占有很大比重，并且排序本身对推动算法分析的发展也起很大作用。目前已有上百种排序方法，但并没有一个万能的排序方法来解决所有问题，接下来介绍几种常用的排序方法，并对它们进行分析和比较。

排序算法性能评价

评价排序算法好坏的标准主要有两条：

执行时间和所需的辅助空间

算法本身的复杂程度

排序算法的时间复杂度：

　　大多数排序算法的时间开销主要是关键字之间的比较和记录的移动。有的排序算法其执行时间不仅依赖于问题的规模，还取决于输入实例中数据的状态。

排序算法的空间复杂度：

　　若排序算法所需的辅助空间并不依赖于问题的规模n，即辅助空间是O(1)，则称之为就地排序(In-PlaceSou)。非就地排序一般要求的辅助空间为O(n)。

插入排序

　　插入排序(Insertion Sort)的基本思想是：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子文件中的适当位置，直到全部记录插入完成为止。

　　常用的插入排序：直接插入排序 和希尔排序。

1.直接插入排序

　　排序过程中每次从无序表中取出第一个元素，将它插入到有序表中的适当位置，使之成为新的有序表，重复n-1次可完成排序过程。

　　时间复杂度为O（n^2），空间复杂度为O（1），稳定的。

伪码：

//直接插入排序void straightSelectSort(Record Array[], int n){    for(i = 0~n-1)        Small = Array[i];        for(j = i+1~n-1)            if(Small > Array[j])                Small=Array[j];        swap(Small,Array[i]);}

2.希尔排序

　　希尔排序（Shell Sort）又称为“缩小增量排序”。是1959年由D.L.Shell提出来的。该方法先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下（接近最好情况），效率是很高的。

　　在希尔排序开始时增量较大，分组较多，每组的记录数目少，故各组内直接插入较快，后来增量d_i逐渐缩小，分组数逐渐减少，而各组的记录数目逐渐增多，但由于已经按d_i-1作为距离排过序，使文件较接近于有序状态，所以新的一趟排序过程也较快。

　　希尔排序是不稳定的。

伪码：

void Insort(int a[],int n, int x)//x为步长，n为序列长度{    for (int i=x;i
      
       =x;j-=x){            if(a[j]
       
        0;i/=2){
    //设置增量为2，也就是步长每次减少2        for (int j=0;j

交换排序

　　交换排序是通过两两比较待排序记录的关键字，发现两个记录的次序相反时即进行交换，直到没有反序的记录为止。

　应用交换排序基本思想的主要排序方法有：冒泡排序和快速排序。

1.冒泡排序

　　将被排序的记录数组S[1..n]垂直排列，每个记录s[i]看作是重量为s[i]的气泡。根据轻气泡不能在重气泡之下的原则，从下往上扫描数组s：凡扫描到违反本原则的轻气泡，就使其向上"飘浮"。如此反复进行，直到最后任何两个气泡都是轻者在上，重者在下为止。

　　平均时间复杂度为O（n^2），空间复杂度为O（1），由于是交换式的所以稳定。

代码：

void BubbleSort(SeqList R){ //采用自下向上扫描，对R做冒泡排序     int i，j；     Boolean exchange； //交换标志     for(i=1;i
      
       =i；j--) //对当前无序区R[i..n]自下向上扫描        if(R[j+1].key

2.快速排序

　　设当前待排序的无序区为S[low..high]，利用分治法可将快速排序的基本思想描述为：

　　①分解：

　在S[low..high]中任选一个记录作为基准(Pivot)，以此基准将当前无序区划分为左、右两个较小的子区间S[low..pivotpos-1)和S[pivotpos+1..high]，并使左边子区间中所有记录的关键字均小于等于基准记录(不妨记为pivot)的关键字pivot.key，右边的子区间中所有记录的关键字均大于等于pivot.key，而基准记录pivot则位于正确的位置(pivotpos)上，它无须参加后续的排序。

　　注意：

　划分的关键是要求出基准记录所在的位置pivotpos。划分的结果可以简单地表示为(注意pivot=S[pivotpos])：

　S[low..pivotpos-1].keys≤S[pivotpos].key≤S[pivotpos+1..high].keys

其中low≤pivotpos≤high。

　　②求解：

　通过递归调用快速排序对左、右子区间S[low..pivotpos-1]和S[pivotpos+1..high]快速排序。

　　③组合：

　因为当"求解"步骤中的两个递归调用结束时，其左、右两个子区间已有序。对快速排序而言，"组合"步骤无须做什么，可看作是空操作。

　　在当前无序区中选取划分的基准关键字是决定算法性能的关键。

　　由于快速排序的交换思想，可知它是不稳定的。

　　它的平均复杂度可以计算出为O（nlogn），空间复杂度为O（1）。

代码：

int Partition(SeqList R，int i，int j) {
     //调用Partition(R，low，high)时，对R[low..high]做划分，     //并返回基准记录的位置      ReceType pivot=R[i]； //用区间的第1个记录作为基准 '      while(i
      
       =pivot.key) //pivot相当于在位置i上          j--； //从右向左扫描，查找第1个关键字小于pivot.key的记录R[j]        if(i
       
        pivot.key            R[j--]=R[i]; //相当于交换R[i]和R[j]，交换后j指针减1       } //endwhile      R[i]=pivot； //基准记录已被最后定位      return i；    } //partitionvoid QuickSort(SeqList R，int low，int high)   { //对R[low..high]快速排序     int pivotpos； //划分后的基准记录的位置     if(low

选择排序

　　选择排序通过每一趟从待排序的记录中选出关键字最小的记录，顺序放在已排好序的子文件的最后，直到全部记录排序完毕。

　常用的选择排序方法有直接选择排序和堆排序。

1.直接选择排序

n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果：

　　在无序区S[1..n]中选出关键字最小的记录S[k]，将它与无序区的第1个记录S[1]交换，使S[1..1]和S[2..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。第i趟排序开始时，当前有序区和无序区分别为S[1..i-1]和S[i..n](1≤i≤n-1)。该趟排序从当前无序区中选出关键字最小的记录S[k]，将它与无序区的第1个记录S[i]交换，使S[1..i]和S[i+1..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。

　这样，n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果。

　　平均时间复杂度为O(n^2)，空间复杂度为O（1）。

　　由于这个选择的关系，有可能会把相同元素的相对位置改变，故为不稳定的。

代码：

void SelectSort(SeqList R){   int i，j，k；   for(i=1;i

2.堆排序

1.堆的定义

n个关键字序列K_l，K₂，…，K_n称为堆，当且仅当该序列满足如下性质(简称为堆性质)：

　(1) k_i≤K_2i且k_i≤K_2i+1 或(2)K_i≥K_2i且k_i≥K_2i+1(1≤i≤

)

2.堆的分类

　　堆可分为大根堆和小根堆。

　　根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最小者的堆称为小根堆。

　根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最大者，称为大根堆。

3.基本思想

　　通常堆是通过一维数组来实现的。在起始数组为 0 的情形中：

堆的根节点（即堆积树的最大值）存放在数组位置 1 的地方;

　　　　注意：不使用位置 0，否则左子树永远为 0^[2]

父节点i的左子节点在位置 (2*i);

父节点i的右子节点在位置 (2*i+1);

子节点i的父节点在位置 floor(i/2);

　　在堆的数据结构中，堆中的最大值总是位于根节点。堆中定义以下几种操作：

最大堆调整（Max_Heapify）：将堆的末端子结点作调整，使得子结点永远小于父结点

创建最大堆（Build_Max_Heap）：将堆所有数据重新排序

堆排序（HeapSort）：移除位在第一个数据的根结点，并做最大堆调整的递归运算

4.算法复杂度

　　堆排序的最坏时间复杂度为O(nlgn)。堆排序的平均性能较接近于最坏性能。由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录数较少的文件。

　堆排序是就地排序，辅助空间为O(1)，它是不稳定的排序方法。

代码:

//筛选法 void sift(int E[],int j,int length) {     int i=j;     int c = 2*i+1;//数据从0开始      while(c < length)     {         if((c+1
      
       
        E[c])              break;//此节点数据已经比孩子节点数据大 则停止循环         else         {             int t=E[i];             E[i]=E[c];             E[c]=t;              i=c;//继续重复上述操作，直到孩子节点小于此节点或到数的最后一层             c = 2*i+1;         }     } } //堆排序 void HeapSort(int E[],int n)//第二个参数是数组长度 {     //初始化堆     for(int i=n/2;i>=0;i--)//i=n/2是从倒数第二行开始         sift(E,i,n);      for(int i=0;i

归并排序

　　归并排序(Merge Sort)是利用"归并"技术来进行排序。归并是指将若干个已排序的子文件合并成一个有序的文件。

1、算法基本思路

　设两个有序的子文件(相当于输入堆)放在同一向量中相邻的位置上：R[low..m]，R[m+1..high]，先将它们合并到一个局部的暂存向量R1(相当于输出堆)中，待合并完成后将R1复制回R[low..high]中。

（1）合并过程

　合并过程中，设置i，j和p三个指针，其初值分别指向这三个记录区的起始位置。合并时依次比较R[i]和R[j]的关键字，取关键字较小的记录复制到R1[p]中，然后将被复制记录的指针i或j加1，以及指向复制位置的指针p加1。

　重复这一过程直至两个输入的子文件有一个已全部复制完毕(不妨称其为空)，此时将另一非空的子文件中剩余记录依次复制到R1中即可。

（2）动态申请R1

　实现时，R1是动态申请的，因为申请的空间可能很大，故须加入申请空间是否成功的处理。

　　平均时间复杂度为O（nlogn），空间复杂度为O（n），稳定的。

代码：

void Merge(SeqList R，int low，int m，int high){
     //将两个有序的子文件R[low..m)和R[m+1..high]归并成一个有序的     //子文件R[low..high]     int i=low，j=m+1，p=0； //置初始值     RecType *R1； //R1是局部向量，若p定义为此类型指针速度更快     R1=(ReeType *)malloc((high-low+1)*sizeof(RecType))；     if(! R1) //申请空间失败       Error("Insufficient memory available!")；     while(i<=m&&j<=high) //两子文件非空时取其小者输出到R1[p]上       R1[p++]=(R[i].key<=R[j].key)?R[i++]：R[j++]；     while(i<=m) //若第1个子文件非空，则复制剩余记录到R1中       R1[p++]=R[i++]；     while(j<=high) //若第2个子文件非空，则复制剩余记录到R1中       R1[p++]=R[j++]；     for(p=0，i=low；i<=high；p++，i++)       R[i]=R1[p]；//归并完成后将结果复制回R[low..high]} //Merge

分配排序

　　　分配排序的基本思想：排序过程无须比较关键字，而是通过"分配"和"收集"过程来实现排序.它们的时间复杂度可达到线性阶：O(n)。

　　分配排序包括桶排序和基数排序。

1.桶排序

　　桶排序(Bucket Sort)，其基本思想是：设置若干个桶，依次扫描待排序的记录R[0]，R[1]，…，R[n-1]，把关键字等于k的记录全都装入到第k个桶里(分配)，然后按序号依次将各非空的箱子首尾连接起来(收集)。

　　箱子的个数取决于关键字的取值范围。

　　桶排序的平均时间复杂度是线性的，即O(n)。但最坏情况仍有可能是O(n^2)。空间复杂度为O（m+n）。（m为每个桶的值域）

伪码：

void BucketSon(R){ //对R[0..n-1]做桶排序，其中0≤R[i].key<1(0≤i

2.基数排序

　　基数排序(Radix Sort)是当每个桶的值域区间很大时对桶排序的改进。

　　将一个记录的值即排序码拆分为多个部分来进行比较。例如如果要对0~9999之间的整数进行排序，可以先按照千位数字进行桶排序，将所有数字分配到10个桶中，接下来，继续按照桶排序的方法对百位、十位、个位进行排序，这样，可以完成排序。这种将排序码拆分为多个字码分别来进行排序的方法就是基数排序。

代码： 具体参见

//数组实现#include
      
       using namespace std;int data[10]={
    73, 22, 93, 43, 55, 14, 50, 65, 39, 81};int tmp[10];int count[10];int maxbit(int data[],int n)//取数据位数{    int d=1;    for(int i=0;i
       
        d)            d=c;    }    return d;}void RadixSort(int data[],int n){        int d=maxbit(data,n);//获取数据最大位数        int r=1;    for(int i=0;i
        
         =0;j--)        {            int p=data[j]/r;            int s=p%10;            tmp[count[s]-1]=data[j];//由于如果此位相同的数字有两个 那计数是从0开始的，所以它的位置就应该-1            count[s]--;            //cout<
         
          <<" ";        }        for(int i=0;i

导航：

本文由创作，采用进行许可。欢迎转载，请注明出处：
转载自：