Yanyg - SAN Software Engineer

排序算法

目录

1 内部排序

1.1 插入排序

1.1.1 计算机编程艺术

直接插入排序: 重新排列记录R1, …, RN到适当位置,排序完成后他们的键将处于有序状态:K1≤ … ≤KN

S1. [对j循环] 对j=2, 3, …, N执行S2到S5,然后结束算法;
S2. [设定i, K, R] 置 i ← j-1,K ← Kj, R ← Rj
S3. [比较K:Ki] 如果K≥Ki转到S5(已经找到R期望的位置);
S4. [移动Ri,减小i] 置 Ri+1 ← Ri,然后i ← i-1, 如果 i ← > 0返回S3(如果i=0,则K是目前找到的最小键,所以记录R属于位置1);
S5. [R进入Ri+1] 置 Ri+1←R。

1.1.2 WIKI

插入排序(英语:Insertion Sort)是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在实现上,通常采用in-place排序(即只需用到O(1)的额外空间的排序),因而在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间。

1.1.3 C语言实现

#include <stdio.h>

/* sort_insertion - sort algorithm by insertion
 * @array - starting pointer of integer array
 * @n - size of array @array
 */
static void sort_insertion(int *array, size_t n)
{
        size_t i, j;
        int v;

        for (i = 1; i < n; ++i) {
                v = array[i];
                /* check j < i then loop break after j underflow, because
                 * we need do loop for j == 0.
                 */
                for (j = i - 1; j < i; --j) {
                        if (v >= array[j]) {
                                break;
                        }
                        array[j+1] = array[j];
                }

                /* correction is @array[j+1].
                 * j+1 is corrected position even if j underflowed
                 */
                array[j+1] = v;
        }
}

static void print_array(const char *str, const int *array, size_t n)
{
        size_t i;

        printf("%s:", str);
        for (i = 0; i < n; ++i) {
                printf(" %d", array[i]);
        }
        printf("\n");
}

int main(int argc, char *argv[argc])
{
        int array[] = {250, 178, 473, 128, 852, 367, 178, 542, 250};
        const size_t n = sizeof(array)/sizeof(array[0]);

        print_array("before sort", array, n);
        sort_insertion(array, n);
        print_array("after  sort", array, n);

        return 0;
}

1.2 冒泡排序(交换排序)

1.2.1 计算机编程艺术

冒泡排序: 重新排列记录R1, …, RN到适当位置,排序完成后他们的键将处于有序状态:K1≤ … ≤KN

B1. [初始化BOUND] 置BOUND ← N (BOUND是尚不知其记录是否已处于最终位置上的最高小标;这表示此刻我们尚一无所知);
B2. [对j进行循环] 置 t ← 0,对 j=1, 2, …, BOUND-1执行步骤B3,然后转到B4,但如果BOUND=1,则直接跳转到B4;
B3. [比较/交换Rj:Rj+1] 如果Kj < Kj+1,则交换 Rj←→Rj+1,并置 t←j;
B4. [是否还要交换?] 如果 t←0,则此算法终止,否则置 BOUND ← t,并返回到B2;

1.2.2 WIKI

冒泡排序(英语:Bubble Sort)是一种简单的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

冒泡排序对n个项目需要O(n2)的比较次数,且可以原地排序。尽管这个算法是最简单了解和实现的排序算法之一,但它对于包含大量的元素的数列排序是很没有效率的。

冒泡排序是与插入排序拥有相等的运行时间,但是两种算法在需要的交换次数却很大地不同。在最坏的情况,冒泡排序需要O(n2)次交换,而插入排序只要最多O(n)交换。冒泡排序的实现(类似下面)通常会对已经排序好的数列拙劣地运行O(n2),而插入排序在这个例子只需要O(n)个运算。因此很多现代的算法教科书避免使用冒泡排序,而用插入排序取代之。冒泡排序如果能在内部循环第一次运行时,使用一个旗标来表示有无需要交换的可能,也可以把最优情况下的复杂度降低到O(n)。在这个情况,已经排序好的数列就无交换的需要。若在每次走访数列时,把走访顺序反过来,也可以稍微地改进效率。有时候称为鸡尾酒排序,因为算法会从数列的一端到另一端之间穿梭往返。

冒泡排序算法的运作如下:

  1. 比较相邻的元素。如果第一个比第二个大,就交换他们两个。
  2. 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。这步做完后,

最后的元素会是最大的数。

  1. 针对所有的元素重复以上的步骤,除了最后一个。
  2. 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。
  3. 由于它的简洁,冒泡排序通常被用来对于程序设计入门的学生介绍算法的概念。

1.2.3 C语言实现

#include <stdio.h>

static void swap_int_nocheck(int *a, int *b)
{
        int v = *a;
        *a = *b;
        *b = v;
}

/* sort_bubble - sort algorithm by bubbling
 * @array - starting pointer of integer array
 * @n - size of array @array
 */
static void sort_bubble(int *array, size_t n)
{
        size_t i, j;

        for (i = 1; i < n; ++i) {
                for (j = 0; j < n - i; ++j) {
                        if (array[j] > array[j+1]) {
                                swap_int_nocheck(array+j, array+j+1);
                        }
                }
        }
}

static void print_array(const char *str, const int *array, size_t n)
{
        size_t i;

        printf("%s:", str);
        for (i = 0; i < n; ++i) {
                printf(" %d", array[i]);
        }
        printf("\n");
}

int main(int argc, char *argv[argc])
{
        int array[] = {250, 178, 473, 128, 852, 367, 178, 542, 250};
        const size_t n = sizeof(array)/sizeof(array[0]);

        print_array("before sort_bubble", array, n);
        sort_bubble(array, n);
        print_array("after  sort_bubble", array, n);

        return 0;
}

1.2.4 C语言实现旗标版(性能优化)

#include <stdio.h>

static void swap_int_nocheck(int *a, int *b)
{
        int v = *a;
        *a = *b;
        *b = v;
}

/* sort_bubble - sort algorithm by bubbling
 * @array - starting pointer of integer array
 * @n - size of array @array
 */
static void sort_bubble(int *array, size_t n)
{
        size_t i, j, t;

        while (n) {
                t = 0;
                for (i = 0; i < n - 1; ++i) {
                        if (array[i] > array[i+1]) {
                                swap_int_nocheck(array+i, array+i+1);
                                /* we use i+1 because starting-index is 0 */
                                t = i + 1;
                        }
                }
                /* update @n to @t because @t is the last swapped pair
                 * @n will set to 0 to break outter loop if no swap happened.
                 */
                n = t;
        }
}

static void print_array(const char *str, const int *array, size_t n)
{
        size_t i;

        printf("%s:", str);
        for (i = 0; i < n; ++i) {
                printf(" %d", array[i]);
        }
        printf("\n");
}

int main(int argc, char *argv[argc])
{
        int array[] = {250, 178, 473, 128, 852, 367, 178, 542, 250};
        const size_t n = sizeof(array)/sizeof(array[0]);

        print_array("before sort_bubble flagged", array, n);
        sort_bubble(array, n);
        print_array("after  sort_bubble flagged", array, n);

        return 0;
}

1.3 选择排序

1.3.1 计算机编程艺术

直接选择排序: 适当重新安排记录R1, …, RN;在完成排序后,它们的键码将是有序的K1≤…≤KN。排序是以上边指出的方法为基础,但改为首选最大最大元素,紧接着选择第二个最大的,等等,这样做证明是更为方便的。

S1. [对j进行循环] 对 j=N, N-1, …, 2执行步骤S2和S3; S2. [找max(K1, …, Kj)] 查一遍Kj, Kj-1, …, K1 以找出极大者,设它为Ki,其中i尽可能地大; S3. [同Rj进行交换] 交换记录Ri↔Rj(现在诸记录Rj, …, RN都处于它们的最后位置处)。

1.3.2 C语言实现

#include <stdio.h>

static void swap_int_nocheck(int *a, int *b)
{
        int v = *a;
        *a = *b;
        *b = v;
}

/* sort_selection - sort algorithm by selecting
 * @array - starting pointer of integer array
 * @n - size of array @array
 */
static void sort_selection(int *array, size_t n)
{
        size_t i, j, t;
        int v;

        for (i = 0; i < n; ++i) {
                v = array[i];
                for (j = i+1; j < n; ++j) {
                        if (v > array[j]) {
                                v = array[j];
                                t = j;
                        }
                }

                /* @array[t] is the maximum */
                if (v != array[i]) {
                        swap_int_nocheck(array+i, array+t);
                }
        }
}

static void print_array(const char *str, const int *array, size_t n)
{
        size_t i;

        printf("%s:", str);
        for (i = 0; i < n; ++i) {
                printf(" %d", array[i]);
        }
        printf("\n");
}

int main(int argc, char *argv[argc])
{
        int array[] = {250, 178, 473, 128, 852, 367, 178, 542, 250};
        const size_t n = sizeof(array)/sizeof(array[0]);

        print_array("before sort_selection", array, n);
        sort_selection(array, n);
        print_array("after  sort_selection", array, n);

        return 0;
}

1.4 合并排序

1.4.1 计算机编程艺术

1.4.1.1 有序文件两路合并

两路合并:本算法把有序文件x1≤x2≤…≤xm和 y1≤y2≤…≤yn合并成单一文件 z1≤z2≤…≤zm+n

M1. [初始化] 置 i←1, j←1, k←1;
M2. [找较小者] 如果xi≤yi,则转到步骤3,否则转到步骤5;
M3. [输出xi] 置zk←xi,k←k+1,i←i+1,如果i≤m,返回M2;
M4. [传送yj, …, yn] 置(zk, …, zm+n)←(yj, …, yn)并终止此算法; M5. [输出yj] 置zk←yj,k←k+1,j←j+1,如果j≤n,返回M2;
M6. [传送xi, …, xm] 置(zk, …, zm+n)←(xi, …, xm)并终止此算法。

1.4.1.2 自然的两路合并排序

自然的两路合并排序: 使用两个存储区域,对记录R1, …, RN排序,

1.4.2 C语言实现

#include <errno.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

static void print_array(const char *str, const int *array, size_t n)
{
        size_t i;

        printf("%s:", str);
        for (i = 0; i < n; ++i) {
                printf(" %d", array[i]);
        }
        printf("\n");
}

/* sort_merge - sort algorithm by merging
 * @array - starting pointer of integer array
 * @n - size of array @array
 */
static int sort_merge(int *array, size_t n)
{
        size_t i, j, t, step;
        int v, *dest, *a, *b, *s1, *e1, *s2, *e2, *dd, *ds;

        dest = malloc(sizeof(*dest)*n*2);
        if (!dest) {
                fprintf(stderr, "could not alloc mem for merge\n");
                return ENOMEM;
        }

        memcpy(dest, array, n*sizeof(*array));
        ds = dest;

        for (step = 1; step < n; step *= 2) {
                dd = (ds == dest ? dest + n : dest);

                for (i = 0; i < n; i += step*2) {
                        s1 = ds + i;
                        e1 = s1 + step;
                        if (e1 > ds + n)
                                e1 = ds + n;
                        s2 = e1;
                        e2 = s2 + step;
                        if (e2 > ds + n)
                                e2 = ds + n;

                        while (s1 < e1 && s2 < e2) {
                                if (*s1 < *s2)
                                        *dd = *s1++;
                                else
                                        *dd = *s2++;
                                ++dd;
                        }

                        while (s1 < e1)
                                *dd++ = *s1++;
                        while (s2 < e2)
                                *dd++ = *s2++;
                }

                ds = dd - n;
        }

        // data copy back
        memcpy(array, ds, n*sizeof(*array));
        free(dest);
        return 0;
}

void __sort_merge_recursive(int* arr, int *help, size_t n)
{
        size_t i, part1 = n/2, part2;
        int *s1, *e1, *s2, *e2, *d;

        if (n <=1)
                return;

        part2 = part1 + (n%2);
        __sort_merge_recursive(arr, help, part1);
        __sort_merge_recursive(arr + part1, help, part2);

        s1 = arr;
        e1 = s1 + part1;
        if (e1 > arr + n)
                e1 = arr + n;
        s2 = e1;
        e2 = s2 + part2;
        if (e2 > arr + n)
                e1 = arr + n;

        d = help;
        while (s1 < e1 && s2 < e2) {
                if (*s1 <= *s2)
                        *d = *s1++;
                else
                        *d = *s2++;
                ++d;
        }
        while (s1 < e1)
                *d++ = *s1++;
        while (s2 < e2)
                *d++ = *s2++;

        for (i = 0; i < n; ++i)
                arr[i] = help[i];
}

int sort_merge_recursive(int *arr, size_t n)
{
        int *help = malloc(sizeof(*help)*n);

        if (!help)
                return ENOMEM;
        __sort_merge_recursive(arr, help, n);
        free(help);

        return 0;
}

int main(int argc, char *argv[argc])
{
        int array[] = {250, 178, 473, 128, 852, 367, 178, 542, 250};
        const size_t n = sizeof(array)/sizeof(array[0]);

        print_array("before sort_merge", array, n);
        sort_merge_recursive(array, n);
        print_array("after  sort_merge", array, n);

        return 0;
}

1.5 快速排序

1.5.1 算法导论

利用分治思想实现。分三步处理:

分解
数组$A[p..r]$划分为两个子数组$A[p..q-1]$与$A[q+1..r]$,使得\(A[p..q-1]\)

中的每一个元素都小于等于$A[q]$,$A[q+1..r]$每个元素都大于等于$A[q]$;其中,计算下标$q$也是划分过程的一部分;

解决
递归调用快速排序,对子数组$A[p..q-1]$和$A[q+1..r]$进行排序;
合并
因子数组都是原址排序的,所以不需要合并操作,$A[p..r]$已经是有序的。

1.5.2 优化

快排预期时间复杂度$O(nlgn)$,但如果数组已经是有序的,则会退化为$O(n^2)$。考虑随机化或中位化,但这个过程会引入一次数据交换,可能导致快排退化为非稳定排序。稳定的排序算法,是指关键字相同的记录,经过排序后相对次序保持不变。

1.5.3 C语言实现

#include <stdio.h>

int array[] = {108, 159, 124, 829, 520, 751, 328, 592, 650, 813};

#define PR_ARR(str, arr)        print_arr(str, arr, sizeof(arr)/sizeof(arr[0]))

static void print_arr(const char *str, const int *arr, size_t n)
{
        size_t i;

        printf("%s arr = ", str);
        for (i = 0; i < n; ++i) {
                printf("%3d ", arr[i]);
        }
        printf("\n");
}

static void swap_no_check(int *a, int *b)
{
        int t = *a;
        *a = *b;
        *b = t;
}

static inline size_t partition(int *arr, size_t low, size_t high)
{
        int x;
        size_t i, j;

        for (i = low - 1, j = low, x = arr[high]; j < high; ++j) {
                if (arr[j] <= x) {
                        ++i;
                        swap_no_check(arr + i, arr + j);
                }
        }

        ++i;
        swap_no_check(arr + i, arr + high);

        return i;
}

/*
 * interval: [low, high]
 */
static void __quick_sort(int *arr, size_t low, size_t high)
{
        size_t mid = (low + high)/2, q;

        if (low >= high)
                return;

        // swap mid and tail to performance risk off
        swap_no_check(arr + mid, arr + high);

        q = partition(arr, low, high);

        __quick_sort(arr, low, q);
        __quick_sort(arr, q + 1, high);
}

static inline void quick_sort(int *arr, size_t n)
{
        if (n)
                __quick_sort(arr, 0, n - 1);
}

int main(int argc, char *argv[argc])
{
        PR_ARR("before", array);

        quick_sort(array, sizeof(array)/sizeof(array[0]));

        PR_ARR("after ", array);

        return 0;
}

1.6 堆排序

1.6.1 算法导论

1.6.1.1 堆数据结构

堆数据结构是一组数组对象,可以被视为一颗完全二叉树。除最后一层外,树的每一层都是填满的,且最后一层从左向右填充。对于给定的任意下标,其左子树为2*i,右子树为2*i+1。考虑C数组起始下标为0,左子树为2*i + 1,右子树为2*(i+1)。 FIXME: Add Graphviz Here draw a tree and array.

1.6.1.2 保持堆的性质

对于一个数组A和下标i,对其调用max-heapify时,要求左子树left[i]和右子树right[i] 都是最大堆。max-heapify让A[i]在最大堆中“下降”,是的以i为根的子树成为最大堆。

1.6.1.3 建堆

自底向上地对数组A执行max-heapify。因为在最开始,对叶子节点执行max-heapify时,不存在左子树和右子树,因此满足最大堆,此后逐渐减小索引i调用max-heapify,堆性质得以满足。当i为0时,则整个数组满足最大堆,数组第一个元素是数组中的最大元素。

1.6.1.4 堆排序

先建堆,此后将第1个元素(最大元素)与数组最后一个元素交换,并使得数组大小减1,以此迭代直到数组大小为1,此时整个数组是有序的。

1.6.2 计算机编程艺术

1.6.2.1 描述

5.2.3节《选择排序》中树选择节讨论堆排序。堆排序:一个由键K1, K2, …, KN组成的文件称为一个堆,如果:

对 1≤ ⌊j/2⌋ < j ≤ N 有 K⌊j/2⌋ ≥ Kj

于是K1≥ K2, K1\geK3, K2≥K4等。且有 K1 = max{K1, K2, …, KN}。

1.6.2.2 算法描述

算法H(堆排序,弗洛伊德):重新排列记录R1, …, RN到适当位置,排序完成后它们的键将处于有序状态:K1≤…≤KN。首先重新排列输入文件构成一个堆,然后重复移动堆的顶节点,把它传送到正确位置。假定N≥2。

  • H1 [初始化] 置 l ← ⌊N/2⌋+1, r←N;
  • H2 [减小l或r] 如果l>1,则置l←l-1,R←Rl

K←Kl,(如果l<1,则处于把输入文件变化为堆的过程,另一方面,如果l\eq{}1,则键K1, K2, …, Kr已构成一个堆);否则置 R←R{r},K←Kr,Rr←R1, r←r-1,如果这使得r\eq{}1,则置R1←R,并终止算法。

  • H3 [准备上选] 置j←l,(这时对l→⌊k/2⌋

<k≤r 有 K⌊k/2⌋≥Kk; FIXME: <Unfinished>

1.6.3 C语言实现

#include <stdio.h>

int array[] = {108, 159, 124, 829, 520, 751, 328};

#define PR_ARR(str, arr)        print_arr(str, arr, sizeof(arr)/sizeof(arr[0]))

static void print_arr(const char *str, const int *arr, size_t n)
{
        size_t i;

        printf("%s arr = ", str);
        for (i = 0; i < n; ++i) {
                printf("%3d ", arr[i]);
        }
        printf("\n");
}

static void max_heapify(int *arr, size_t i, size_t n)
{
        size_t l = (i<<1) + 1, r = (i+1)<<1, max = i;

        if (l < n && arr[l] > arr[i])
                max = l;

        if (r < n && arr[r] > arr[max])
                max = r;

        if (max != i) {
                arr[i] ^= arr[max];
                arr[max] ^= arr[i];
                arr[i] ^= arr[max];
                max_heapify(arr, max, n);
        }
}

static void build_max_heapify(int *arr, size_t n)
{
        size_t i = (n/2);

        do {
                --i;
                max_heapify(arr, i, n);
        } while (i < n); /* overflow */
}

static void heap_sort(int *arr, size_t n)
{
        size_t i;

        build_max_heapify(arr, n);

        for (i = n - 1; i != 0; --i) {
                arr[0] ^= arr[i];
                arr[i] ^= arr[0];
                arr[0] ^= arr[i];
                max_heapify(arr, 0, --n);
        }
}

int main(int argc, char *argv[argc])
{
        PR_ARR("before", array);

        heap_sort(array, sizeof(array)/sizeof(array[0]));

        PR_ARR("after", array);

        return 0;
}

1.7 希尔排序

1.8 基数排序

FIXME:

1.9 桶排序