冒泡排序、选择排序、插入排序、堆排序、希尔排序、计数排序、归并排序、快速排序、桶排序、基数排序
各排序算法的时间复杂度：

图片来源：https://en.wikipedia.org/wiki/Sorting_algorithm
各排序算法的时间复杂度

冒泡排序

冒泡排序在1956年就已经被研究，不用多说了，经典中的经典了。

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
/**
 * @file bubble.c
 * @author your name (you@domain.com)
 * @brief 冒泡排序
 * @version 0.1
 * @date 2022-04-15
 * 
 * @copyright Copyright (c) 2022
 * 
 */

#include "stdio.h"


void swap(int* x, int* y)
{
    if (x != y)
    {
        *x = *x ^ *y;
        *y = *x ^ *y;
        *x = *x ^ *y;
    }
}

void bubble_sort(int* nums, int size)
{
    int i,j;
    /* 外层循环控制有边界 */
    for (i = size - 1; i >=1; --i)
    {
        for (j = 0; j < i; ++j)
        {
            if (nums[j] > nums[j + 1])
            {
                swap(&nums[j], &nums[j+1]);
            }
        }
    }
}

int main(void)
{
    int array[] = {3,4,1,2,5,7,8,6,5,9,10,5};
    bubbleSort(array, sizeof(array)/sizeof(int));
    int i = 0;
    for (; i < sizeof(array)/sizeof(int); ++i)
    {
        printf("%d ", array[i]);
    }
    printf("\n");
    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
/**
 * @file selection.c
 * @author your name (you@domain.com)
 * @brief 选择排序
 * @version 0.1
 * @date 2022-04-15
 * 
 * @copyright Copyright (c) 2022
 * 
 */

#include "stdio.h"

/**
 * 从序列中选择一个最大(或者最小)的，放到对应位置,
 * 由于从一个序列中选择最大或者最小的方式有多种，
 * 所以有多种选择排序,堆排序也可以看作是选择排序
 */


void swap(int* a, int* b)
{
    if (a != b){
        *a = *a ^ *b;
        *b = *a ^ *b;
        *a = *a ^ *b;
    }
}

/** 简单选择排序 */
void selectionSort(int* nums, int size)
{
    int i = 0;
    /* 外层循环控制待排序元素的位置 */
    for (; i < size - 1; ++i)
    {
        int minIndex = i;
        int j = 0;
        for (j = i + 1; j < size; ++j)
        {
            if (nums[j] < nums[minIndex]){
                minIndex = j;
            }
        }
        swap(&nums[minIndex], &nums[i]);
    }
}


int main(void)
{
    int array[] = {3,4,1,2,5,7,8,6,5,9,10,5};
    selectionSort(array, sizeof(array)/sizeof(int));
    int i = 0;
    for (; i < sizeof(array)/sizeof(int); ++i)
    {
        printf("%d ", array[i]);
    }
    printf("\n");
    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
/**
 * @file insertionSort.c
 * @author your name (you@domain.com)
 * @brief 插入排序
 * @version 0.1
 * @date 2022-04-15
 * 
 * @copyright Copyright (c) 2022
 * 
 */

#include "stdio.h"

void swap(int* a, int* b)
{
    if (a != b){
        *a = *a ^ *b;
        *b = *a ^ *b;
        *a = *a ^ *b;
    }
}

void insertionSort(int* nums, int size)
{
    int i = 1;
    for (; i < size; ++i)
    {
        int key = nums[i];
        int j = i - 1;
        for (; j >= 0 && key < nums[j]; --j)
        {
            nums[j + 1] = nums[j];
        }
        nums[j + 1] = key;
    }
}

int main(void)
{
    int array[] = {3,4,1,2,5,7,8,6,5,9,10,5};
    insertionSort(array, sizeof(array)/sizeof(int));
    int i = 0;
    for (; i < sizeof(array)/sizeof(int); ++i)
    {
        printf("%d ", array[i]);
    }
    printf("\n");
    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
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
/**
 * @file heapSort.c
 * @author your name (you@domain.com)
 * @brief 堆排序，也是一种选择排序
 * @version 0.1
 * @date 2022-04-15
 * 
 * @copyright Copyright (c) 2022
 * 
 */

#include "stdio.h"



void swap(int* a, int* b)
{
    if (a != b){
        *a = *a ^ *b;
        *b = *a ^ *b;
        *a = *a ^ *b;
    }
}

/**
 * @brief max堆，下滤
 * 
 * @param nums 
 * @param start 
 * @param end 
 */
void maxPercDown(int* nums, int dad, int end)
{
    int child = 0;
    int tmp = nums[dad];
    for (;dad * 2 + 1 <= end; dad = child)
    {
        child = dad * 2 + 1;
        /* 找到左右子元素中的最大值 */
        if (child != end && nums[child + 1] > nums[child])
        {
            ++child;
        }
        if (nums[child] > tmp)
        {
            nums[dad] = nums[child];
        }
        else
        {
            break;
        }
    }
    nums[dad] = tmp;
}

void heapSrot(int* nums, int size)
{
    /* 从最后一个父元素开始
       因为数组从0开始，所以对于一个下标为x的节点来说
       如果左右子节点存在，那么左子节点的下标是2x+1,右子节点是2x+2,
       所以，最后一个元素的下标是size-1,因此size - 1 == 2x+1 或者2x + 2;
       所以x = size / 2 - 1;
     */
    int dad = size/2 - 1;
    /* 第一步，将数组转换成max堆
       max堆中的数并没有排序好，因为只符合父节点比子节点大，
       但左右子节点的大小情况未知
     */
    for (; dad >= 0; --dad)
    {
        maxPercDown(nums, dad, size - 1);
    }
    /* 第二步，排序元素 */
    for (; size >= 1; --size)
    {
        /* 通过不断交换第一个元素和最后一个未排序的元素
           将当前最大的未排序元素放到最后，相当于从后往前排 */
        swap(&nums[0], &nums[size - 1]);
        maxPercDown(nums, 0, size - 2);
    }
}


int main(void)
{
    int array[] = {9,10,8,7,1,3,5,4,6,2,4, 13,12,10};
    heapSrot(array, sizeof(array)/sizeof(int));
    int i = 0;
    for (; i < sizeof(array)/sizeof(int); ++i)
    {
        printf("%d ", array[i]);
    }
    printf("\n");
    return 0;
}

希尔排序

希尔排序，1959 Donard L.Shell提出,也称递减增量排序算法,是优化的插入排序,插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率；但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位；

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
/**
 * @file shellSort.c
 * @author your name (you@domain.com)
 * @brief 希尔排序，也称递减增量排序算法,是优化的插入排序
 * 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率；
 * 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位；
 * 1959 Donard L.Shell提出
 * @version 0.1
 * @date 2022-04-15
 * 
 * @copyright Copyright (c) 2022
 * 
 */

#include "stdio.h"
#include "math.h"

/** Hibbard提出1，3，7，15...，这样的2^k - 1序列用于增量排序效果
 * 比N = N / 2的效果好
 * Sedgewick提出1，5，19，41，109...,这样的项或者是9*4^i - 9*2^i + 1
 * 或者是4^i - 3*2^i + 1,比上面的Hibbard提出的效果好
 */

void shellSort(int* nums, int size)
{
    int increment = 0;
    for (increment = size >> 1; increment > 0; increment >>= 1)
    {
        /** 希尔排序的内部就是简单插入排序 */
        int i;
        for (i = increment; i < size; ++i)
        {
            int key = nums[i];
            int j;
            for (j = i - increment; j >= 0 && nums[j] > key; j -= increment)
            {
                nums[j + increment] = nums[j];
            }
            nums[j + increment] = key;
        }
    }
}


int main(void)
{
    int array[] = {3,4,1,2,5,7,8,6,5,9,10,5};
    shellSort(array, sizeof(array)/sizeof(int));
    int i = 0;
    for (; i < sizeof(array)/sizeof(int); ++i)
    {
        printf("%d ", array[i]);
    }
    printf("\n");
    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
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
98
99
100
101
102
103
104
105
106
107
108
109
/**
 * @file counting_sort.c
 * @author your name (you@domain.com)
 * @brief 计数排序，非比较排序，作为一种线性时间复杂度的排序，
 * 计数排序要求输入的数据必须是有确定范围的整数，并且数据最好集中在一定的范围内，
 * 如果有个数特别大或者特别小，内存浪费会比较大。
 * 计数排序的基本思想是，如果我知道比我小的数有几个，那么我也就知道我排第几了
 * @version 0.1
 * @date 2022-04-19
 * 
 * @copyright Copyright (c) 2022
 * 
 */

#include "stdio.h"
#include "stdlib.h"
#include "string.h"

int find_max_min(int* arr, int size, int* p_max, int* p_min)
{
    if (size <= 0)
    {
        return -1;
    }
    *p_max = arr[0];
    *p_min = arr[0];
    int i;
    for (i = 1; i < size; ++i)
    {
        if (arr[i] > *p_max)
        {
            *p_max = arr[i];
        }
        if (arr[i] < *p_min)
        {
            *p_min = arr[i];
        }
    }
    return 0;
}

void counting_sort(int* arr, int size)
{
    int max, min;
    int ret = find_max_min(arr, size, &max, &min);
    if (ret < 0)
    {
        printf("find max or min error\n");
        return;
    }
    int* sorted_arr = (int*)malloc(size * sizeof(int)+20);
    if (!sorted_arr)
    {
        printf("out of memory\n");
        return;
    }
    int* count_arr = (int*)calloc(max - min + 1, sizeof(int));
    if (!count_arr)
    {
        printf("out of memory\n");
        free(sorted_arr);
        return;
    }
    int i;
    /* 这一步类似于哈希,将数的有序性转化为数组下标的有序性 */
    for (i = 0; i < size; ++i)
    {
        ++count_arr[arr[i] - min];
    }
    /****************下面两个for循环是关键点*****************/
    for (i = 1; i < max - min + 1; ++i)
    {
        count_arr[i] += count_arr[i - 1];
    }
    /* 计数排序，i从0开始还是size - 1开始无所谓，基数排序必须跟
    上一步中的个数累加顺序有关 */
    for (i = size - 1; i >= 0; --i)
    {
        sorted_arr[--count_arr[arr[i] - min]] = arr[i];
    }
    // for (i = 0; i < size; ++i)
    // {
    //     sorted_arr[--count_arr[arr[i] - min]] = arr[i];
    // }
    /*******************************************************/
    for (i = 0; i < size; ++i)
    {
        printf("%d, ", sorted_arr[i]);
    }
    memcpy(arr, sorted_arr, size * sizeof(int));
    printf("\n");
    free(count_arr);
    free(sorted_arr);
    return;
}


int main(void)
{
    int array[] = {3,4,1,2,5,7,8,6,5,9,10,5};
    counting_sort(array, sizeof(array)/sizeof(int));
    int i;
    for (i = 0; i < sizeof(array)/sizeof(int); ++i)
    {
        printf("%d ", array[i]);
    }
    printf("\n");
    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
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
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
/**
 * @file merge_sort.c
 * @author your name (you@domain.com)
 * @brief 归并排序
 * 采用分治法（Divide and Conquer）的一个非常典型的应用。
 * @version 0.1
 * @date 2022-04-18
 * 
 * @copyright Copyright (c) 2022
 * 
 */

#include "stdio.h"
#include "stdlib.h"
#include <math.h>

/**
 * 归并排序分为迭代法和递归法
 * 迭代法的基本思想是，一开始假设一个元素一组，然后相邻的两组进行比大小合并
 * 这样两个短的就变成了一个比原来长的有序分组了，然后再相邻的两两合并
 * 示意图如下，假设要求递增排序
 * 10   9   8   7   6   5   4   3   2   1
 *  \   /   \   /   \   /   \   /   \   /
 * [9,10]   [7,8]   [5,6]   [3,4]   [1,2]
 *      \   /           \   /
 *    [7,8,9,10]      [3,4,5,6]     [1,2]
 *              \     /
 *         [3,4,5,6,7,8,9,10]       [1,2]
 *                           \     /
 *                    [1,2,3,4,5,6,7,8,9,10]
 * 
 * 递归法的基本思想是，通过递归调用，不断对数进行二分法分组，直到每个分组都
 * 只有一个元素，然后再合并，合并过程类似上述类似。
 */



void merge(int* nums, int* tmp_nums, int left, int star_r, int right)
{
    int i, j, k;
    k = left;
    for (i = left, j = star_r; i <= star_r - 1 && j <= right;)
    {
        if (nums[i] <= nums[j])
        {
            tmp_nums[k] = nums[i];
            ++i;
            ++k;
        }
        else
        {
            tmp_nums[k] = nums[j];
            ++j;
            ++k;
        }
    }
    for (; j <= right; ++j, ++k)
    {
        tmp_nums[k] = nums[j];
    }
    for (; i <= star_r; ++i, ++k)
    {
        tmp_nums[k] = nums[i];
    }
    int size = right - left + 1;
    for (i = 0; i < size; ++i, ++left)
    {
        nums[left] = tmp_nums[left];
    }
}

/************************ 迭代法 *****************************/
void merge_sort_iter(int* nums, int size)
{
    int* tmp_nums = (int*)malloc(size * sizeof(int));
    // step 标识分组的长度，以1，2，4，8...方式增长
    int step = 1;
    int index = 0;
    // 第一层用于控制步长
    for (step = 1; step < size; step <<= 1)
    {
        // 第二层用于分组划分,span是合并后的分组大小
        int span = step + step;
        for (index = 0; index < size; index += span)
        {
            merge(nums, tmp_nums, index, fmin(index + step, size - 1), fmin(index + span - 1, size - 1));
        }
    }
    free(tmp_nums);
    return;
}


/************************ 递归法 *****************************/
void m_sort(int* nums, int* tmp_nums, int left, int right)
{
    if (left < right)
    {
        int center = (left + right) / 2;
        m_sort(nums, tmp_nums, left, center);
        m_sort(nums, tmp_nums, center + 1, right);
        merge(nums, tmp_nums, left, center + 1, right);
    }
}


void merge_sort(int *nums, int size)
{
    int* tmp_nums = (int*)malloc(size * sizeof(int));
    if (!tmp_nums)
    {
        printf("out of memory\n");
        return;
    }
    m_sort(nums, tmp_nums, 0, size - 1);
    free(tmp_nums);
    return;
}


int main(void)
{
    int array[] = {3,4,1,2,5,7,8,6,5,9,10,5};
    //merge_sort(array, sizeof(array)/sizeof(int));
    merge_sort_iter(array, sizeof(array)/sizeof(int));
    int i = 0;
    for (; i < sizeof(array)/sizeof(int); ++i)
    {
        printf("%d ", array[i]);
    }
    printf("\n");
    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
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
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
/**
 * @file quick_sort.c
 * @author your name (you@domain.com)
 * @brief 快速排序
 * @version 0.1
 * @date 2022-04-18
 * 
 * @copyright Copyright (c) 2022
 * 
 */

#include "stdio.h"
#include <stdlib.h>
#include <time.h>


void swap(int* a, int* b)
{
    if (a != b){
        *a = *a ^ *b;
        *b = *a ^ *b;
        *a = *a ^ *b;
    }
}

typedef struct Range
{
    int start;
    int end;
} Range;



/* 非递归的方式,在一次循环中，将可能的边界压栈 */
void quick_sort1(int* nums, int size)
{
    if (size <= 1)
    {
        return;
    }
    Range range[size];
    int p = 0;
    range[p].start = 0;
    range[p].end = size - 1;
    ++p;
    for (; p;)
    {
        Range r = range[--p];
        if (r.start >= r.end)
        {
            continue;
        }
        /* 去中间位置的数为枢纽数 */
        int pivot = nums[(r.start + r.end) / 2];
        int i = r.start;
        int j = r.end;
        /* 注意这里是小于等于 */
        for (; i <= j;)
        {
            for (; nums[i] < pivot;)
            {
                ++i;
            }
            for (; nums[j] > pivot;)
            {
                --j;
            }
            /* 注意这里是小于等于 */
            if (i <= j)
            {
                swap(&nums[i], &nums[j]);
                ++i;
                --j;
            }
        }

        if (r.start < j)
        {
            range[p].start = r.start;
            range[p].end = j;
            ++p;
        }
        if (i < r.end)
        {
            range[p].start = i;
            range[p].end = r.end;
            ++p;
        }
    }
}


int median3(int* nums, int left, int right)
{
    int center = ((left & right) + (left | right)) >> 1;
    if (nums[left] > nums[center]) {
        swap(&nums[left], &nums[center]);
    }
    if (nums[left] > nums[right]) {
        swap(&nums[left], &nums[right]);
    }
    if (nums[center] > nums[right]) {
        swap(&nums[center], &nums[right]);
    }
    // 把pivot数交换到最后一个位置 */
    swap(&nums[center], &nums[right - 1]);
    return nums[right - 1];
}


void q_sort(int* nums, int left, int right)
{
    int pivot = median3(nums, left, right);
    int i = left;
    int j = right - 1;
    while (i < j) {
        while (nums[++i] < pivot);
        while (nums[--j] > pivot);
        if (i < j)
        {
            swap(&nums[i], &nums[j]);
        }
    }
    /* 把pivot交换回i的位置 */
    swap(&nums[i], &nums[right - 1]);
    /* 至少有两个元素再排序 */
    if (i - 1 - left >= 1) {
        q_sort(nums, left, i - 1);
    }
    if (right - i - 1 >= 1) {
        q_sort(nums, i + 1, right);
    }
}

/* 递归方式 */
void quick_sort(int *nums, int size)
{
    q_sort(nums, 0, size - 1);
    return;
}

int main(void)
{
    int i = 0;
    struct timeval tv;
    gettimeofday(&tv, NULL);
    srand((unsigned int)(tv.tv_usec));
    int *arr = (int*)malloc(20 * sizeof(int));
    for (i = 0; i < 20; ++i) {
        arr[i] = rand() % 100000;
    }
    quick_sort(arr, 20);
    for (i = 0; i < 20; ++i)
    {
        printf("%d ", arr[i]);
    }
    printf("\n");
    free(arr);
    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
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
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
/**
 * @file bucket_sort.c
 * @author your name (you@domain.com)
 * @brief 桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。
 * 这里的映射函数类似于hash。
桶排序的思想近乎彻底的分治思想。
桶排序假设待排序的一组数均匀独立的分布在一个范围中，并将这一范围划分成几个子范围（桶）。
然后基于某种映射函数f ，将待排序列的关键字 k 映射到第i个桶中 (即桶数组B 的下标i) ，那么该关键字k 就作为 B[i]中的元素 (每个桶B[i]都是一组大小为N/M 的序列 )。
接着将各个桶中的数据有序的合并起来 : 对每个桶B[i] 中的所有元素进行比较排序 (可以使用快排)。然后依次枚举输出 B[0]….B[M] 中的全部内容即是一个有序序列。
补充： 映射函数一般是 f = array[i] / k; k^2 = n; n是所有元素个数
为了使桶排序更加高效，我们需要做到这两点：
1、在额外空间充足的情况下，尽量增大桶的数量；
2、使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中；
同时，对于桶中元素的排序，选择何种比较排序算法对于性能的影响至关重要。
 * @version 0.1
 * @date 2022-04-19
 * 
 * @copyright Copyright (c) 2022
 * 
 */

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


#define BUCKET_SIZE (5) /**< 假定均匀分布的情况下平均每个桶放几个元素*/


typedef struct Node
{
    int elem;
    struct Node* list_next;
} Node;

typedef struct BucketManager
{
    int nums;
    Node** buckets;  
} BucketManager;

typedef struct BucketSpaceManager
{
    int index;
    Node* nodes_space;
} BucketSpaceManager;


BucketSpaceManager* init_bucket_space(int size)
{
    BucketSpaceManager* space_mgr = (BucketSpaceManager*)malloc(sizeof(BucketSpaceManager));
    if (!space_mgr)
    {
        printf("out of memory,File:%s, Func:%s, Line:%d\n", __FILE__, __func__, __LINE__);
        goto exit_1;
    }
    space_mgr->index = 0;
    space_mgr->nodes_space = (Node*)malloc(size * sizeof(Node));
    if (!space_mgr->nodes_space)
    {
        printf("out of memory,File:%s, Func:%s, Line:%d\n", __FILE__, __func__, __LINE__);
        goto exit_2;
    }

    return space_mgr;

exit_2:
    free(space_mgr);
exit_1:
    return NULL;
}


BucketManager* init_buckets(int bucket_nums)
{
    BucketManager* bucket_mgr = (BucketManager*)malloc(sizeof(BucketManager));
    if (!bucket_mgr)
    {
        printf("out of memory,File:%s, Func:%s, Line:%d\n", __FILE__, __func__, __LINE__);
        goto exit_1;
    }
    bucket_mgr->nums = bucket_nums;
    bucket_mgr->buckets = (Node**)calloc(bucket_mgr->nums, sizeof(Node*));
    if (!bucket_mgr->buckets)
    {
        printf("out of memory,File:%s, Func:%s, Line:%d\n", __FILE__, __func__, __LINE__);
        goto exit_2;
    }
    return bucket_mgr;
exit_2:
    free(bucket_mgr);
exit_1:
    return NULL;
}


Node* get_bucket_space(BucketSpaceManager* space_mgr)
{
    if (space_mgr)
    {
        return &space_mgr->nodes_space[space_mgr->index++];
    }
    else
    {
        return NULL;
    }
}


void release_bucket_space(BucketSpaceManager* space_mgr)
{
    if (space_mgr)
    {
        if (space_mgr->nodes_space)
        {
            free(space_mgr->nodes_space);
        }
        free(space_mgr);
    }
}


void release_buckets(BucketManager* buckets_mgr)
{
    if (buckets_mgr)
    {
        if (buckets_mgr->buckets)
        {
            free(buckets_mgr->buckets);
        }
        free(buckets_mgr);
    }
}

int find_max_min(int* arr, int size, int* p_max, int* p_min)
{
    if (size <= 0)
    {
        return -1;
    }
    *p_max = arr[0];
    *p_min = arr[0];
    int i;
    for (i = 1; i < size; ++i)
    {
        if (arr[i] > *p_max)
        {
            *p_max = arr[i];
        }
        if (arr[i] < *p_min)
        {
            *p_min = arr[i];
        }
    }
    return 0;
}


int insert_bucket(BucketManager* bucket_mgr, int index, Node* new_node)
{
    Node* cur, *pre;
    if (!bucket_mgr->buckets[index])
    {
        bucket_mgr->buckets[index] = new_node;
    }
    else
    {
        /** 桶内使用插入排序 */
        cur = bucket_mgr->buckets[index];
        pre = cur;
        while (cur->list_next && new_node->elem > cur->elem)
        {
            pre = cur;
            cur = cur->list_next;
        }

        if (new_node->elem <= cur->elem)
        {
            if (pre == cur)
            {
                new_node->list_next = cur;
                bucket_mgr->buckets[index] = new_node;
            }
            else
            {
                new_node->list_next = cur;
                pre->list_next = new_node;
            }
        }
        else
        {
            cur->list_next = new_node;
        }

    }
    return 0;
}


void bucket_sort(int* arr, int size)
{
    int max, min;
    int ret = find_max_min(arr, size, &max, &min);
    if (ret < 0)
    {
        return;
    }

    BucketSpaceManager* space_mgr = init_bucket_space(size);
    if (!space_mgr)
    {
        printf("out of memory,File:%s, Func:%s, Line:%d\n", __FILE__, __func__, __LINE__);
        goto exit_1;
    }

    int bucket_nums = (max - min) / BUCKET_SIZE + 1;
    BucketManager* bucket_mgr = init_buckets(bucket_nums);
    if (!bucket_mgr)
    {
        goto exit_2;
    }
    int i;
    for (i = 0; i < size; ++i)
    {
        int index = (arr[i] - min) / BUCKET_SIZE;
        Node* new_node = get_bucket_space(space_mgr);
        if (!new_node)
        {
            goto exit_3;
        }
        new_node->elem = arr[i];
        new_node->list_next = NULL;
        insert_bucket(bucket_mgr, index, new_node);
    }
    for (i = 0; i < bucket_mgr->nums; ++i)
    {
        Node* node = bucket_mgr->buckets[i];
        while(node)
        {
            printf("%d ", node->elem);
            node = node->list_next;
        }
    }
    printf("\n");
exit_3:
    release_buckets(bucket_mgr);
exit_2:
    release_bucket_space(space_mgr);
exit_1:
    return;
}


int main(void)
{
    int test_nums[] = {237384,348185,338816,825359,461215,315112,170091,173609,724297,828355,395935,687922,127118,795454,166794,888047,274616,667202,772520,845914,142832,575527,980196,584061,784366,68694,80105,618370,915739,787506,379362,601205,44762,969018,625507,738640,900407,43638,477963,233716,613792,751212,231136,467042,514654,521610,369778,843173,257148,760274,234955,265546,891429,750091,942435,882691,485058,792360,435287,372065,396852,330275,801939,200914,455728,109280,527003,303337,793015,667734,279361,37810,783709,960454,33515,263864,624043,788379,449351,538850,706217,238925,353546,816968,654562,564565,948428,739868,861656,857587,418080,653483,909732,952407,927615,35267,732179,232870,933798,61900,147786,777833,294447,441553,819649,999015,523917,507135,9098,588245,831300,993003,945127,295861,806452,771032,921668,596114,58389,569490,199237,885193,713430,997040,349454,18832,365963,558789,793979,254667,902665,558387,193214,22187,589600,12593,959246,288997,790510,739049,415542,64949,504677,744804,344632,973744,984968,641758,44835,276866,533525,98170,362427,158920,761852,350430,378032,170007,937691,243911,35862,531400,478419,649378,146626,88512,280222,670261,941343,38126,514239,239530,502593,525678,583466,591214,539578,787397,941549,774755,828458,408562,867366,117131,114317,466268,629942,971386,113065,796098,875547,527563,539137,993188,177348,731079,452588,788027,482866,183936,891182,14590,796156,74952,512718,988078,316782,432209,405396,909257,659880,642669,784593,862734,581531,297746,379112,965834,757501,134934,262876,151414,341459,68737,335705,108420,175807,49204,418698,817329,683802,860609,970110,562200,491152,474457,82314,164791,579463,324083,114843,523863,305404,361637,631095,644669,990028,661638,98042,785313,92497,393902,493634,54193,786608,157915,907705,900047,733377,104396,800956,611681,900941,905797,918430,595666,611837,661676,485663,356116,62184,22936,101311,174347,176398,692221,924783,332203,23632,778317,433707,631680,847304,963864,713851,549636,191334,907916,47933,193726,839680,126830,969619,628862,971186,734295,940422,873838,710272,209108,23584,415483,344786,442615,533638,869735,327330,64692,223777,613179,926166,278178,42026,695892,190137,520649,212425,591392,953797,870512,920351,832099,272207,808275,724503,127489,522614,56839,59895,102922,200728,277140,756415,619144,202689,448065,169987,854403,718299,290852,184409,866904,468376,434288,683022,468668,521252,630787,910353,142102,776763,402397,997568,460132,591549,560002,140986,393106,315836,299789,11157,948822,736508,906511,359633,102634,758603,805615,991907,260305,566652,360444,640556,683744,490938,70267,974394,483178,140278,963198,607682,209876,545401,940834,353171,46725,959406,354607,105717,363535,16577,802543,148157,857807,853261,1498,894257,545218,888366,440977,760701,96299,194450,556914,761520,613246,137907,808247,716421,37096,466670,750120,55193,913440,8276,447656,578312,259763,531876,512665,141442,939404,522308,727677,66404,306827,611378,640320,463646,23442,814541,819520,700355,999156,299221,300487,694583,925423,942388,200218,951988,223828,625765,806161,775098,668188,354891,941824,874533,790457,17266,587582,782052,543260,761066,33671,282287,36517,641769,385319,788130,444800,151440,760399,156927,810160,399433,20665,789379,245026,869278,79201,525654,154337,153772,520742,409817,351982,632677,27469,461968,67163,598474,413742,162730,398958,301268,188138,454016,685406,65119,424960,818292,500147,531479,320450,31786,847222,17718,573327,675570,627627,134531,278662,882290,91973,715585,416932,141758,330628,608707,961155,644588,685130,558779,690500,576750,57187,662322,665426,878670,398251,851778,73445,291259,667672,879137,421584,252470,981007,959007,53698,133588,258920,681480,73704,369061,257507,783989,955086,78221,878089,393338,909013,941463,497392,775208,464141,885513,194241,576540,994311,430940,463882,476639,97844,412750,31014,834638,766103,636265,574729,830894,789695,824714,226564,302451,431214,698974,268952,909138,568967,526732,990610,420963,887778,652540,435751,931021,543446,232181,236984,751446,608881,804842,538843,329712,355717,782681,473005,767954,470918,742657,728655,365915,904237,846747,6298,705289,457213,288518,679537,486580,99128,173621,770845,958054,602720,628137,857349,902228,143259,788408,349345,704796,603484,480846,169475,888264,7467,101509,944655,550048,233987,97958,211933,262737,696890,306842,268402,823675,462983,500079,337185,779420,235971,618001,852936,348159,585270,253322,133651,275390,815377,859521,719221,37242,211276,151229,636060,782778,520680,520329,485325,259013,617869,511118,52820,606179,457781,861353,410867,169794,503806,854135,485535,34892,964607,585208,638485,609536,731747,715170,318192,802739,356387,170816,357610,891098,977234,976964,264819,525494,418773,26864,134949,843984,324369,726637,41795,512710,401258,835971,73776,630372,381524,305245,549503,725983,342165,317492,850053,764863,120577,43205,843143,996410,732112,282227,857503,197508,483094,483191,404547,689744,533489,54389,816657,900804,547343,766481,89532,836491,571400,361547,453296,487986,777471,581869,517966,657816,205850,484738,437893,369736,329489,129082,995024,910156,562018,690831,772881,471961,68259,868647,162362,698669,706968,803864,200166,791470,779783,656081,432804,101615,903098,603139,243133,63039,723923,706235,176627,421722,156099,251079,570462,387579,135309,254221,900525,401696,545242,649953,265465,478224,210210,870963,11204,906806,593938,308828,839903,344986,552973,868191,423898,841030,31248,201878,908361,938518,702414,927371,187915,582150,250622,853272,378462,750728,841296,646057,86613,903991,884906,370017,62265,971984,411031,64080,252978,73118,398306,312366,58337,774908,11239,137947,738056,492168,116364,24769,96167,192952,142183,517522,978015,944570,354291,42020,729306,258838,402630,687489,965651,456761,261371,7505,994268,758338,292010,750701,193464,514023,303629,973093,998924,693448,114160,989360,30856,262046,625396,142208,76524,64194,932588,28579,606417,300349,605278,223074,298180,775329,468490,652937,990775,698051,584527,259521,53062,300194,522713,38368,473798,940083,295847,514003,243339,886679,558418,48354,266870,101180,725339,414568,438067,74220,606737,674479,136313,758031,941488,506637,146915,500431,56167,876539,911115,819750,526974,136156,809654,819404,994640,114101,610563,365490,210767,558064,868269,621800,943069,84813,577138,794535,644600,760143,357944,229363,240759,31577,178432,281788,921022,888824,619432,71886,313585,988663,434824,385765,135830,842738,370217,578942,354150,32117,347770,436059,109040,955493,608239,501982,465481,519878,96756,397057,209517,402619,619978,231284,399712,160156,531674,41788,899754,535660,334515,908049,679252,825448,396682,349157,921979,17598,811584,849117,415521,968473,119924,241966,956841,819813,256247,926526,8530,456200,933361,282325,705205,553214,906451,944192,889932,164576,516882,859439,52687,111709,778327,369781,474722,264710,537749,420656,227498,913284,444034,86666,71542};

    int array[] = {9,1,10,8,7,10,3,5,4,6,10,10,2,10,11,9,4,7,20,22,54};
    bucket_sort(array, sizeof(array)/sizeof(int));
    // bucket_sort(test_nums, sizeof(test_nums)/sizeof(int));
    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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
/**
 * @file radix_sort.c
 * @author your name (you@domain.com)
 * @brief 基数排序是一种非比较型整数排序算法，
 * 其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。
 * 由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。
 * @version 0.1
 * @date 2022-04-20
 * 
 * @copyright Copyright (c) 2022
 * 
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/* 待排序数的进制 */
#define BASE (10)


int find_max(int* arr, int size)
{
    int max = arr[0];
    int i;
    for (i = 1; i < size; ++i)
    {
        if (max < arr[i])
        {
            max = arr[i];
        }
    }
    return max;
}


void radix_sort(int* arr, int size)
{
    int* backup = arr;
    int* snd_arr = (int*)malloc(size * sizeof(int));
    int bucket[BASE] = {0};
    int i;
    int max = find_max(arr, size);
    int exp = 1;
    while (max / exp > 0)
    {
        for (i = 0; i < size; ++i)
        {
            ++bucket[(arr[i] / exp) % BASE];
        }
        for (i = 1; i < size; ++i)
        {
            bucket[i] += bucket[i - 1];
        }
        /* 计数排序，i从0开始还是size - 1开始无所谓，基数排序必须跟
        上一步中的个数累加顺序有关 */
        for (i = size - 1; i >= 0; --i)
        {
            snd_arr[--bucket[(arr[i] / exp) % BASE]] = arr[i];
        }
        /* 交换两个指针，这样就不用复制了，来回倒腾 */
        int * tmp;
        tmp = arr;
        arr = snd_arr;
        snd_arr = tmp;
        memset(bucket, 0 , BASE * sizeof(int));
        exp *= BASE;
    }
    if (backup != arr)
    {
        memcpy(arr, snd_arr, size * sizeof(int));
    }
    free(snd_arr);
}

int main(void)
{
    int array[] = {3,4,1,2,5,7,8,6,5,9,10,5};
    radix_sort(array, sizeof(array)/sizeof(int));
    int i = 0;
    for (; i < sizeof(array)/sizeof(int); ++i)
    {
        printf("%d ", array[i]);
    }
    printf("\n");
    return 0;
}