常见的排序算法总结

一、冒泡排序：

最坏运行时间：O(n^2)

最佳运行时间：O(n^2)

不多说，直接上代码：

int bubble_sort(int *arr,int n)
{
int i,j,temp;

    if(n<2) return -1;
    for(i=0; i<n-1; i++)
    {
        for(j=i+1; j<n; j++)
        {
            if(arr[i]>arr[j])
            {
                temp=arr[i];
                arr[i]=arr[j];
                arr[j]=temp;
            }
        }
    }

return 0;
}

二、直接插入排序

最优复杂度：当输入数组就是排好序的时候，复杂度为O(n)，而快速排序在这种情况下会产生O(n^2)的复杂度。

最差复杂度：当输入数组为倒序时，复杂度为O(n^2)

插入排序比较适合用于“少量元素的数组”。

插入排序就是每一步都将一个待排数据按其大小插入到已经排序的数据中的适当位置，直到全部插入完毕。

代码：

int insert_sort(int *arr,int n)
{
int i,j,k,temp;

    if(n<2) return -1;
    for(i=1; i<n; i++)
    {
        temp=arr[i];
        for(j=0; j<i; j++)
        {
            if(temp<arr[j])
            {
                for(k=i-1; k>=j; k–)
                {
                    arr[k+1]=arr[k];
                }
                arr[j]=temp;
                break;
            }
        }
    }

return 0;
}

三、选择排序

先来看看选择排序的思想。选择排序的思想非常直接，不是要排序么？那好，我就从所有序列中先找到最小的，然后放到第一个位置。之后再看剩余元素中最小的，放到第二个位置……以此类推，就可以完成整个的排序工作了。

最好情况时间：O(n^2)。

最坏情况时间：O(n^2)。

代码：

int selection_sort(int *arr,int n)
{
int i,j,k,temp;

    if(n<2) return -1;
    for(i=0;i<n-1;i++)
    {
        temp=arr[i];
        for(j=k=i;j<n;j++)
        {
            if(temp>arr[j])
            {
                temp=arr[j];
                k=j;
            }
        }
        temp=arr[i];
        arr[i]=arr[k];
        arr[k]=temp;
    }

return 0;
}

四、归并排序

首先考虑下如何将将二个有序数列合并。这个非常简单，只要从比较二个数列的第一个数，谁小就先取谁，取了后就在对应数列中删除这个数。然后再进行比较，如果有数列为空，那直接将另一个数列的数据依次取出即可。

思想：运用分治法思想解决排序问题。

最坏情况运行时间：O(nlgn)

最佳运行时间：O(nlgn)

问：归并排序的缺点是什么？

答：他是Out-place sort，因此相比快排，需要很多额外的空间。

问：为什么归并排序比快速排序慢？

答：虽然渐近复杂度一样，但是归并排序的系数比快排大。

问：对于归并排序有什么改进？

答：就是在数组长度为k时，用插入排序，因为插入排序适合对小数组排序。在算法导论思考题2-1中介绍了。复杂度为O(nk+nlg(n/k)) ，当k=O(lgn)时，复杂度为O(nlgn)

代码：

/*
arr:原数组
tempArr:临时数组
bIndex:第一个排序序列的起始索引
mIndex:第一个排序序列的结束索引和第二个排序序列的起始索引
eIndex:第二个排序序列的结束索引
*/
int merge(int *arr,int *tempArr,int bIndex,int mIndex,int eIndex)
{
int i,j,k;

    for(i=0,j=bIndex,k=mIndex; j<mIndex && k<eIndex;)
    {
        if(arr[j]<arr[k])
            tempArr[i++]=arr[j++];
        else
            tempArr[i++]=arr[k++];
    }
    if(j<mIndex)
    {
        while(j<mIndex)
            tempArr[i++]=arr[j++];
    }
    else if(k<eIndex)
    {
        while(k<eIndex)
            tempArr[i++]=arr[k++];
    }

for(i=0; i<eIndex-bIndex; i++)
arr[bIndex+i]=tempArr[i];

return 0;
}

int merge_sort(int *arr,int n)
{
    int *pTempArray=NULL;
    int length;     //有序子序列长度
    int i;

    if(n<2) return -1;
    pTempArray=(int *)malloc(sizeof(int)*n);
    if(pTempArray==NULL) return -2;

    for(length=1; length<n; length*=2)
    {
        for(i=0; i+length*2<=n; i+=length*2)
        {
            merge(arr,pTempArray,i,i+length,i+length*2);
        }
    }
    if(length/2<n)
        merge(arr,pTempArray,0,length/2,n);

free(pTempArray);

return 0;
}

五、快速排序

快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略，通常称其为分治法(Divide-and-ConquerMethod)。

该方法的基本思想是：

1．先从数列中取出一个数作为基准数。

2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。

3．再对左右区间重复第二步，直到各区间只有一个数。

虽然快速排序称为分治法，但分治法这三个字显然无法很好的概括快速排序的全部步骤。因此我的对快速排序作了进一步的说明：挖坑填数+分治法：

先来看实例吧，定义下面再给出（最好能用自己的话来总结定义，这样对实现代码会有帮助）。

以一个数组作为示例，取区间第一个数为基准数。

0	1	2	3	4	5	6	7	8	9
72	6	57	88	60	42	83	73	48	85

初始时，i = 0; j = 9; X = a[i] = 72

由于已经将a[0]中的数保存到X中，可以理解成在数组a[0]上挖了个坑，可以将其它数据填充到这来。

从j开始向前找一个比X小或等于X的数。当j=8，符合条件，将a[8]挖出再填到上一个坑a[0]中。a[0]=a[8]; i++; 这样一个坑a[0]就被搞定了，但又形成了一个新坑a[8]，这怎么办了？简单，再找数字来填a[8]这个坑。这次从i开始向后找一个大于X的数，当i=3，符合条件，将a[3]挖出再填到上一个坑中a[8]=a[3]; j–;

数组变为：

0	1	2	3	4	5	6	7	8	9
48	6	57	88	60	42	83	73	88	85

i = 3; j = 7; X=72

再重复上面的步骤，先从后向前找，再从前向后找。

从j开始向前找，当j=5，符合条件，将a[5]挖出填到上一个坑中，a[3] = a[5]; i++;

从i开始向后找，当i=5时，由于i==j退出。

此时，i = j = 5，而a[5]刚好又是上次挖的坑，因此将X填入a[5]。

数组变为：

0	1	2	3	4	5	6	7	8	9
48	6	57	42	60	72	83	73	88	85

可以看出a[5]前面的数字都小于它，a[5]后面的数字都大于它。因此再对a[0…4]和a[6…9]这二个子区间重复上述步骤就可以了。

对挖坑填数进行总结

1．i =L; j = R; 将基准数挖出形成第一个坑a[i]。

2．j–由后向前找比它小的数，找到后挖出此数填前一个坑a[i]中。

3．i++由前向后找比它大的数，找到后也挖出此数填到前一个坑a[j]中。

4．再重复执行2，3二步，直到i==j，将基准数填入a[i]中。

最坏运行时间：当输入数组已排序时，时间为O(n^2)，当然可以通过随机化来改进（shuffle array 或者 randomized select pivot）,使得期望运行时间为O(nlgn)。

最佳运行时间：O(nlgn)

代码：

int quick_sort(int *arr[],int n)
{
int i,j,mid;

    if(n<2) return -1;
    mid=arr[0];
    for(i=0,j=n-1;i<j;j–)
    {
        if(arr[j]<mid)
        {
            arr[i]=arr[j];
            for(i++;i<j;i++)
            {
                if(arr[i]>mid)
                {
                    arr[j]=arr[i];
                    break;
                }
            }
        }
        if(i==j) break;
    }
    arr[i]=mid;
    quick_sort(arr,i);
    quick_sort(&arr[i+1],len-i-1);

return 0;
}

六、堆排序

堆排序是一种选择排序，其时间复杂度为O(nlogn)。

堆的定义

　　n个元素的序列{k₁，k₂，…,k_n}当且仅当满足下列关系之一时，称之为堆。

　　情形1：k_i<= k_2i且k_i<= k_2i+1（最小化堆或小顶堆）

　　情形2：k_i>= k_2i且k_i>= k_2i+1 （最大化堆或大顶堆）

　　其中i=1,2,…,n/2向下取整;

　　若将和此序列对应的一维数组（即以一维数组作此序列的存储结构）看成是一个完全二叉树，则堆的含义表明，完全二叉树中所有非终端结点的值均不大于（或不小于）其左、右孩子结点的值。

　　由此，若序列{k₁，k₂，…,k_n}是堆，则堆顶元素（或完全二叉树的根）必为序列中n个元素的最小值（或最大值）。

　　例如，下列两个序列为堆，对应的完全二叉树如图：

　　若在输出堆顶的最小值之后，使得剩余n-1个元素的序列重又建成一个堆，则得到n个元素的次小值。如此反复执行，便能得到一个有序序列，这个过程称之为堆排序。

　　堆排序（Heap Sort）只需要一个记录元素大小的辅助空间（供交换用），每个待排序的记录仅占有一个存储空间。

堆的存储

　　一般用数组来表示堆，若根结点存在序号0处， i结点的父结点下标就为(i-1)/2。i结点的左右子结点下标分别为2*i+1和2*i+2。

　　（注：如果根结点是从1开始，则左右孩子结点分别是2i和2i+1。）

　　如第0个结点左右子结点下标分别为1和2。

　　如最大化堆如下：

　　左图为其存储结构，右图为其逻辑结构。

堆排序的实现

　　实现堆排序需要解决两个问题：

　　　　1.如何由一个无序序列建成一个堆？

　　　　2.如何在输出堆顶元素之后，调整剩余元素成为一个新的堆？

　　先考虑第二个问题，一般在输出堆顶元素之后，视为将这个元素排除，然后用表中最后一个元素填补它的位置，自上向下进行调整：首先将堆顶元素和它的左右子树的根结点进行比较，把最小的元素交换到堆顶；然后顺着被破坏的路径一路调整下去，直至叶子结点，就得到新的堆。

　　我们称这个自堆顶至叶子的调整过程为“筛选”。

　　从无序序列建立堆的过程就是一个反复“筛选”的过程。

构造初始堆

　　初始化堆的时候是对所有的非叶子结点进行筛选。

　　最后一个非终端元素的下标是[n/2]向下取整，所以筛选只需要从第[n/2]向下取整个元素开始，从后往前进行调整。

　　比如，给定一个数组，首先根据该数组元素构造一个完全二叉树。

　　然后从最后一个非叶子结点开始，每次都是从父结点、左孩子、右孩子中进行比较交换，交换可能会引起孩子结点不满足堆的性质，所以每次交换之后需要重新对被交换的孩子结点进行调整。

进行堆排序

　　有了初始堆之后就可以进行排序了。

　　堆排序是一种选择排序。建立的初始堆为初始的无序区。

　　排序开始，首先输出堆顶元素（因为它是最值），将堆顶元素和最后一个元素交换，这样，第n个位置（即最后一个位置）作为有序区，前n-1个位置仍是无序区，对无序区进行调整，得到堆之后，再交换堆顶和最后一个元素，这样有序区长度变为2。。。

　　不断进行此操作，将剩下的元素重新调整为堆，然后输出堆顶元素到有序区。每次交换都导致无序区-1，有序区+1。不断重复此过程直到有序区长度增长为n-1，排序完成。

堆排序实例

　　首先，建立初始的堆结构如图：

　　然后，交换堆顶的元素和最后一个元素，此时最后一个位置作为有序区（有序区显示为黄色），然后进行其他无序区的堆调整，重新得到大顶堆后，交换堆顶和倒数第二个元素的位置……

　　重复此过程：

　　最后，有序区扩展完成即排序完成：

　　由排序过程可见，若想得到升序，则建立大顶堆，若想得到降序，则建立小顶堆。

代码：

int heap_adjust(int *arr,int rootIndex,int endIndex)
{
    //建立大根堆
    int childIndex;
    int temp;

    for(childIndex=rootIndex*2+1;childIndex<=endIndex;rootIndex=childIndex,childIndex=rootIndex*2+1)
    {
        if(childIndex<endIndex && arr[childIndex]<arr[childIndex+1])
            childIndex++;
        if(arr[rootIndex]<arr[childIndex])
        {
            temp=arr[rootIndex];
            arr[rootIndex]=arr[childIndex];
            arr[childIndex]=temp;
        }

else

break;
}

return 0;
}

int heap_sort(int *arr,int n)
{
int i;
int temp;

    for(i=n/2;i>=0;i–)
    {
        heap_adjust(arr,i,n-1);
    }
    print_array(arr,n);

    for(i=n-1;i>=0;i–)
    {
        temp=arr[0];
        arr[0]=arr[i];
        arr[i]=temp;
        heap_adjust(arr,0,i-1);
    }

return 0;
}

各排序算法简要比较

名称	数据对象	稳定性	时间复杂度		空间复杂度	描述
名称	数据对象	稳定性	平均	最坏	空间复杂度	描述
插入排序	数组、链表	√	O(n²)		O(1)	(有序区,无序区)。把无序区的第一个元素插入到有序区的合适的位置。对数组：比较得少，换得多。
直接选择排序	数组	×	O(n²)		O(1)	(有序区,无序区)。在无序区里找一个最小的元素跟在有序区的后面。对数组：比较得多，换得少。
直接选择排序	链表	√	O(n²)		O(1)	(有序区,无序区)。在无序区里找一个最小的元素跟在有序区的后面。对数组：比较得多，换得少。
堆排序	数组	×	O(nlogn)		O(1)	(最大堆,有序区)。从堆顶把根卸出来放在有序区之前，再恢复堆。
归并排序	数组、链表	√	O(nlogn)		O(n) +O(logn) ，如果不是从下到上	把数据分为两段，从两段中逐个选最小的元素移入新数据段的末尾。可从上到下或从下到上进行。
快速排序	数组	×	O(nlogn)	O(n²)	O(logn) ,O(n)	(小数,枢纽元,大数)。
Accum qsort	链表	√	O(nlogn)	O(n²)	O(logn) ,O(n)	(无序区,有序区)。把无序区分为(小数,枢纽元,大数)，从后到前压入有序区。
决策树排序	√	O(logn!)		O(n!)	O(n) <O(logn!) <O(nlogn)
计数排序	数组、链表	√	O(n)		O(n+m)	统计小于等于该元素值的元素的个数 i，于是该元素就放在目标数组的索引 i位。(i≥0)
桶排序	数组、链表	√	O(n)		O(m)	将值为 i 的元素放入i 号桶，最后依次把桶里的元素倒出来。
基数排序	数组、链表	√	一种多关键字的排序算法，可用桶排序实现。

均按从小到大排列

n 代表数据规模

m 代表数据的最大值减最小值

打赏

堆的存储

堆排序的实现

构造初始堆

进行堆排序

堆排序实例

Inline Hook

[转]常用排序算法稳定性分析

You may also like

Leave a Comment Cancel Reply