Xi's Blog
0%

排序算法

发表于 更新于 分类于 ，

课程笔记：一些比较重要的排序算法。
基于比较的排序的时间复杂度最优是$O(nlogn)$，而后面三个不基于比较的排序可以超越这个限制.

1. Merge Sort

  1. 将单带上的数据根据run分散到K个带上，需$O(N)$时间
  2. 在一个长度为K的数组上建立最小堆
  3. 循环，对于每个带的第i个run，采用MergeSort排序后写到一个另外的tape上（因此总共需要2K个tape）
  1. Create sorted runs
    1. Read M blocks
    2. Sort M blocks in memory
    3. Write data into a run
  2. Merge the runs (K-way merge)
    1. K input buffers, 1 output buffer
    2. Repeat
      1. Select the first record in input buffer in sort order
      2. Write the record to the output buffer. If the output buffer is full, write to the disk.
      3. Delete the record in the buffer and read next block of the run into buffer.

1.1 使用斐波那契数列

上面第一步中将单带数据分散到两个tape并且两个tape的run数是相邻斐波那契数，如果凑不出来，那么填充一些

1.2 Huffman Tree

Minimize the merge time

用sequence的长度作为huffman tree节点的权重。这样

$$
TotalMergeTime=O(TheWeightedExternalPathLength)
$$

2.1 Counting Sort

  • 数据长度为n，key有k个可能的取值
  • 时间复杂度$O(n+k)$，但是如果key的有效取值范围很大会导致空间消耗巨大，因此只适合在key可能取值少的情况下使用。
  • 是一个稳定的排序
1
2
3
4
5
6
7
8
9
c[k] and initialized to be 0
for key in keys:
	c[key]++
for i = 1 to k:
	c[i] = c[i - 1] + c[i]
for j = len(keys) - 1 downto 1:
	b[c[keys[j]] - 1] = keys[j]
	c[keys[j]]--
# 最终数据就在b中

2.2 Radix Sort

  • 不同于Counting Sort和Bucket Sort，没有对数据的分布和特征做出假设，比较通用。
  • 对每一位进行稳定的排序，由于key很少（十进制，只有十个可能取值），此处可以用计数排序
    在使用计数排序的情况下，时间复杂度是$\Theta(d(n+k))$，空间消耗取决于计数排序

2.3 Bucket Sort

  • 只要在桶中元素数目的平方和的期望和排序元素个数呈线性关系，可以在线性时间内完成排序。也就是说数据需要尽可能均匀分布
  • 桶数组有点像open address hash table中的hash数组，桶内元素用链表（是不是也可以用别的？）连接
  • 需要将所有的key映射到0-1区间
1
2
3
4
5
6
初始化buckets，需要n个slots
for v in array:
	insert v into buckets[floor(n * v)]
for bucket in buckets:
	sort bucket using insertion sort
concatenate buckets together in order