排序算法

1 内部排序

1.1 插入排序

1.1.1 计算机编程艺术

直接插入排序: 重新排列记录R₁, …, R_N到适当位置，排序完成后他们的键将处于有序状态：K₁≤ … ≤K_N

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

1.1.2 WIKI

https://zh.wikipedia.org/wiki/%E6%8F%92%E5%85%A5%E6%8E%92%E5%BA%8F

插入排序（英语：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 计算机编程艺术

冒泡排序: 重新排列记录R₁, …, R_N到适当位置，排序完成后他们的键将处于有序状态：K₁≤ … ≤K_N

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

1.2.2 WIKI

https://zh.wikipedia.org/wiki/%E5%86%92%E6%B3%A1%E6%8E%92%E5%BA%8F

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

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

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

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

比较相邻的元素。如果第一个比第二个大，就交换他们两个。

对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，

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

针对所有的元素重复以上的步骤，除了最后一个。

持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

由于它的简洁，冒泡排序通常被用来对于程序设计入门的学生介绍算法的概念。

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 计算机编程艺术

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

S1. [对j进行循环] 对 j=N, N-1, …, 2执行步骤S2和S3； S2. [找max(K₁, …, K_j)] 查一遍K_j, K_j-1, …, K₁ 以找出极大者，设它为K_i，其中i尽可能地大； S3. [同R_j进行交换] 交换记录R_i↔R_j（现在诸记录R_j, …, R_N都处于它们的最后位置处）。

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 有序文件两路合并

两路合并：本算法把有序文件x₁≤x₂≤…≤x_m和 y₁≤y₂≤…≤y_n合并成单一文件 z₁≤z₂≤…≤z_m+n。

M1. [初始化] 置 i←1, j←1, k←1；
M2. [找较小者] 如果x_i≤y_i，则转到步骤3，否则转到步骤5；
M3. [输出x_i] 置z_k←x_i，k←k+1，i←i+1，如果i≤m，返回M2；
M4. [传送y_j, …, y_n] 置(z_k, …, z_m+n)←(y_j, …, y_n)并终止此算法； M5. [输出y_j] 置z_k←y_j，k←k+1，j←j+1，如果j≤n，返回M2；
M6. [传送x_i, …, x_m] 置(z_k, …, z_m+n)←(x_i, …, x_m)并终止此算法。

1.4.1.2 自然的两路合并排序

自然的两路合并排序: 使用两个存储区域，对记录R₁, …, R_N排序，

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节《选择排序》中树选择节讨论堆排序。堆排序：一个由键K₁, K₂, …, K_N组成的文件称为一个堆，如果：

对 1≤ ⌊j/2⌋ < j ≤ N 有 K_⌊j/2⌋ ≥ K_j。

于是K₁≥ K₂, K₁\geK₃, K₂≥K₄等。且有 K₁ = max{K₁, K₂, …, K_N}。

1.6.2.2 算法描述

算法H（堆排序，弗洛伊德）：重新排列记录R₁, …, R_N到适当位置，排序完成后它们的键将处于有序状态：K₁≤…≤K_N。首先重新排列输入文件构成一个堆，然后重复移动堆的顶节点，把它传送到正确位置。假定N≥2。

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

K←K_l，（如果l<1，则处于把输入文件变化为堆的过程，另一方面，如果l\eq{}1，则键K₁, K₂, …, K_r已构成一个堆）；否则置 R←R{r}，K←K_r，R_r←R₁， r←r-1，如果这使得r\eq{}1，则置R₁←R，并终止算法。

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

<k≤r 有 K_⌊k/2⌋≥K_k； 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: