explorer

万丈高楼平地起,勿在浮沙筑高台

0%

[What]数据结构与算法 -> 线性排序

课程:王争 –> <数据结构与算法之美>

整理常用的几种排序算法。

算法 时间复杂度 是否基于比较
冒泡、插入、选择 O(n ^ 2)
快排、归并 O(nlogn)
桶、计数、基数 O(n)

桶、计数、基数排序的时间复杂度都是O(n),因为这些排序算法的时间复杂度是线性的,所以称为线性排序。

这三个算法都不涉及元素之间的比较操作,但对要排序的数据有一定要求。

桶排序(Bucket sort)

概念

桶排序的核心思想:将要排序的数据分到几个有序的桶里,每个桶里的数据再单独进行排序。桶内排序完毕后,再把桶里的数据按照顺序依次取出,最终的序列就是有序的了。

桶排序对数据有以下要求:

  1. 要排序的数据需要很容易就能划分成多个桶, 并且桶与桶之间有着天然的大小顺序 , 这样每个桶内的数据都排序完之后,桶与桶之间的数据不需要再进行排序。
  2. 数据在各个桶之间的分布是比较均匀的。如果数据经过桶划分之后,有些桶里的数据非常多,有些非常少,那桶内数据排序的时间复杂度就不是常量级了。
    • 如果数据都被划分到一个桶里,那就退化为O(nlogn)的时间复杂度了。

桶排序适用于外部排序的场景:数据存储在外部磁盘,数据量太大而无法全部加载到内存中。

假设要对10G的外部数据进行排序,但内存只有几百兆,那么思路如下:
1. 扫描外部数据获取其数据范围
2. 依据数据范围将它们依次划分为n个桶,桶是按照大小顺序排列的
  - 在划分桶的过程中,都是使用元数据来表示桶的排列的(不会占用很大内存)
  - 数据一般不会均匀分布,所以对于一部分数据特别集中的桶,需要将其再划分为更小的桶
3. 按照桶的顺序依次将一个桶的数据读入内存,进行快速排序,完成后将此桶内存写回硬盘
4. 当步骤3执行完毕后,一个大文件也就排好序了

简易的示例代码如下:

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
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h>

#define BUF_SIZE (10)
static int buf[BUF_SIZE];

#define BUCKET_SIZE_MAXIMUM (4)
typedef struct
{
int *buf;
int size;
int start;
int end;
int index;
}bucket_t;

static void swap(int *a, int *b)
{
int tmp = *a;
*a = *b;
*b = tmp;
}

static int partition(int *buf, int p, int r)
{
int i = p;

for(int j = p; j <= r - 1; j++)
{
if(buf[j] < buf[r])
{
if(i != j)
{
swap(&buf[j], &buf[i]);
}
i++;
}
}

swap(&buf[i], &buf[r]);

return i;
}

static void quick_sort_frame(int *buf, int p, int r)
{
if(p >= r)
{
return ;
}
int q = partition(buf, p, r);

printf("quick_sort p = %d, r = %d, q = %d\n", p, r, q);
for(int i = p; i <= r; i++)
{
printf("%d,", buf[i]);
}
printf("\n");
quick_sort_frame(buf, p, q - 1);
quick_sort_frame(buf, q + 1, r);
}
static void quick_sort(int *buf, int size)
{
quick_sort_frame(buf, 0, size - 1);
printf("quick sort:\n");
for(int i = 0; i < size; i++)
{
printf("%d,", buf[i]);
}
printf("\n");
}
static void bucket_sort(int *buf, int size)
{
int minimum = buf[0];
int maximum = buf[0];

for(int i = 1; i < size; i++)
{
if(minimum > buf[i])
{
minimum = buf[i];
}
else if(maximum < buf[i])
{
maximum = buf[i];
}
}
printf("get buffer minimum = %d, maximum = %d\n", minimum, maximum);

int bucket_cnt = size / BUCKET_SIZE_MAXIMUM;
int remain = size % BUCKET_SIZE_MAXIMUM;

if(remain)
{
bucket_cnt += 1;
}
printf("we need %d buckets\n", bucket_cnt);

bucket_t buckets[bucket_cnt];
int start_index = minimum;
for(int i = 0; i < bucket_cnt; i++)
{
int malloc_cnt = BUCKET_SIZE_MAXIMUM;
if((i == bucket_cnt - 1) && (remain != 0))
{
malloc_cnt = remain;
}
buckets[i].buf = (int *)malloc(malloc_cnt * sizeof(int));
assert(buckets[i].buf);
buckets[i].size = malloc_cnt;
buckets[i].start = start_index;
buckets[i].end = start_index + buckets[i].size - 1;
buckets[i].index = 0;
start_index += buckets[i].size;
printf("bucket -> %d, start = %d,end = %d, size = %d\n",
i, buckets[i].start, buckets[i].end,buckets[i].size);
}

int buf_index = 0;
for(int i = 0; i < size; i++)
{
for(int j = 0; j < bucket_cnt; j++)
{
if((buf[i] <= buckets[j].end) && (buf[i] >= buckets[j].start))
{
buf_index = j;
break;
}
}
buckets[buf_index].buf[buckets[buf_index].index++] = buf[i];

printf("bucket %d -> index %d = %d\n",
buf_index, buckets[buf_index].index - 1, buf[i]);
}

int *buf_addr = buf;
for(int i = 0; i < bucket_cnt; i++)
{
quick_sort(buckets[i].buf, buckets[i].size);
memcpy(buf_addr, buckets[i].buf, buckets[i].size * sizeof(int));
buf_addr += buckets[i].size;

free(buckets[i].buf);
}
}

int main(int argc, char *argv[])
{
printf("buffer contents:\n");
for(int i = BUF_SIZE; i > 0; i--)
{
buf[BUF_SIZE - i] = i;
printf("%d,", buf[BUF_SIZE - i]);
}
printf("\n");

bucket_sort(buf, BUF_SIZE);

printf("buffer contents:\n");
for(int i = 0; i < BUF_SIZE; i++)
{
printf("%d,", buf[i]);
}
printf("\n");
return 0;
}

分析

时间复杂度

理想情况下:

  • n个数据被均分到m个桶内,每个桶内就有 k=n/m 个元素。
  • 每个桶都使用快速排序,其时间复杂度为O(klogk),那么m个桶就为 O(m*(n/m)*log(n/m)) ==> O(n*log(n/m))
  • 去掉低阶,就是O(n)

计数排序(Counting sort)

概念

计数排序是桶排序的一种特殊情况,当要排序的数据范围不大的时候,可以根据最大值k划分为k个桶,并且桶内也不需要排序了,最终数据读出后就是有序的。

其实现思想如下:

  1. 将值转换为从0开始的非负整数。
    • 比如原来有负数,那么统一加上一个偏移。如果带有小数点,则乘为整数,并加偏移。
  2. 扫描一次数组a,得出其最大值。
  3. 根据最大值k创建数组c[k+1]
  4. 遍历数据,将对应值的个数存入数组c(计数)
  5. 对数组c顺序求和,得出小于或等于对应值的数据个数
  6. 反向扫描数组a,并取出其对应数组c处的值,也就是小于或等于该值的个数。根据此个数放入数组r的对应下标处减一,且数组c的对应计数值减一
  7. 最终将数组r的值拷贝进数组a便完成了排序

示例代码如下:

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
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

static void count_sort(int *buf, int size)
{
int maximum = buf[0];

for(int i = 1; i < size; i++)
{
if(maximum < buf[i])
{
maximum = buf[i];
}
}
int count_size = maximum + 1;
int c[count_size] ;

memset(c, 0, count_size * sizeof(int));

for(int i = 0; i < size; i++)
{
c[buf[i]] += 1;
}

for(int i = 1; i < count_size; i++)
{
c[i] = c[i] + c[i - 1];
}

int r[size];
for(int i = size - 1; i >= 0; i--)
{
int val = c[buf[i]] - 1;
r[val] = buf[i];
c[buf[i]]--;
}
memcpy(buf, r, size * sizeof(int));
}
int main(int argc, char *argv[])
{
int buf[] = {2, 5, 3, 0, 2, 3, 0, 3};

printf("buffer before sort:\n");
for(int i = 0; i < sizeof(buf)/ sizeof(buf[0]); i++)
{
printf("%d,", buf[i]);
}
printf("\n");
count_sort(buf, sizeof(buf) / sizeof(buf[0]));

printf("buffer contents:\n");
for(int i = 0; i < sizeof(buf)/ sizeof(buf[0]); i++)
{
printf("%d,", buf[i]);
}
printf("\n");
return 0;
}

分析

时间复杂度

由于整个过程只涉及对数组的多次遍历操作,去掉其系数得出时间复杂度为O(n).

空间复杂度

在操作过程中,最大会申请n大小的数组,所以其空间复杂度也是O(n).

基数排序(Radix sort)

概念

在对一堆数据值很大排序的情况下(比如对电话号码进行排序),可以将数值的每一位从低到高依次进行排序(比如计数排序),这样最终的数据就是有序的了。

  • 排序时使用的算法必须是稳定排序算法,不能破坏已有排序的顺序
  • 当数据长短不一时,可以采取高位或地位补0的措施进行对齐
  • 数据的位与位之间有递进关系。

分析

时间复杂度

当使用计数排序时,每次排序的复杂度为O(n),数据有m位的话那就是O(m*n)

空间复杂度

每次排序的空间复杂度为O(n),但增加的空间并不会随着位数的增加而累计,所以其最终的空间复杂度也是O(n)

Last Updated 2021-01-26 二 12:13.
Render by hexo-renderer-org with Emacs 26.3 (Org mode 9.4)