堆排序

堆排序利用了堆的特性进行排序。堆是一种近似完全二叉树的结构,满足以下性质:子节点的键值总是小于(或大于)它的父节点。

堆排序的C实现:

void sink(int *n, int i, int len)
{
    int l = 2*i + 1;
    if (l > len - 1) return;
    int r = l + 1;
    int _max_lr = (r > len - 1) ? l : (*(n+r) > *(n+l) ? r : l);
    if (*(n+_max_lr) < *(n+i)) return;
    swap(n+_max_lr, n+i);
    sink(n, _max_lr, len);
}

void heap(int *n, int len)
{
    int i;
    for (i=(len-1)/2; i>=0; i--) {
        sink(n, i, len);
    }

    print_n_array(n, 10);
    for (i=0; i<len; i++) {
        swap(n, n+len-1-i);
        sink(n, 0, len-i-1);
    }
}

堆排序最差情况的时间复杂度为\(n \lg n\) .堆排序需要的额外空间为\(O(1)\) .堆排序是不稳定的.

堆排序与快排的比较

  • 快排总体来说较堆排序更快
  • 快排最差情况下接近\(O(n^2)\)
  • 快排需要更多的额外空间

因此,考虑到堆排序最差情况的复杂度上限和需要额外空间的上限,通常将其应用在对实时性要求较高和安全性较高的嵌入式系统中。

堆排序与归并排序的比较

  • 二者时间复杂度均为\(n \lg n\) .
  • 堆排序在数据缓存较小的计算机上更快,因为堆排序需要更少的额外空间。
  • 堆排序不稳定,归并排序稳定。
  • more

归并排序

归并排序是把两个或两个以上有序列表合并为一个新的有序列表。

归并排序的C实现(递归版本):

void merge(int *n, int len)
{
    if (len <= 1) return;

    int half = len / 2;
    merge(n, half);
    merge(n+half, len-half);

    int *_n = (int *) malloc(half * sizeof(int));
    memcpy(_n, n, half * sizeof(int));

    int i=0, j=half, k=0;
    while (i<half && j<len) {
        *(n+ k++) = *(n+j) < *(_n+i) ? *(n+ j++) : *(_n+ i++);
    }
    while (i<half) {
        *(n+ k++) = *(_n+ i++);
    }
            free(_n);
}

复杂度计算:

\begin{equation*} \left\{ \begin{array}{l} T(1) = 1 \\ T(n) = 2 T(\frac n 2) + n \end{array} \right. \end{equation*}

解之可得:

\begin{equation*} T(n) = n \log_2 n \end{equation*}

比较操作的次数介于\((n \log n)/2\)\(n \log n - n + 1\) 之间。赋值操作的次数是\(2n \log n\) 。归并算法的空间复杂度为:\(O(n)\) .

归并排序是唯一的稳定的复杂度为\(O(n \log n)\) 的排序算法。

三路快速排序

三路快速排序是快速排序针对相等元素较多情况的改进版本。

三路快排的C实现:

void quicksort3(int *n, int len)
{
    int i=0, j=0, k=len-1;

    if (len<2) return;

    while (i<k) {
        if (*(n+i) < *(n+k)) {
            swap(n+ i++, n+ j++);
        } else if (*(n+i) == *(n+k)) {
            swap(n+i, n+ --k);
        } else {
            i++;
        }
    }

    // k-j is length of nums larger than tail num, len-k is length of nums
    // equal to tail num
    int m = (k-j) < (len-k) ? (k-j) : (len-k);
    int _i;
    for (_i=0; _i<m; _i++) {
        swap(n+j+_i, n+len-m+_i);
    }

    // j is len of nums less than tail num
    if (j>1) quicksort3(n, j);
    if (k-j>1) quicksort3(n+len-k+j, k-j);
}

三路快排比传统快排稍微复杂,但它继承了快排的所有优点,而且针对相等元素较多的情况速度提升非常明显。

MORE