常见排序算法

[TOC]

整理:选择、Shell、堆、快速排序是不稳定的;直接插入、冒泡、归并排序、桶排序、基数排序是稳定的。

冒泡排序

在要排序的一组数中,对当前还未排好序的范围内的全部数,自上而下对相邻的两个数依次进行比较和调整,让较大的数往下沉,较小的往上冒。即:每当两相邻的数比较后发现它们的排序与排序要求相反时,就将它们互换。

下面是一种改进的冒泡算法,它记录了每一遍扫描后最后下沉数的位置k,这样可以减少外层循环扫描的次数。

冒泡排序是稳定的。时间复杂度O(n^2)。

void bubble_sort(int *x, int n)
{
    int last;

    for (int i = n-1; i > 0; i = last) {     /* 循环到没有比较范围 */
        for (int j = 0, k = 0; j < i; ++j) { /* 每次预置k=0,循环扫描后更新k */
            if (x[j] > x[j+1]) {             /* 大的放在后面,小的放到前面 */
                swap(x[j], x[j+1]);
                last = j;                    /* 保存最后下沉的位置。这样k后面的都是排序排好了的。*/
            }
        }
    }
}

选择排序

在要排序的一组数中,选出最小的一个数与第一个位置的数交换;然后在剩下的数当中再找最小的与第二个位置的数交换,如此循环到倒数第二个数和最后一个数比较为止。

选择排序是不稳定的。时间复杂度O(n^2)。

void select_sort(int *x, int n)
{
    int min;

    for (int i = 0; i < n-1; ++i) {    /* 要选择的次数:0~n-2共n-1次 */
        min = i;                       /* 假设当前下标为i的数最小,比较后再调整 */
        for (int j= i+1; j < n; ++j) { /* 循环找出最小的数的下标是哪个 */
            if (x[j] < x[min]) {
                min = j;               /* 如果后面的数比前面的小,则记下它的下标 */
            }
        }

        if (min != i) {                /* 如果min在循环中改变了,就需要交换数据 */
            swap(x[i], x[min]);
        }
    }
}

直接插入排序

在要排序的一组数中,假设前面(n-1) [n>=2] 个数已经是排好顺序的,现在要把第n个数插到前面的有序数中,使得这n个数也是排好顺序的。如此反复循环,直到全部排好顺序。

直接插入排序是稳定的。时间复杂度O(n^2)。

void insert_sort(int *x, int n)
{
    int tmp;

    for (int i = 1; i < n; ++i) {  /*要选择的次数:1~n-1共n-1次*/
        /* 暂存下标为i的数。注意:下标从1开始,原因就是开始时第一个数即下
         * 标为0的数,前面没有任何数,单单一个,认为它是排好顺序的。*/
        tmp = x[i];
        /* 注意:j=i-1,j--,这里就是下标为i的数,在它前面有序列中找插入位置。*/
        for (int j = i-1; j >= 0 && t < x[j]; --j) {
            /* 如果满足条件就往后挪。最坏的情况就是t比下标为0的数都小,它
             * 要放在最前面,j==-1,退出循环*/
            x[j+1] = x[j];
        }
        x[j+1] = tmp;              /* 找到下标为i的数的放置位置*/
    }
}

shell排序

Shell排序是直接插入排序的改良算法。

在直接插入排序算法中,每次插入一个数,使有序序列只增加1个节点, 并且对插入下一个数没有提供任何帮助。如果比较相隔较远距离(称为增量)的数,使得数移动时能跨过多个元素,则进行一次比较就可能消除多个元素交换。D.L.shell于1959年在以他名字命名的排序算法中实现了这一思想。算法先将要排序的一组数按某个增量d分成若干组,每组中记录的下标相差d.对每组中全部元素进行排序,然后再用一个较小的增量对它进行,在每组中再进行排序。当增量减到1时,整个要排序的数被分成一组,排序完成。

下面的函数是一个Shell排序算法的一个实现,初次取序列的一半为增量,以后每次减半,直到增量为1。

Shell排序是不稳定的。

void shell_sort(int *x, int n)
{
    int tmp;

    for (int i = n/2; i > 0; i = i/2) { /* 控制增量 */
        for (int j = i; j < n; ++j) {   /* 这个实际上就是上面的直接插入排序 */
            tmp = x[j];
            for (int k = j-i; k >= 0 && tmp < x[k]; k-=i) {
                x[k+i] = x[k];
            }
            x[k+i] = tmp;
        }
    }
}

两路归并排序

递归关系:一个大的数列需要排序,把它从中间分成两部分,每一部分归并排序,然后把排好序的这两个部分再合并起来(合并的时候要按顺序合并)。如果分成的这部分只有一个数,那么这个部分就不用再排序(看做已经排好序的)。

归并排序的关键在于merge函数,两路归并相对简单,需要注意边界处理。1

归并排序是稳定的。时间复杂度是O(nlogn),空间复杂度O(n)。

void merge(int a[], int b[], int left, int mid, int right)
{
    int left_end = mid-1,
        n = right - left + 1,
        k = left;
    while ((left <= left_end) && (mid <= right)) {
        if (a[left] <= a[mid]) b[k++] = a[left++];
        else b[k++] = a[mid++];
    }
    while (left <= left_end) b[k++] = a[left++];
    while (mid <= right)     b[k++] = a[mid++];
    // copy back to a[]
    while(n-- > 0){
        a[right] = b[right];
        --right;
    }
}

void merge_sort(int a[], int b[], int left, int right)
{
    int mid;
    if (left < right) {
        mid = (right + left) / 2;
        merge_sort(a, b, left, mid);
        merge_sort(a, b, mid+1, right);
        merge(a, b, left, mid+1, right);
    }
}

void m_sort(int a[], int array_size)
{
    int *b = (int*)malloc(array_size);
    merge_sort(a, b, 0, array_size - 1);
    free(b);
}

快速排序

快速排序是对冒泡排序的一种本质改进。它的基本思想是通过一趟扫描后,使得排序序列的长度能大幅度地减少。在冒泡排序中,一次扫描只能确保最大数值的数移到正确位置,而待排序序列的长度可能只减少1。快速排序通过一趟扫描,就能确保某个数(以它为基准点)的左边各数都比它小,右边各数都比它大。然后又用同样的方法处理它左右两边的数,直到基准点的左右只有一个元素为止。它是由C.A.R.Hoare于1962年提出的。

显然快速排序可以用递归实现,当然也可以用栈化解递归实现。

快速排序是不稳定的。时间复杂度O(nlogn),非递减序列会导致O(n^2)。2

快排的主要思想:

  • 选择一个基准点(比如最左边的值)
  • 使用基准点分割待排序数组,使得左边的值都小于基准点,右边的值都大于或等于基准点
  • 对左边和右边的新数组,分别递归这个分割任务

快排的递归实现:

void quick_sort(int* a, int low, int high)
{
    int pivot;
    if(low < high){
        pivot = partition(a, low, high);
        quick_sort(a, low, pivot-1);
        quick_sort(a, pivot+1, high);
    }
}

其中,关键在于 partition 算法,其一是如何选取pivot,其二是如何交换数组元素。

partition 方法1: 两边同时扫描

从数组两边同时扫描:从右边扫描,当遇到比pivot小的元素,则交换到最左边;然后,从左边扫描,遇到比pivot大的元素,则交换到最右边。

int partition(int *x, int low, int high)
{
    int l = low;
    int r = high;
    int pivot = *(x+low);       /* 暂存pivot */

    /* 从两边同时扫描 */
    while (l<r) {
        /* 从右边扫描,只要比pivot大仍放在右边 */
        while (l<r && x[r]>pivot) --r;

        /* 上面的循环退出,即出现比pivot小的数 */
        if (l<r) {
            x[l] = x[r];        /* 把右边的小点挪到左边 */
            ++l;                /* 右移,跳过已知的小点 */
        }

        /* 从左边扫描,只要小于等于pivot仍放在左边 */
        while (l<r && x[l]<=pivot) ++l;

        /* 上面的循环退出,即出现比pivot大的数 */
        if (l<r) {
            x[r] = x[l];        /* 把左边的大点挪到右边 */
            --r;                /* 左移,跳过已知的大点 */
        }
    }

    /* 扫描结束后,把pivot放到适当位置 */
    x[l] = pivot;

    return l;
}

partition 方法2: 快慢双指针

使用两颗指针从左向右遍历,一慢一快。慢指针用于维护已经判断过比pivot小的那些元素,指向它们的末尾;快指针用于遍历数组,当遇到比pivot小的元素时候,交换到慢指针维护的数组里,同时慢指针增1。

int partition(int* a, int low, int high)
{
    int pivot, pos;
    pos = low;
    pivot = a[pos];                 /* 使用左边界作为pivot */
    for(int i=low+1; i<=high; ++i){ /* 快指针i遍历数组 */
        if(a[i] < pivot){
            ++ pos;                 /* 慢指针pos维护分割点 */
            /* 把小于pivot的值交换到左边,由pos分割 */
            if(pos != i) swap(a[pos], a[i]);
        }
    }
    swap(a[low], a[pos]);
    return pos;                     /* 返回pivot新下标 */
}

【注意】这里使用左边界作为pivot,快指针是从low+1开始遍历,最终需要把左边界的pivot交换到合适的位置去。

堆排序

堆排序是一种树形选择排序,是对直接选择排序的有效改进。

堆的定义如下:

具有n个元素的序列 h1,h2,…,hn,当且仅当满足 h(i)>=h(2i),h(i)>=h(2i+1) 或 h(i)<=h(2i),h(i)<=h(2i+1) 时称之为堆,其中 i=1,…,n/2。

在这里只讨论满足前者条件的堆,即最大堆。

由堆的定义可以看出,堆顶元素(即第一个元素)必为最大项。完全二叉树可以很直观地表示堆的结构。堆顶为根,其它为左子树、右子树。

初始时把要排序的数的序列看作是一棵顺序存储的二叉树,调整它们的存储顺序,使之成为一个堆,这时堆的根节点的数最大。然后将根节点与堆的最后一个节点交换。然后对前面(n-1)个数重新调整使之成为堆。依此类推,直到只有两个节点的堆,并对它们作交换,最后得到有n个节点的有序序列。

从算法描述来看,堆排序需要两个过程,一是建立堆,二是堆顶与堆的最后一个元素交换位置。所以堆排序有两个函数组成。一是建堆的渗透函数,二是反复调用渗透函数实现排序的函数。

堆排序是不稳定排序。时间复杂度O(nlogn)。

/*
 * 功能:渗透建堆
 * 输入:数组名称(也就是数组首地址)、参与建堆元素的个数、从第几个元素开始
 */
void shift(int *x, int n, int pos)
{
    int tmp, right;

    tmp = x[pos];               /* 暂存开始元素 */
    right = 2*pos + 1;          /* 右子树元素下标 */

    while (right<n) {
        /* 判断是否满足堆的条件:满足就继续下一轮比较,否则调整。 */
        if (right<n-1 && x[right] < x[right+1]) ++right;

        if (tmp < x[right]) {   /* 调整 */
            x[pos] = x[right];
            pos = right;        /* 调整后,开始元素也随之调整 */
            right = 2*pos + 1;
        } else {                /* 没有需要调整了,已经是个堆了,退出循环。*/
            break;
        }
    }

    x[pos] = tmp;               /*开始元素放到它正确位置*/
}
/*
 * 功能:堆排序
 * 输入:数组名称(也就是数组首地址)、数组中元素个数
 */
void heap_sort(int *x, int n)
{
    for (int i=n/2-1; i>=0; --i) {
        shift(x,n,i);           /* 初始建堆 */
    }

    for (int j=n-1; j>=1; --j) {
        swap(x[0], x[j]);
        shift(x,j,0);           /* 剩下的数再建堆 */
    }
}

桶排序

假设有一组长度为N的待排关键字序列K[1….n]。首先,将这个序列划分成M个的子区间(桶) ;然后,基于某种映射函数 ,将待排序列的关键字k映射到第i个桶中(即桶数组B的下标 i) ,那么该关键字k就作为B[i]中的元素(每个桶B[i]都是一组大小为N/M的序列);接着,对每个桶B[i]中的所有元素进行比较排序(可以使用快排);最后,依次枚举输出B[0]….B[M]中的全部内容即是一个有序序列。

例如:待排序列K= {49、 38 、 35、 97 、 76、 73 、 27、 49 }。这些数据全部在1-100之间。因此我们定制10个桶,然后确定映射函数f(k)=k/10。则第一个关键字49将定位到第4个桶中(49/10=4)。依次将所有关键字全部堆入桶中,并在每个非空的桶中进行快速排序。甚至,我们可以定制100个桶,那么一遍扫描后直接就能得到有序序列。

桶排序性能分析

桶排序利用函数的映射关系,减少了几乎所有的比较工作。实际上,桶排序的f(k)值的计算,其作用就相当于快排中的划分,已经把大量数据分割成了基本有序的数据块(桶)。然后只需要对桶中的少量数据做先进的比较排序即可。

对N个关键字进行桶排序的时间复杂度分为两个部分:

  1. 循环计算每个关键字的桶映射函数,这个时间复杂度是O(N)。
  2. 利用先进的比较排序算法对每个桶内的所有数据进行排序,其时间复杂度为 ∑ O(Ni*logNi) 。其中Ni 为第i个桶的数据量。

很显然,第(2)部分是桶排序性能好坏的决定因素。尽量减少桶内数据的数量是提高效率的唯一办法(因为基于比较排序的最好平均时间复杂度只能达到O(N*logN)了)。因此,我们需要尽量做到下面两点:

  1. 映射函数f(k)能够将N个数据平均的分配到M个桶中,这样每个桶就有[N/M]个数据量。
  2. 尽量的增大桶的数量。极限情况下每个桶只能得到一个数据,这样就完全避开了桶内数据的“比较”排序操作。 当然,做到这一点很不容易,数据量巨大的情况下,f(k)函数会使得桶集合的数量巨大,空间浪费严重。这就是一个时间代价和空间代价的权衡问题了。

对于N个待排数据,M个桶,平均每个桶[N/M]个数据的桶排序平均时间复杂度为:

O(N)+O(M*(N/M)*log(N/M))=O(N+N*(logN-logM))=O(N+N*logN-N*logM)

当N=M时,即极限情况下每个桶只有一个数据时。桶排序的最好效率能够达到O(N)。

总结: 桶排序的平均时间复杂度为线性的O(N+C),其中C=N*(logN-logM)。如果相对于同样的N,桶数量M越大,其效率越高,最好的时间复杂度达到O(N)。 当然桶排序的空间复杂度 为O(N+M),如果输入数据非常庞大,而桶的数量也非常多,则空间代价无疑是昂贵的。此外,桶排序是稳定的。

此外,在查找算法中,基于比较的查找算法最好的时间复杂度也是O(logN)。比如,折半查找、平衡二叉树、红黑树等。但是Hash表却有O(C)线性级别的查找效率(不冲突情况下查找效率达到O(1))。可以说,Hash表的思想和桶排序有异曲同工之妙!

基数排序

基数排序是桶排序算法的改进,桶排序是将待排序数据的单一关键字依次进行桶分配,而基数排序是将待排数据中的每组关键字依次进行桶分配。桶排序和基数排序属于“分配式”排序(distribution sort),是通过比较键值的大小,将要排序的元素分配到“桶”(bucket)里,从而达到排序的目的。这基于“比较”的排序有本质区别,后者最好的复杂度也只有O(nlogn)。

基数排序是稳定排序,时间复杂度 O(n)。

示例:

278、109、063、930、589、184、505、269、008、083

我们将每个数值的个位,十位,百位分成三个关键字: 278 -> k1(个位)=8 ,k2(十位)=7 ,k3=(百位)=2。

然后从最低位个位开始(从最次关键字开始),对所有数据的k1关键字进行桶分配(因为,每个数字都是 0-9的,因此桶大小为10),再依次输出桶中的数据得到下面的序列。

930、063、083、184、505、278、008、109、589、269

再对上面的序列接着进行针对k2的桶分配,输出序列为:

505、008、109、930、063、269、278、083、184、589

最后针对k3的桶分配,输出序列为:

008、063、083、109、184、269、278、505、589、930

基数排序性能分析:

很明显,基数排序的性能比桶排序要略差。每一次关键字的桶分配都需要O(N)的时间复杂度,而且分配之后得到新的关键字序列又需要O(N)的时间复杂度。假如待排数据可以分为d个关键字,则基数排序的时间复杂度将是O(d*2N) ,当然d要远远小于N,因此基本上还是线性级别的。基数排序的空间复杂度为O(N+M),其中M为桶的数量。一般来说N»M,因此额外空间需要大概N个左右。

void radix_sort(int x[], int n)
{
    int tmp[n][n] = {0};
    int order[n] = {0};

    int num = 1;
    while(num <= n) {
        for(int i = 0; i < n; i++) {
            int lsd = ((x[i] / num) % n);
            tmp[lsd][order[lsd]] = x[i];
            order[lsd]++;
        }

        // 重新排列
        int k = 0;
        for(i = 0; i < n; i++) {
            if(order[i] != 0)  {
                int j;
                for(j = 0; j < order[i]; j++, k++) {
                    x[k] = tmp[i][j];
                }
            }
            order[i] = 0;
        }

        num *= n;
    }
}

EOF