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

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

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

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

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

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

桶排序(Bucket sort)

概念

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

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

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

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

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

简易的示例代码如下:

#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便完成了排序

示例代码如下:

#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 2018-12-30 Sun 22:13.
Render by hexo-renderer-org with Emacs 26.1 (Org mode 9.1.14)