数据结构 十 排序

sort.h

对于基数排序的实现，这位大神太厉害了。代码

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
#ifndef SORT_H
#define SORT_H

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

/*
1. 内部排序
    1. 插入排序
        1. 直接插入排序
        2. 折半插入排序
        3. 希尔排序
    2. 交换排序
        1. 冒泡排序
        2. 快速排序
    3. 选择排序
        1. 简单选择排序
        2. 堆排序
    4. 归并排序
    5. 基数排序  
2. 外部排序
    1. 
*/

void printf_result(int *begin, int *end);
//直接插入排序
void direct_insert_sort(int *begin, int *end);
//折半插入排序
void half_insert_sort(int *begin, int *end);
//希尔排序
void shell_sort(int *begin, int *end);

//冒泡排序
void bubble_sort(int *begin, int *end);
//快速排序
void quick_sort(int *begin, int *end);

//简单选择排序
void simple_select_sort(int *begin, int *end);
//堆排序
void heap_sort(int *begin, int *end);
//调整heap的一个子树
void heap_adjust(int *begin, int *end, int seq, int len);

//归并排序
void merge_sort(int *begin, int *end);
//归并 归并low-mid mid+1-high
void merge(int *begin, int *end);

//桶排序
void bucket_sort(int *begin, int *end);
//基数排序
void radix_sort(int *begin, int *end);

#endif

sort.c

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
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
#include "sort.h"

void printf_result(int *begin, int *end)
{
    for (; begin != end; begin++)
        printf("%d ", *begin);
    printf("%d\n", *begin);
}

//直接插入排序
void direct_insert_sort(int *begin, int *end)
{
    printf("direct_insert_sort\n");
    int num = end - begin + 1;
    int *a = begin;
    for (int i = 1; i <= num - 1; i++)
    {
        //将a[i]放在前面合适的地方
        int temp = a[i];
        int j = 0;
        for (j = i - 1; j >= 0 && a[j] > temp; j--)
            a[j + 1] = a[j];
        a[j + 1] = temp;
    }
    return;
}
//折半插入排序
void half_insert_sort(int *begin, int *end)
{
    printf("half_insert_sort\n");
    int num = end - begin + 1;
    int *a = begin;
    for (int i = 1; i <= num - 1; i++)
    {
        //折半查找插入的位置
        int temp = a[i];
        int low = 0;
        int high = i - 1;
        while (low <= high)
        {
            int mid = (low + high) / 2;
            if (a[mid] > temp)
                high = mid - 1;
            else
                low = mid + 1;
        }
        for (int j = i; j >= low + 1; j--)
            a[j] = a[j - 1];
        a[low] = temp;
    }
    return;
}
//希尔排序
void shell_sort(int *begin, int *end)
{
    printf("shell_sort\n");
    int num = end - begin + 1;
    int step = num;
    int *a = begin;
    do
    {
        step /= 2;
        //分段排序 直接插入排序
        for (int start = 0; start <= step - 1; start++)
        {
            //每一段的起始位start
            for (int i = start + step; i <= num - 1; i += step)
            {
                //将a[i]放在前面合适的地方
                int temp = a[i];
                int j = start;
                for (j = i - step; j >= start && a[j] > temp; j -= step)
                {
                    a[j + step] = a[j];
                }
                a[j + step] = temp;
            }
        }
    } while (step != 1);
    return;
}
//冒泡排序
void bubble_sort(int *begin, int *end)
{
    printf("bubble_sort\n");
    int num = end - begin + 1;
    int *a = begin;
    for (int i = 0; i <= num - 2; i++)
    {
        for (int j = 0; j <= num - i - 1; j++)
        {
            if (a[j] > a[j + 1])
            {
                int temp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = temp;
            }
        }
    }
    return;
}
//快速排序
void quick_sort(int *begin, int *end)
{
    printf("quick_sort\n");
    //选择一个基准，不断地从后向前，从前向后进行交换
    int num = end - begin + 1;
    int *a = begin;
    if (num > 1)
    {
        int high = num - 1;
        int low = 0;
        int mid = a[0];
        while (low < high)
        {
            //从右向左找
            while (low < high && a[high] >= mid)
                high--;
            a[low] = a[high];
            while (low < high && a[low] <= mid)
                low++;
            a[high] = a[low];
        }
        a[low] = mid;
        quick_sort(begin, begin + low - 1);
        quick_sort(begin + low + 1, end);
    }
    return;
}

//简单选择排序
void simple_select_sort(int *begin, int *end)
{
    printf("simple_select_sort\n");
    //每一次从乱序的序列中选择一个最小的放在顺序序列的最后面。
    int num = end - begin + 1;
    int *a = begin;
    for (int i = 0; i <= num - 2; i++)
    {
        //从 i - num-i中选择一个最下的放在i
        int min_index = i;
        for (int j = i; j <= num - 1; j++)
            if (a[j] < a[min_index])
                min_index = j;
        int temp = a[i];
        a[i] = a[min_index];
        a[min_index] = temp;
    }
}
//堆排序
void heap_sort(int *begin, int *end)
{
    printf("heap_sort\n");
    int num = end - begin + 1;
    //首先建立大根堆，即对 n/2 - 1 为根的子树进行调整。
    for (int i = num / 2; i >= 0; i--)
        heap_adjust(begin, end, i, num);
    //循环输出最大值，并调整堆。
    for (int i = 0; i <= num - 1; i++)
    {
        int temp = begin[0];
        begin[0] = begin[num - i - 1];
        begin[num - i - 1] = temp;
        heap_adjust(begin, end, 0, num - i - 1);
    }
}
//调整heap的一个子树
void heap_adjust(int *begin, int *end, int seq, int len)
{
    //将树根与其最大的孩子进行交换，递归直到叶子。
    int temp = begin[seq];
    for (int i = seq * 2 + 1; i < len; i = i * 2 + 1)
    {
        //指向大的孩子
        if (i + 1 < len && begin[i] < begin[i + 1])
            i++;
        if (temp < begin[i])
        {
            begin[seq] = begin[i];
            seq = i;
        }
        else if (temp >= begin[i])
            break;
    }
    begin[seq] = temp;
}
//归并排序
void merge_sort(int *begin, int *end)
{
    int num = end - begin + 1;
    if (num > 1)
    {
        int mid = num / 2;
        merge_sort(begin, begin + mid - 1);
        merge_sort(begin + mid, end);
        merge(begin, end);
    }
}
//归并 归并low-mid mid+1-high
void merge(int *begin, int *end)
{
    //即将传进来的数组进行排序。
    int num = end - begin + 1;
    int mid = num / 2;
    // 0-mid-1 mid-end
    int num_a = mid;
    int num_b = num - mid;
    int *a = begin;
    int *b = begin + num_a;
    int *c = (int *)malloc(num * sizeof(int));
    int i = 0;
    int j = 0;
    int k = 0;
    while (i < num_a && j < num_b)
        if (a[i] <= b[j])
            c[k++] = a[i++];
        else
            c[k++] = b[j++];
    //将剩下的全部放入c中
    if (i < num_a)
        while (i < num_a)
            c[k++] = a[i++];
    else
        while (j < num_b)
            c[k++] = b[j++];
    for (k = 0; k <= num - 1; k++)
        begin[k] = c[k];
}
//桶排序
void bucket_sort(int *begin, int *end)
{
    printf("bucket_sort\n");
    //建立一个桶数组，将元素放在对应的桶中，取出。
    //就好像统计每一个元素的个数并根据该信息创造出来一个一摸一样的元素序列。
    int num = end - begin + 1;
    int max = INT_MIN;
    for (int i = 0; i <= num - 1; i++)
        if (max < begin[i])
            max = begin[i];
    int *bucket = (int *)malloc((max + 1) * sizeof(int));
    memset(bucket, 0, (max + 1) * sizeof(int));
    for (int i = 0; i <= num - 1; i++)
        bucket[begin[i]]++;
    num = 0;
    for (int i = 0; i <= max; i++)
        for (int j = 0; j <= bucket[i] - 1; j++)
            begin[num++] = i;
}
//基数排序
void radix_sort(int *begin, int *end)
{
    printf("radix_sort\n");
    //对关键字的每一位进行依次桶排序，从低位到高位。
    int num = end - begin + 1;
    int max = INT_MIN;
    for (int i = 0; i <= num - 1; i++)
        if (max < begin[i])
            max = begin[i];
    int radix[10];
    int *output = (int *)malloc(num * sizeof(int));
    for (int exp = 1; max / exp > 0; exp *= 10)
    {
        memset(radix, 0, 10 * sizeof(int));
        memset(output, 0, num * sizeof(int));
        for (int i = 0; i <= num - 1; i++) //{2, 6, 4, 1, 3, 7, 9, 45, 4, 23, 0};
            radix[(begin[i] / exp) % 10]++;
        //重组radix,令其代表其数应该在的位置。
        for (int i = 1; i <= 9; i++)
            radix[i] += radix[i - 1];
        //将排序好的数输出
        for (int i = num - 1; i >= 0; i--)
        {
            output[(radix[(begin[i] / exp) % 10]--) - 1] = begin[i];
        }
        //保存输出
        memcpy(begin, output, num * sizeof(int));
    }
}

main.c

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include "sort.c"

int main()
{
    int num[] = {2, 6, 4, 1, 3, 7, 9, 45, 4, 23, 0};
    //direct_insert_sort(num, num + 10);
    //half_insert_sort(num, num + 10);
    //shell_sort(num,num+10);
    //bubble_sort(num,num+10);
    //quick_sort(num,num+10);
    //simple_select_sort(num,num+10);
    //heap_sort(num, num + 10);
    //merge_sort(num,num+10);
    //bucket_sort(num,num+10);
    //radix_sort(num, num + 10);
    printf_result(num, num + 10);
}