排序算法总结

发表于 | 分类于
各种排序算法分析与实现

说明：代码使用codeblocks编译，C++实现，个人编写，如有错误，还望指正。

fengjingtu

总结

排序方法 稳定性 平均时间复杂度 最优时间复杂度 最坏时间复杂度 空间复杂度
插入排序 稳定 O($$n^{2}$$) O（$$n$$） O（$$n^{2}$$） 1
冒泡排序 稳定 O（$$n^{2}$$) O（$$n^{2}$$） O（$$n^{2}$$） 1
二路归并排序 稳定 O($$nlog$$)
二叉树排序 稳定 O($$nlogn$$)
计数排序 稳定 O（$$n+k$$)
桶排序 不稳定 O（n）
选择排序 不稳定 O（$$n^{2}$$） O（$$n^{2}$$） O（$$n^{2}$$） 1
堆排序 不稳定 O（$$nlogn$$） O（$$nlogn$$） O（$$nlogn$$） 1
希尔排序 不稳定 O（$$nlogn$$）
基数排序 不稳定 O（$$n+k$$）
快速排序 不稳定 O（$$nlogn$$） O（$$nlogn$$） O（$$n^{2}$$） O（$$nlogn$$）

插入排序

插入排序把序列分为两个部分，一部分有序，一部分无序。每一次循环都把无序的第一个元素插入到有序的序列中。

以序列 {4，2，1，3，5}为例。

当一个序列中只有一个元素的时候，我们认为这个序列有序。所以最开始的时候，有序和无序序列如下：

{4|， 2，1，3，5}

接下来取无序中的第一个元素，和有序元素中的最后一个元素，也就是最大的元素比较，如果大于，则不需要移动，去下一个无序元素即可，如果小于，则一直交换到合适的位置。

取2和4比较，小于，则和4交换位置{2，4|，1，3，5}，发现到达有序的第一个位置，则停止。

然后取1，和4比较，小于则交换{2，1，4|，3，5}，继续和2比较交换{1，2，4|，3，5}至此1的位置也找到了。

接下来元素3，需要和4比较交换{1，2，3，4|，5}，继续和2比较不交换，结束。

元素5 和4比较不交换，结束。

整个过程可以在原序列上直接操作，只需要一个临时的变量用于交换。所以空间复杂度认为是O(1);

时间上，如果本来是有序的队列，每个元素只需要和自己前一位的元素比较一次就可以完成排序，这个是最优时间复杂度：O(n)，相反，如果这个一个倒序的序列，第n元素都需要和n-1个元素比较，这个时候是最坏时间复杂度：O(n2)。平均时间复杂度是O(n2);

插入排序是稳定的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void insert_sort(int array[],int len)
{
    int v=0;
    int j=0;
    for(int i=1;i<len;i++)
    {
        v=array[i];
        for(j=i-1;j>=0;j--)
        {
            if(array[j]>v)
                array[j+1]=array[j];
            else
                break;
        }
        array[j+1]=v;
    }
}

冒泡排序

冒泡排序总是比较和交换相邻的两个元素。再一次循环中，获得到一个最大的值，把他交换到序列的最后，然后再剩下的序列中同样找到一个最大的数。

以序列 {4，2，1，3，5}为例。

寻找最大的数字，比较交换，放到最后：4和2比较交换。

{2， 4，1，3，5}

4和1比较交换：{2， 1，4，3，5}

4和3比较交换：{2， 1，3，4，5}

4和5比较不交换{2， 1，3，4，5}，这一轮循环下来，得到了最大的值5：{2， 1，3，4，|5}

第二轮以同样的方式：2和1比较交换，2和3比较不交换，3和4比较不交换，得到{1， 2，3，|4，5}

在经过两轮的比较就完成了排序。

整个过程可以在原序列上直接操作，只需要一个临时的变量用于交换。所以空间复杂度认为是O(1);

时间上，不管序列是否有序，我们都需要进行比较，一共需要比较（n-1）轮，每轮比较的次数是n的线性表达式。我们认为最优。最坏。平均的时间复杂度都是O(n2)。

冒泡排序是稳定的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void insert_sort(int array[],int len)
{
    int v=0;
    int j=0;
    for(int i=1;i<len;i++)
    {
        v=array[i];
        for(j=i-1;j>=0;j--)
        {
            if(array[j]>v)
                array[j+1]=array[j];
            else
                break;
        }
        array[j+1]=v;
    }
}

选择排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void insert_sort(int array[],int len)
{
    int v=0;
    int j=0;
    for(int i=1;i<len;i++)
    {
        v=array[i];
        for(j=i-1;j>=0;j--)
        {
            if(array[j]>v)
                array[j+1]=array[j];
            else
                break;
        }
        array[j+1]=v;
    }
}

快速排序

快速排序采用分治法，把一个串，按照一个基准值分为左右两部分，将以同样的方式排序左右两部分，每一次调用的结果固定了基准值的最终位置。：在下面的代码中，基准值选择串尾的数，基准值左面都比它小，右面都比它大

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
int Partition(int array[],int len,int start,int end)
{
    if(array== NULL || len<=0 || start<0 || end>=len)
        return -1;
    int val=array[end];
    int devide=start;
    int tmp;
    for(int i=start;i<=end;i++)
    {
        if(array[i]<val)
        {
            tmp=array[devide];
            array[devide]=array[i];
            array[i]=tmp;
            devide++;
        }
    }
    tmp=array[devide];
    array[devide]=array[end];
    array[end]=tmp;
    return devide;
}
void quick_sort(int array[],int len,int start,int end)
{
    if(start==end)
        return ;
    int index=Partition(array,len,start,end);
    if(index > start)
        quick_sort(array,len,start,index-1);
    if(index < end)
        quick_sort(array,len,index+1,end);
}

堆排序

1、建最大堆。

2、把堆顶元素放在末尾。

3、把这个堆的最后一个元素删除，重新调整这个堆。

4、重复2、3；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
void max_heap_adjust(int array[],int len,int i)
{
    int tmp=0;
    int left=2*i+1;
    int right=2*i+2;
    int m=0;
    if(left<=len)
    {
        m=left;
    }
    if(right<=len&&array[right]>array[m])
    {
        m=right;
    }
    if(m>i&&array[m]>array[i])
    {
        tmp=array[m];
        array[m]=array[i];
        array[i]=tmp;
        max_heap_adjust(array,len,m);
    }
}

void build_maxheap(int array[],int len)
{
//从最后一个有孩子的节点下标开始

    int last_father=len/2;
    for(int i=last_father;i>=0;i--)
    {
        max_heap_adjust(array,len,i);
    }
    return;
}

void heap_sort(int array[],int len)
{
    if(array==NULL || len<=0)
        return ;
        build_maxheap(array,len-1);
    int tmp;
    for(int i=len-1;i>0;i--)
    {
        tmp=array[0];
        array[0]=array[i];
        array[i]=tmp;
        max_heap_adjust(array,i-1,0);
    }

    return ;
}