排序算法分析与总结（堆排序，快速排序，归并排序，排序稳定性，基数排序）

排序算法总结

排序算法总结... 1

1概念... 1

2比较排序分类介绍... 2

2.1堆排序... 2

2.2归并排序（Merge Sort）... 6

2.3快速排序（Quicksort）... 9

2.3.3随机快速排序... 10

3非比较排序分类介绍... 11

3.1计数排序（Counting sort）... 11

3.2基数排序（Radix sort）... 11

1概念

原地排序：在排序输入数组时，只有常数个元素被放到数组以外的空间中去。

稳定性：具有相同值得元素在输出数组中的相对次序与他们输入数组中的次序相同。

比较排序：排序结果中，个元素的次序基于输入元素间的比较，我们把这类排序算法叫做比较排序。如：冒泡，插入，快速，堆，归并排序等。可以证明，比较排序的下界是clip_image0021_thumbclip_image0041_thumb

非比较排序：一般有前提条件，常用的有：计数排序，基数排序，桶排序等。

排序算法

平均时间

最坏时间

额外空间

稳定性

冒泡排序

clip_image0061_thumb

clip_image0062_thumb

clip_image0081_thumb

稳定

插入排序

clip_image0063_thumb

clip_image0064_thumb

clip_image0082_thumb

稳定

堆排序

clip_image0101_thumb

clip_image0102_thumb

O(1)

不稳定

快速排序

clip_image0103_thumb

clip_image0065_thumb

O(1) 或其他

不稳定

归并排序

clip_image0104_thumb

clip_image0105_thumb

O(1)

稳定

基数排序

clip_image0121_thumb

clip_image0122_thumb

O(n+k)

稳定

选择排序

clip_image0066_thumb

clip_image0067_thumb

O(1)

不稳定

希尔排序

不确定

不确定

clip_image0141_thumb

不稳定

下面我重点介绍一下，堆排序，归并排序，快速排序，基数排序

2比较排序分类介绍

2.1堆排序

2.1.1基本概念

堆是一种数据结构。（二叉）堆数据结构，它可以被视为一个完全二叉树，树的每一层都填满，最后一层除外。

clip_image0162_thumb

获取父代与子代的方法。（注c,c++中从0开始，稍微注意下）

Parent(i)

return i/2

Left(i)

return 2i

Right(i)

return 2i + 1

二叉堆分两种：

1最大堆：A[parten[i]]>=A[i];

2最小堆：A[parten[i]]<=A[i];

clip_image0181_thumb

2.1.2保持堆的性质

输入一个数组A,下标i,当Max_Heapyify被调用时，我们假设以left(i),Right(i),为跟结点的二叉树都是最大堆，i有可能小于其子女，我们使用该函数来保持最大堆的性质。

clip_image0201_thumb

下图，函数输入i=2;

clip_image0221_thumb

2.1.3建堆

从倒数第二层开始，往上建堆（因为倒数第一层是叶节点）。

clip_image0241_thumb

具体过程如下：

clip_image0261_thumb

可以证明，建堆的时间复杂度是clip_image0281_thumb.

2.1.4堆排序

有了上面的铺垫，堆排序即每次将跟结点放入数组最后一位，然后使堆的长度减一，循环直至堆的长度为1。

clip_image0301_thumb

图释如下：

clip_image0321_thumb

建堆的过程需要，重新排列n此，所以整个算法的时间复杂度是clip_image0341_thumb。

2.1.5堆排序常见应用：

处理优先级队列。

// chapter6.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include<iostream>
#include<vector>

using namespace std;

void Max_Heapify( vector<double>& A,int i);
void Build_MAX_Heap(vector<double>& A);
void HeapSort(vector<double>& A);





int _tmain(int argc, _TCHAR* argv[])
{

    double data[]={4,1,3,2,16,9,10,14,8,7};
    vector<double>A(10,1); 
    

    for(int i=0;i<A.size();i++)
    {
        A[i]=data[i];

    }

    HeapSort(A);


        for(int i=0;i<A.size();i++)
    {
        

        cout<<A[i]<<endl;
    }

    return 0;
}



void Build_MAX_Heap(vector<double>& A) //以vector A为内容建立堆
{
    for(int i=(A.size())/2;i>=0;i--)
        Max_Heapify(A,i);
}



void Max_Heapify( vector<double> &A,int i)  //A表示一个二叉堆，调整i作为跟结点的二叉堆，保持堆的性质。
{
    int l=2*i+1;
    int  r=2*i+2;

    int largest=i;
    if(l<A.size() && A[l]>A[i])
        largest=l;

    if(r<A.size() && A[r]>A[largest])
        largest=r;

    if(largest!=i)  //如果出现比跟结点大的，交换。
    {
        double temp=A[i];
        A[i]=A[largest];
        A[largest]=temp;
        Max_Heapify(A,largest);    //交换了之后下面的可能违反了堆得性质。
    }

}


void HeapSort(vector<double>& A)  //对vector A的内容进行堆排序
{
    Build_MAX_Heap(A);


    vector<double> B ;
    for(int i=A.size()-1;i>0;i--)  //交换A[i] 与A[0];
    {
        double temp=A[0];
        A[0]=A[i];
        A[i]=temp;


        B.push_back(A[i]);
        A.pop_back();        //把A末尾删除，并且保存到vector B


        Max_Heapify(A,0);//因为0和最后一个位置交换了，要保持最大堆的性质，要执行此函数


    }

    while(!B.empty())
    {
        A.push_back(B.back());
        B.pop_back();
    }
    
    

}

2.2归并排序（Merge Sort）

归并排序采用了分治模式解决问题。分治模式每次递归都有三个步骤：

1分解（Divide）:将原问题分解

2解决(Conquer)：递归的解决各子问题，若子问题够小，可以直接解决。

3合并（Combine）:将子问题的结果合并为原问题的解。

下面是合并的伪代码与图解，其中A代表要排序的数组，p,r代表要排序的起始结束的索引。

clip_image0361_thumb

clip_image0381_thumb

下面我们看下合并排序的伪代码与图解 clip_image0401_thumb

clip_image0421_thumb

为什么归并排序的时间复杂度是clip_image0342_thumb呢？请看下图，每一行合并的复杂度是clip_image0142_thumb，一共有lg(n)行，所以时间复杂度是clip_image0343_thumb

clip_image0461_thumb

2.3快速排序（Quicksort）

快速排序最坏的情况clip_image0068_thumb，但是平均时间复杂度是clip_image0344_thumb，它通常是排序算法比较实用的选择。因为

1平均时间复杂度是clip_image0345_thumb

2原地排序

2.3.1快速排序的描述

快速排序也是基于分治模式（divide and conquer）.思想是通过，每个元素与最后一个元素比较，较小的分在左边一组，较大的分在右边一组，最后一个元素在中间，如此迭代下去，伪代码如下：

clip_image0501_thumb

分割的过程见下图。

clip_image0521_thumbclip_image0541_thumb

2.3.2快速排序的性能

在最坏的情况下，快速排序的时间复杂度为clip_image0069_thumb，如输入是一组有序序列，每次分割比例都很悬殊。即使每次分割的情况是9:1，下时间复杂度仍然为clip_image0346_thumb。如下图：

clip_image0581_thumb

快速排序平均时间复杂度clip_image0347_thumb，并且其中的常数因子较小，并且快速排序时原地排序。所以快速排序算法比较常用。

2.3.3随机快速排序

为了避免每次分割不均匀的情况，可以每次在1~(n-1)中随机抽取一个数字与最后一个数字进行交换，这样就可以避免最坏的情况了。

clip_image0611_thumb

3非比较排序分类介绍

3.1计数排序（Counting sort）

计数排序假设n个输入元素中的每一个都是介于0到k之间的整数（k为整数），若k=O(n),则计数排序的运行时间是O(n).

假设我们需要对A[n]排序，我们需要额外的两个数组B[n]存储输出结果，C[k]，表示A[n]中整数i的个数有C[i]个。伪代码与图示如下：

clip_image0631_thumb

clip_image0651_thumb

计数排序是有前提的，所以它比较快，另外它是稳定的，可以作为基数排序的子函数。总的运算时间是clip_image0671_thumb

3.2基数排序（Radix sort）

基数排序时对位进行排序，如下图，我们先对个位进行排序，再对十位，百味…排序，所以这里就要求每次排序的算法是稳定的。

clip_image0691_thumb

基数排序的算法流程很简单如下，其中d代表有d位数字。

clip_image0711_thumb

第二行，可以利用计数排序来实现。每次计数排序的时间复杂度是clip_image0672_thumb，那么d此循环，所以时间复杂度是clip_image0731_thumb.从公式看来，貌似基数排序比快速排序执行的次数要少，但是基数排序每一遍执行的时间要长得多。到底哪一个好，还要取决于实际的硬件与输入数据，并且基数排序不是原地排序。

// sort algorigthms.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include<iostream>
#include<vector>
#include<assert.h>
#include <math.h>

using namespace std;


#define MaxDouble 65535.0
#define Num 8  //Num代表要排序的数组大小

void Merge(double A[],int p,int q,int r);//q代表分开的地方
void Merge_Sort(double A[],int p,int r);//p,r代表排序的首末位置

void Quick_Sort(double A[],int p,int r);//快速排序算法
int Partition(double A[],int p,int r);//快速排序算法的分割
int Random_Partition(double A[],int p,int r);//随机快速排序算法
void Counting_Sort(int A[],int k);//不稳定的计数排序（自己想的，不稳定）
void Counting_Sort_Stable(int A[],int B[],int k);//稳定的快速排序算法

void Radix_Sort(int A[],int d);//d是最高位
void Counting_Sort_Stable_ForRadixSort(int A[],int B[],int k);//为了基数排序写的计数排序算法
int _tmain(int argc, _TCHAR* argv[])
{

    int A[Num]={121,921,313,120,322,3,1,13};
    int B[Num];
    Radix_Sort(A,9);//基数排序实验
    for(int i=0;i<Num;i++)
        cout<<A[i]<<endl;
    return 0;
}

void Merge_Sort(double A[],int p,int r){ //归并排序法
    
    assert(p>=0);
    assert(r<Num);


    if(p<r){
        int q=floor((p+r)/2.0);
        Merge_Sort(A,p,q);
        Merge_Sort(A,q+1,r);

        Merge(A,p,q,r);
    }

}

void Merge(double A[],int p,int q,int r){ //归并排序的合并部分

    if(p<r){
        int n1=q-p+2;
        int n2=r-q+1;

        double *L1=new double[n1];
        double *L2=new double[n2];

        L1[n1-1]=MaxDouble;//将末尾设置为无穷大，有利于后续算法。
        L2[n2-1]=MaxDouble;

        for(int i=0;i<n1-1;i++)
            L1[i]=A[p+i];

        for(int i=0;i<n2-1;i++)
            L2[i]=A[q+1+i];


        int i=0;
        int    j=0;

        for(int k=p;k<=r;k++){//将L1,L2,有顺序的,从小到大赋值给原有的A
            if(L1[i]<L2[j]){
                A[k]=L1[i];
                i++;
            }
            else{
                A[k]=L2[j];
                j++;
            }
        }



    }
}


void Quick_Sort(double A[],int p,int r){   //最常用的排序算法。平时运算时间  O(n*lgn)
        assert(p>=0);
    assert(r<Num);
    if(p<r){
        int q= Random_Partition(A,p,r);  //用Random_就是随机快速排序法，可以保证接近平均运算时间
        Quick_Sort(A,p,q-1);
        Quick_Sort(A,q+1,r);
    }
}

int  Partition(double A[],int p,int r){

    int i=p-1;
    
    double temp1=A[r];

    for(int j=p;j<r-1;j++){
        if(A[j]<A[r]){
            i++;
            double temp=A[i];
            A[i]=A[j];
            A[j]=temp;
        }
    }

    double temp=A[i+1];
            A[i+1]=A[r];
            A[r]=temp;


    return i+1;
}


int  Random_Partition(double A[],int p,int r){//随机分配，为了防止最坏情况出现，如排序好了，时间需要O(n*n)
    //随机分配，即每次开始，交换A[r],与A[0..r-1（随机找一个）]


    int random=rand()%Num;

    int exc=A[r];
    A[r]=A[random];
    A[random]=exc;


    int i=p-1;
    
    double temp1=A[r];

    for(int j=p;j<=r-1;j++){
        if(A[j]<A[r]){
            i++;
            double temp=A[i];
            A[i]=A[j];
            A[j]=temp;
        }
    }

    double temp=A[i+1];
            A[i+1]=A[r];
            A[r]=temp;


    return i+1;
}


void Counting_Sort(int A[],int k){//计数排序(整数数组），假设n个输入元素的每一个都是介于0到k之间的整数，k为某个整数。
    //当k=O(n)时，运行时间为O(n)
    //提前知道数组A的大小为Num
    

    int *C=new int [k+1];
    
    for(int i=0;i<k+1;i++)
        C[i]=0;


    for(int i=0;i<Num;i++)
        C[A[i]]++;


    int index=0;
    for(int j=0;j<k+1;j++){
        for(int i=0;i<C[j];i++){
            A[index++]=j;
        }
    }



}


void Counting_Sort_Stable(int A[],int B[],int k){//计数排序(整数数组），假设n个输入元素的每一个都是介于0到k之间的整数，k为某个整数。
    //当k=O(n)时，运行时间为O(n)
    //提前知道数组A的大小为Num
    

    int *C=new int [k+1];
    
    for(int i=0;i<k+1;i++)
        C[i]=0;


    for(int i=0;i<Num;i++)
        C[A[i]]++;


    int index=0;


    for(int i=1;i<k+1;i++){
        C[i]=C[i]+C[i-1];
    }

    for(int j=Num-1;j>=0;j--){

        B[ C[A[j]]-1 ]=A[j]; //因为数组从0开始。
        C[A[j]]--;
    }

}

void Radix_Sort(int A[],int d){

    int *B=new int [Num];
    for(int bit=1;bit<=d;bit++){
        for(int i=0;i<Num;i++){
            B[i]=(A[i]/(int)pow(10.0,bit-1))%10;
        }
         Counting_Sort_Stable_ForRadixSort(B,A,9);
    }


}



void Counting_Sort_Stable_ForRadixSort(int A[],int B[],int k){//B代表要排序的数字，A代表B中数字的某一位
    //当k=O(n)时，运行时间为O(n)
    //提前知道数组A的大小为Num
    

    int *C=new int [k+1];

    int *B_temp=new int [Num];
    for(int i=0;i<Num;i++)
        B_temp[i]=B[i];

    
    for(int i=0;i<k+1;i++)
        C[i]=0;


    for(int i=0;i<Num;i++)
        C[A[i]]++;


    int index=0;


    for(int i=1;i<k+1;i++){
        C[i]=C[i]+C[i-1];
    }

    for(int j=Num-1;j>=0;j--){

        B[ C[A[j]]-1 ]=A[j]; //因为数组从0开始。
        B[ C[A[j]]-1]=B_temp[j];
        C[A[j]]--;
    }

}

参考文献：

1算法导论（To Be frankly,大部分总结自此书，只是把自己的总结与大家分享）

2维基百科（上面关于排序算法写得很详细，如http://zh.wikipedia.org/wiki/%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F

3算法稳定性参考链接：http://blog.csdn.net/johnny710vip/article/details/6895654

本人水平有限，怀着分享学习的态度发表此文，欢迎大家批评，交流。感谢您的阅读。
欢迎转载本文，转载时请附上本文地址：http://www.cnblogs.com/Dzhouqi/p/3379640.html
另外：欢迎访问我的博客 http://www.cnblogs.com/Dzhouqi/

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/Dzhouqi/p/3379640.html