首页 关于 微信公众号
欢迎关注我的微信公众号

排序算法总结

2016-12-14

概述

排序分为内部排序和外部排序，内部排序是数据记录在内存中进行的排序，而外部排序是由于数据量较大而不得不借助于外存来容纳全部的排序记录，在排序的过程中需要访问外存。

我们这里常说的排序指的是内部排序。排序算法分为三类即插入排序、交换排序、选择排序。

  1. 插入排序：直接插入排序、折半插入排序、希尔排序
  2. 交换排序：冒泡排序、快速排序
  3. 选择排序：直接选择排序、堆排序

衡量排序算法的几个重要依据

稳定性

假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，ri=rj，且ri在rj之前，而在排序后的序列中，ri仍在rj之前，则称这种排序算法是稳定的；否则称为不稳定的。

排序算法的稳定性是衡量排序算法好坏的非常重要的一个依据。

时间复杂度

概念

1） 时间频度 一个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试，只需知道哪个算法花费的时间多，哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。

2）时间复杂度 在刚才提到的时间频度中，n称为问题的规模，当n不断变化时，时间频度T(n)也会不断变化。但有时我们想知道它变化时呈现什么规律。为此，我们引入时间复杂度概念。 一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n),使得当n趋近于无穷大时，T（n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=Ｏ(f(n)),称Ｏ(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。

在各种不同算法中，若算法中语句执行次数为一个常数，则时间复杂度为O(1),另外，在时间频度不相同时，时间复杂度有可能相同，如T(n)=n2+3n+4与T(n)=4n2+2n+1它们的频度不同，但时间复杂度相同，都为O(n2)。 按数量级递增排列，常见的时间复杂度有：常数阶O(1),对数阶O(log2n),线性阶O(n), 线性对数阶O(nlog2n),平方阶O(n2)，立方阶O(n3),…， k次方阶O(nk),指数阶O(2n)。随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低。 2、空间复杂度 与时间复杂度类似，空间复杂度是指算法在计算机内执行时所需存储空间的度量。记作: S(n)=O(f(n)) 我们一般所讨论的是除正常占用内存开销外的辅助存储单元规模。讨论方法与时间复杂度类似，不再赘述。

3）渐进时间复杂度评价算法时间性能 　　主要用算法时间复杂度的数量级(即算法的渐近时间复杂度)评价一个算法的时间性能。

求解算法的时间复杂度的具体步骤

⑴ 找出算法中的基本语句；

　　算法中执行次数最多的那条语句就是基本语句，通常是最内层循环的循环体。

⑵ 计算基本语句的执行次数的数量级；

　　只需计算基本语句执行次数的数量级，这就意味着只要保证基本语句执行次数的函数中的最高次幂正确即可，可以忽略所有低次幂和最高次幂的系数。这样能够简化算法分析，并且使注意力集中在最重要的一点上：增长率。

⑶ 用大Ο记号表示算法的时间性能。

　　将基本语句执行次数的数量级放入大Ο记号中。

　　如果算法中包含嵌套的循环，则基本语句通常是最内层的循环体，如果算法中包含并列的循环，则将并列循环的时间复杂度相加。例如：

　　for (i=1; i<=n; i++) 　　x++;

　　for (i=1; i<=n; i++) 　　for (j=1; j<=n; j++) 　　x++;

　　第一个for循环的时间复杂度为Ο(n)，第二个for循环的时间复杂度为Ο(n2)，则整个算法的时间复杂度为Ο(n+n2)=Ο(n2)。

　　常见的算法时间复杂度由小到大依次为：

　　Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n2)＜Ο(n3)＜…＜Ο(2n)＜Ο(n!)

　　Ο(1)表示基本语句的执行次数是一个常数，一般来说，只要算法中不存在循环语句，其时间复杂度就是Ο(1)。Ο(log2n)、Ο(n)、 Ο(nlog2n)、Ο(n2)和Ο(n3)称为多项式时间，而Ο(2n)和Ο(n!)称为指数时间。计算机科学家普遍认为前者是有效算法，把这类问题称 为P类问题，而把后者称为NP问题。

O(1)

Temp=i;i=j;j=temp;

以 上三条单个语句的频度均为1，该程序段的执行时间是一个与问题规模n无关的常数。算法的时间复杂度为常数阶，记作T(n)=O(1)。如果算法的执行时 间不随着问题规模n的增加而增长，即使算法中有上千条语句，其执行时间也不过是一个较大的常数。此类算法的时间复杂度是O(1)。

O(n^2)

2.1. 交换i和j的内容 sum=0； （一次） for(i=1;i<=n;i++) （n次 ） for(j=1;j<=n;j++) （n^2次 ） sum++； （n^2次 ） 解：T(n)=2n^2+n+1 =O(n^2)

2.2.

for (i=1;i<n;i++)
{ 
    y=y+1;         ①   
    for (j=0;j<=(2*n);j++)    
       x++;        ②      
}          
解： 语句1的频度是n-1
          语句2的频度是(n-1)*(2n+1)=2n^2-n-1
          f(n)=2n^2-n-1+(n-1)=2n^2-2
          该程序的时间复杂度T(n)=O(n^2).

O(n)

2.3

a=0;
b=1;                      ①
for (i=1;i<=n;i++) ②
{  
   s=a+b;　　　　③
   b=a;　　　　　④  
   a=s;　　　　　⑤
}
解： 语句1的频度：2,        
           语句2的频度： n,        
          语句3的频度： n-1,        
          语句4的频度：n-1,    
          语句5的频度：n-1,                                  
          T(n)=2+n+3(n-1)=4n-1=O(n).

O(log2n)

2.4

     i=1;       ①
    while (i<=n)
       i=i*2; ②
解： 语句1的频度是1,  
          设语句2的频度是f(n),   则：2^f(n)<=n;f(n)<=log2n    
          取最大值f(n)= log2n,
          T(n)=O(log2n )

O(n^3)

2.5

    for(i=0;i<n;i++)
    {  
       for(j=0;j<i;j++)  
       {
          for(k=0;k<j;k++)
             x=x+2;  
       }
    }
解： 当i=m, j=k的时候,内层循环的次数为k当i=m时, j 可以取 0,1,...,m-1 , 所以这里最内循环共进行了0+1+...+m-1=(m-1)m/2次所以,i从0取到n, 则循环共进行了: 0+(1-1)*1/2+...+(n-1)n/2=n(n+1)(n-1)/6所以时间复杂度为O(n^3).

一个经验规则

有如下复杂度关系

c < log2N < n < n * Log2N < n^2 < n^3 < 2^n < 3^n < n!

其中c是一个常量，如果一个算法的复杂度为c 、 log2N 、n 、 n*log2N ,那么这个算法时间效率比较高 ，如果是 2^n , 3^n ,n!，那么稍微大一些的n就会令这个算法不能动了，居于中间的几个则差强人意。

空间复杂度

类似于时间复杂度的讨论，一个算法的空间复杂度(Space Complexity)S(n)定义为该算法所耗费的存储空间，它也是问题规模n的函数。渐近空间复杂度也常常简称为空间复杂度。 空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度。一个算法在计算机存储器上所占用的存储空间，包括存储算法本身所占用的存储空间，算法的输入输出数据所占用的存储空间和算法在运行过程中临时占用的存储空间这三个方面。算法的输入输出数据所占用的存储空间是由要解决的问题决定的，是通过参数表由调用函数传递而来的，它不随本算法的不同而改变。存储算法本身所占用的存储空间与算法书写的长短成正比，要压缩这方面的存储空间，就必须编写出较短的算法。算法在运行过程中临时占用的存储空间随算法的不同而异，有的算法只需要占用少量的临时工作单元，而且不随问题规模的大小而改变，我们称这种算法是“就地"进行的，是节省存储的算法，如这一节介绍过的几个算法都是如此；有的算法需要占用的临时工作单元数与解决问题的规模n有关，它随着n的增大而增大，当n较大时，将占用较多的存储单元。

如当一个算法的空间复杂度为一个常量，即不随被处理数据量n的大小而改变时，可表示为O(1)；当一个算法的空间复杂度与以2为底的n的对数成正比时，可表示为0(10g2n)；当一个算法的空I司复杂度与n成线性比例关系时，可表示为0(n).若形参为数组，则只需要为它分配一个存储由实参传送来的一个地址指针的空间，即一个机器字长空间；若形参为引用方式，则也只需要为其分配存储一个地址的空间，用它来存储对应实参变量的地址，以便由系统自动引用实参变量。

简单排序算法

直接插入排序

1）描述

  1. 直接插入排序就是第 i 趟把第 i 个元素放到前面已经排好序的序列中去
  2. 重复上述操作。 n 个元素共需 n-1 趟扫描，每趟将一个元素插入到它前面的子序列中

2）复杂度分析

3) 稳定性

直接插入排序是稳定的。

4）C 语言实现

void printSort(int table[],int size)
{
    for (int i = 0; i<size; i++) {
         printf("%d\t",table[i]);
    }
    printf("\n");
}
void insertSort(int table[],int size)
{
    
    for(int i=1;i<size;i++){//n-1趟扫描
        int temp=table[i],j;//每趟将table[i]插入到前面排序序列中
        for(j=i-1;j>=0&&temp<table[j];j--)
            table[j+1]=table[j];//将较大元素向后移动
        table[j+1]=temp;//temp到达插入位置
    }
    printSort(table,size);
}

希尔排序

1） 描述

  1. 将一个数据序列分成若干组，每组由若干相隔一段距离的元素组成，这段距离称为增量，在一组内采用直接插入排序算法进行排序
  2. 当增量为 1 时，只有一组，元素是整个序列，在进行一次直接插入排序即可

2） 复杂度分析

3) 稳定性

稳定性不确定

4）C 语言实现

void shellSort(int table[],int size)
{
    for(int delta=size/2;delta>0;delta/=2)//进行若干趟扫描，控制增量，增量减半
        for(int i=delta;i<size;i++){//一趟分若干组，每组进行直接插入排序
            int temp=table[i],j;
            for(j=i-delta;j>=0&&temp<table[j];j-=delta)
                table[j+delta] = table[j];
            table[j+delta] = temp;
        }
    printSort(table,size);
}

冒泡排序

1）描述

比较两个相邻元素的关键值，如果反序，则交换。若按升序排序，每一趟将被扫描的数据序列中的最大元素交换到最后位置，就像气泡从水里冒出一样。

2）复杂度分析

3) 稳定性

稳定

4） C语言代码

void bubleSort(int table[],int size)
{
    int exchange = 1;
    for(int i=1;i<size&&exchange==1;i++){//有交换时才进行下一趟排序
        exchange = 0;//假定元素没有交换
        for(int j=0;j<size-i;j++)
            if(table[j]>table[j+1]){
                int temp = table[j];
                table[j] = table[j+1];
                table[j+1] = temp;
                exchange = 1;
            }
    }
    printSort(table,size);
}

快速排序

1）描述

在数据序列中选择一个值作为比较的基准值，每趟从数据序列的两端开始交替进行，将小于基准值的元素交换到序列前端，大于基准值的元素交换到序列后端，介于两者之间的位置则称为基准值的最终位置。同时序列被划分成两个子序列，再用同样的方法对了两个子序列进行排序，知道子序列长度为1，则完成排序。

2）复杂度分析

3） 稳定性

不稳定

4) C语言代码

void quicklySort(int[],int,int);

void quickSort(int table[],int size)
{
    quicklySort(table,0,size-1);
    printSort(table, size);
}

void quicklySort(int table[],int begin,int end)
{
    if(begin<end){
        int i=begin,j=end;
        int vot=table[i];//基准值
        while(i!=j){//一趟排序
            while(i<j&&vot<=table[j])
                j--;
            if(i<j)//如果有小元素（当有table[j]<vot的时候，该条件恒成立）
                table[i++]=table[j];//把后面的小元素向前移动
            while(i<j&&table[i]<=vot)
                i++;
            if(i<j)
                table[j--]=table[i];//把大元素向后移动
        }
        table[i]=vot;//基准值到达最终位置
        quicklySort(table,begin,j-1);//前段子序列进行排序
        quicklySort(table,i+1,end);//后端子序列进行排序
    }
}

直接选择排序

1）描述

第一趟从n个元素的数据中选出关键字最小或最大的元素放到最前或最后位置，下一趟再从n-1个元素……。直接选择排序算法可用顺序表和单链表实现。

2）复杂度分析

3）稳定性

不稳定

4) 代码

void selectSort(int table[],int size)
{
    for(int i=0;i<size-1;i++){
        int min=i;
        for(int j=i+1;j<size;j++)
            if(table[j]<table[min])
                min=j;
        if(min!=i){
            int temp=table[i];
            table[i]=table[min];
            table[min]=temp;
        }
    }
    printSort(table, size);
}

堆排序

1）描述

  1. 堆：这里的堆不是数据结构里面的堆栈，而是一种数据结构。堆可以视为一颗完全二叉树，完全二叉树的一个优秀的性质是除了最底层之外，每一层都是满的，这使得堆可以利用数组来表示，每一个节点对应数组中的一个元素。二叉堆一般分为两种，最小堆和最大堆。
  2. 最大堆：堆中每个父节点的值都大于等于其孩子节点，这样的堆就是一个最大堆。 最小堆：对中的每个父节点都小于等于其孩子节点，这样的堆就是一个最小堆
  3. 堆排序：堆排序分两个阶段。首先将一个数据序列建成堆序列，根节点值是最小（大）值；然后采用选择排序思路，每趟将根结点值交换到最后，再将其余值调整成堆，依次重复，直到排序完成

2） 复杂度分析

3）稳定性

不稳定

4） 代码

void sift(int[],int,int);
void heapSort(int table[],int size)
{
    int n=size;
    for(int j=n/2-1;j>=0;j--)
        //创建最小堆
        sift(table,j,n-1);
    for(int j=n-1;j>0;j--){
        //每趟将最小值交换到后面，再调整成堆
        int temp=table[0];
        table[0]=table[j];
        table[j]=temp;
        sift(table,0,j-1);
    }
}

void sift(int table[],int begin,int end)
{
    int i=begin,j=2*i+1;//i为子树的根，j为i节点的左孩子
    int temp=table[i];//获得第i个元素的值
    while(j<=end){
        //沿较小值孩子节点向下筛选
        if(j<end&&table[j]>table[j+1])
            //数组元素比较
            j++;  //j为左右孩子的较小者
        if(temp>table[j]){
            //若父母结点值较大
            table[i]=table[j];
            //孩子节点中的较小者上移
            i=j;  //i,j向下一层
            j=2*i+1;
        }
        else break;
    }
    table[i]=temp;//当前子树的原根值调整后的位置
}

void merge(int X[],int Y[],int m,int r,int n)
{
    //一次归并
    int i=m,j=r,k=m;
    int xLength = sizeof(X)/sizeof(X[0]);
    while(i<r&&j<r+n&&j<xLength){
        //将X中两个相邻子序列归并到Y中
        if(X[i]<X[j])
            //较小值复制到Y中
            Y[k++]=X[i++];
        else Y[k++]=X[j++];
        while(i<r)  //将前一个子序列剩余元素复制到Y中
            Y[k++]=X[i++];
        while(j<r+n&&j<xLength)
            //将后一个子序列剩余元素复制到Y中
            Y[k++]=X[j++];
    }
}

void mergepass(int X[],int Y[],int n) //一趟归并
{
    int i=0;
    int xLength = sizeof(X)/sizeof(X[0]);
    while(i<xLength-2*n+1){
        merge(X,Y,i,i+n,n);
        i+=2*n;
    }
    if(i+n<xLength)
        merge(X,Y,i,i+n,n);
    //再一次归并
    else
        for(int j=i;j<xLength;j++)
            //将X剩余元素复制到Y中
            Y[j]=X[j];
}

void mergeSort(int X[])
{
    int xLength = sizeof(X)/sizeof(X[0]);
    int Y[] = new int[xLength];
    int n=1;
    while(n<xLength){
        mergepass(X,Y,n);
        n*=2;
        if(n<xLength){
            mergepass(Y,X,n);
            n*=2;
        }
    }
}

Blog

Opinion

Project