插入排序(选择排序, 冒泡排序Insertion Sort)

插入排序每次从数组里选出一个元素, 和新数组里的元素一一进行对比, 然后将新元素排到比它最大/小的元素的左或右边, 时间复杂度为 O(n2)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/* issort.c */
#include <stdlib.h>
#include <string.h>

/* data 指向数组, size 是数组中元素个数, esize 是每个元素的大小, compare 是元素之间的比较函数 */
iint issort(void *data, int size, int esize, int (*compare)(const void *key1,
    const void *key2))
{
    /* char指针是 1 字节大小的指向, a[i * esize]则引用到了第 i 个大小为 esize 的地址 */
    char *a = data;
    void *key;
    int i, j;

    /* allocate storage for the key element */
    if ((key = (char *)malloc(esize)) == NULL) {
        return -1;
    }

    for (j = 1; j < size; j++) {
        memcpy(key, &a[j * esize], esize);

        i = j - 1;
        while (i >=0 && compare(&a[i *esize], key) > 0) {
            memcpy(&a[(i + 1) * esize], &a[i * esize], esize);
            i--;
        }
        /*
        等同上面的 while
        for (i = j - 1; i >= 0; i--) {
            if (compare(&a[i *esize], key) > 0) {
                memcpy(&a[(i + 1) * esize], &a[i * esize], esize);
            } else {
                break;
            }
        }
        */
        memcpy(&a[(i + 1) * esize], key, esize);
    }
    free(key);
    return 0;
}

快速排序(Quick sort)

  1. 每次选择一个数据, 然后所有的数据和这个数对比, 小的放在左边, 大的放在右边
  2. 然后对左, 右两边的新数组继续重复第一步, 一直到左, 右数组都为空, 依次返回数组

快速排序的时间复杂度依赖于每次所选的数, 最坏为O(n<sup>2></sup>), 平均是O(nlog n)

为最大可能接近O(nlog n), 每次都随机从数组中选择三个数, 取这三个数的中间值

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include <stdlib.h>
#include <string.h>
#include "sort.h"

static int compare_int(const void *int1, const void *int2)
{
    if (*(const int *)int1 > *(const int *)int2) {
        return 1;
    } else if (*(const int *)int1 < *(const int *)int2) {
        return -1;
    } else {
        return 0;
    }
}

static int partition(void *data, int esize, int i, int k,
    int (*compare)(const void *key1, const void *key2))
{
    char *a = (char *)data;
    void *pval, *temp;
    int r[3];

    if ((pval = malloc(esize)) == NULL) {
        return -1;
    }
    if ((temp = malloc(esize)) == NULL) {
        free(pval);
        return -1;
    }
    /* 随机选取三个位置, 排序后取中间的值, 尽量保证左右两边的值是均匀的 */
    r[0] = (rand() % (k - i + 1)) + i;
    r[1] = (rand() % (k - i + 1)) + i;
    r[2] = (rand() % (k - i + 1)) + i;
    issort(r, 3, sizeof(int), compare_int);
    memcpy(pval, &a[r[1] * esize], esize);

    i--;
    k++;
    /* 每选中一个数, 在调换位置之后都保证其左边的数不会符合 compare() < 0 */
    while (1) {
        do {
            k--;
        }while (compare(&a[k * esize], pval) > 0);

        do {
            i++;
        }while (compare(&a[i * esize], pval) < 0);

        if (i >= k) {
            break;
        } else {
            memcpy(temp, &a[i * esize], esize);
            memcpy(&a[i * esize], &a[k * esize], esize);
            memcpy(&a[k * esize], temp, esize);
        }
    }
    free(pval);
    free(temp);

    return k;
}

/**
 * data 是数组指向
 * size 是数组大小
 * esize 是每个元素的大小
 * i 是数组的头结点下标, 初始为 0
 * k 是数组末尾结点下标, 初始为 size - 1
 * compare 是比较函数, 大于返回 1, 小于返回 -1, 等于返回 0
 */
int qksort(void *data, int size, int esize, int i, int k,
    int (*compare)(const void *key1, const void *key2))
{
    int j;

    while (i < k) {
        if ((j = partition(data, esize, i, k, compare)) < 0) {
            return -1;
        }
        /* 每次递归都先处理上个 key 的位置的左边的数据 */
        if (qksort(data, size, esize, i, j, compare) < 0) {
            return -1;
        }
        /* 将位置改到位置 */
        i = j + 1;
    }
    return 0;
}

快速排序的例子: 目录列表

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <stdi.h>
#include <stdlib.h>
#include <string.h>
#include <dirent.h>
#include "sort.h"

typedef struct Directory_ {
    char name[MAXNAMLEN + 1];
}Directory;

static int compare_dir(const void *key1, const void *key2)
{
    int retval;

    if ((retval = strcmp(((const Directory *)key1)->name,
        ((const Directory *)key2)->name)) > 0) {
        return 1;
    } else if (retval < 0) {
        return -1;
    } else {
        return 0;
    }
}

int directls(const char *path, Directory **dir)
{
    DIR *dirptr;
    Directory *temp = NULL;
    struct dirent *curdir;
    int count, i;
    /* 打开目录 */
    if ((dirptr = opendir(path)) == NULL) {
        return -1;
    }

    dir = &temp;
    count = 0;

    while ((curdir = readdir(dirptr)) != NULL) {
        count++;
        if ((temp = (Directory *)realloc(*dir, count * sizeof(Directory))) == NULL) {
            free(*dir);
            return -1;
        } else {
            *dir = temp;
        }
        strcpy(((*dir)[count - 1]).name, curdir->d_name);
    }
    closedir(dirptr);

    if (qksort(*dir, count, sizeof(Directory), 0, count - 1, compare_dir) != 0) {
        return -1;
    }
    return count;
}

归并排序(Merge Sort)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include <stdlib.h>
#include <stdio.h>
#include "sort.h"

static int merge(void *data, int esize, int i, int j, int k,
    int (*compare)(const void *key1, const void *key2))
{
    char *a = data,
         *m;
    int ipos, jpos, mpos;

    ipos = i;
    jpos = j + 1;
    mpos = 0;

    if ((m = (char *)malloc(esize * ((k - i) + 1))) == NULL) {
        return -1;
    }

    while (ipos <= j || jpos <= k) {
        if (ipos > j) {
            while (jpos <= k) {
                memcpy(&m[mpos * esize], &a[jpos * esize], esize);
                jpos++;
                mpos++;
            }
            continue;
        } else if (jpos > k) {
            while (ipos <= j) {
                memcpy(&m[mpos * esize], &a[ipos * esize], esize);
                ipos++;
                mpos++;
            }
            continue;
        }

        if (compare(&a[ipos * esize], &a[jpos * esize]) < 0) {
            memcpy(&m[mpos * esize], &a[ipos * esize], esize);
            ipos++;
            mpos++;
        } else {
            memcpy(&m[mpos * esize], &a[jpos * esize], esize);
            jpos++;
            mpos++;
        }
    }

    memcpy(&a[i * esize], m, esize * ((k - i) + 1));
    free(m);
    return 0;
}


/**
 * data 是数组指向
 * size 是数组大小
 * esize 是每个元素的大小
 * i 是数组的头结点下标, 初始为 0
 * k 是数组末尾结点下标, 初始为 size - 1
 * compare 是比较函数, 大于返回 1, 小于返回 -1, 等于返回 0
 */
int mgsort(void *data, int size, int esize, int i, int k,
    int (*compare)(const void *key1, const void *key2))
{
    int j;

    if (i < k) {
        j = (int)(((i + k - 1)) / 2);

        if (mgsort(data, size, esize, i, j, compare) < 0) {
            return -1;
        }
        if (mgsort(data, size, esize, j + 1, k, compare) < 0) {
            return -1;
        }
        if (merge(data, esize, i, j, k, compare) < 0) {
            return -1;
        }
    }

    return 0;
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
/* 一种排序数组的方法, 每次会使用新的内存来保存左右值, 写回原数组后再释放 */
int merge_sort(void *data, int size, int esize,
    int (*compare)(const void *key1, const void *key2))
{
    char *d = (char *)data;
    char *key, *left, *right;
    int i,
        pos_left = 0,
        pos_right = 0,
        length = (size - 1) * esize;
    int r[3];


    if ((left = (char *)malloc(length)) == NULL ||
        (right = (char *)malloc(length)) == NULL ||
        (key = (char *)malloc(esize)) == NULL) {
        return -1;
    }

    /* 随机确定某个数的位置 */
    r[0] = rand() % size;
    r[1] = rand() % size;
    r[2] = rand() % size;
    issort(r, 3, sizeof(int), compare_int);
    memset(left, '\0', length);
    memset(right, '\0', length);
    memcpy(key, &d[r[1] * esize], esize);
    /* 比较大小, 分到左右数组 */
    for (i = 0; i < size; i++) {
        if (i != r[1]) {
            if (compare(&d[i * esize], key) > 0) {
                /* right */
                memcpy(&right[pos_right * esize], &d[i * esize], esize);
                pos_right++;
            } else {
                /* left */
                memcpy(&left[pos_left * esize], &d[i * esize], esize);
                pos_left++;
            }
        }
    }
    /* 分好的数组写回原数组, 然后释放左右数组 */
    for (i = 0; i < pos_left; i++) {
        memcpy(&d[i * esize], &left[i * esize], esize);
    }
    memcpy(&d[(pos_left) * esize], key, esize);
    for (i = 0; i < pos_right; i++) {
        memcpy(&d[(pos_left + i + 1) * esize], &right[i * esize], esize);
    }
    free(left);
    free(right);
    free(key);
    /* 在原数组上继续比较分好的左右两边 */
    if (pos_left > 1 && merge_sort(d, pos_left, esize, compare) != 0) {
        return -1;
    }
    if (pos_right > 1 && merge_sort(&d[(pos_left + 1) * esize], pos_right,
        esize, compare) != 0) {
        return -1;
    }
    return 0;
}

计数排序(Counting Sort)

计数排序只能用于整型或者那些可以用整型来表示的数据集合, 通过计算一个集合中元素出现的次数来确定集合如何排列

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include <stdlib.h>
#include <string.h>
#include "sort.h"


int ctsort(int *data, int size, int k)
{
    int *counts, *temp;
    int i, j;

    if ((counts = (int *)malloc(size * sizeof(int))) == NULL) {
        return -1;
    }

    for (i = 0; i < k; i++) {
        counts[i] = 0;
    }

    for (j = 0; j < size; j++) {
        counts[data[j]] = counts[data[j]] + 1;
    }

    for (i = 1; i < k; i++) {
        counts[i] = counts[i] + counts[i - 1];
    }

    for (j = size - 1; j >= 0; j--) {
        temp[counts[data[j]] - 1] = data[j];
        counts[data[j]] = counts[data[j]] - 1;
    }

    memcpy(data, temp, size * sizeof(int));

    free(counts);
    free(temp);
    return 0;
}


#### 基数排序(Radix Sort)

基数排序是一种高效的纯属排序算法, 其方法是将数据按位分开, 并从数据的最低有效位到最高有效位进行比较, 依次排序, 从而得到有序的数据集合

对于数据{15, 12, 49, 16, 36, 40}来说, 第一次对个位数进行从低到高排序后{40, 12, 15, 16, 36, 49},然后再对十位数个的数进行排序最后得到最终结果{12, 15, 16, 36, 40, 49}

基数排序并不局限于对整型数据进行排序, 只要能把元素分割成整型数, 就可以使用基数排序


​```c
#include <limits.h>
#include <math.h>
#include <stdlib.h>
#include <string.h>
#include "sort.h"

int rxsort(int *data, int size, int p, int k)
{
    int *counts, *temp;
    int index, pval, i, j, n;

    if ((counts = (int *)malloc(k * sizeof(int))) == NULL) {
        return -1;
    }

    if ((temp = (int *)malloc(size * sizeof(int))) == NULL) {
        return -1;
    }

    for (n = 0; n < p; n++) {
        for (i = 0; i < k; i++) {
            counts[i] = 0;
        }

        pval = (int)pow((double)k, (double)n);

        for (j = 0; j < size; j++) {
            index = (int)(data[j] / pval) % k;
            counts[index] = counts[index] + 1;
        }

        for (i = 1; i < k; i++) {
            counts[i] = counts[i] + counts[i - 1];
        }

        for (j = size - 1; j >= 0; j--) {
            index = (int)(data[j]/pval) % k;
            temp[counts[index] - 1] = data[j];
            counts[index] = counts[index] - 1;
        }
        memcpy(data, temp, size * sizeof(int));
    }
    free(counts);
    free(temp);
    return 0;
}


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <stdlib.h>
#include <string.h>
#include "search.h"


int bisearch(void *sorted, void *target, int size, int esize,
    int (*compare)(const void *key1, const void *key2))
{
    int left, middle, right;

    left = 0;
    right = size - 1;

    while (left <= right) {
        middle = (left + right) / 2;

        switch (compare(((char *)sorted + (esize * middle)), target)) {
            case -1:
                left = middle + 1;
                break;

            case 1:
                right = middle - 1;
                break;

            case 0:
                return middle;
        }
    }
    return -1;
}

二分查找示例: 拼写检查器

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <string.h>
#include <stdlib.h>


#define SPELL_SIZE 31

static int compare_str(const void *str1, const void *str2)
{
    int retval;

    if ((retval = strcmp((const char *)str1, (const char *)str2)) > 0) {
        return -1;
    } else if (retval < 0) {
        return -1;
    } else {
        return 0;
    }
}

/**
 * dictionary 是一个可接受的有序字符串数组
 * size 是字典中字符串的个数
 * word 是被检查的单词
 */
int spell(char (*dictionary)[SPELL_SIZE], int size, const char *word)
{
    if (bisearch(dictionary, word, size, SPELL_SIZE, compare_str) >= 0){
        return -1;
    } else {
        return 0;
    }
}