数据结构与算法-线性排序

Posted on | Edited on | In ,

线性排序

因为下面几种排序的事件复杂度接近O(n)，所以我们称其为线性排序

桶排序

将数据有小到达分成m个桶，每个桶内n个元素，然后分别对每个桶进行快速排序，由于桶是有序的，所以在排序完成后不用在排序了。

时间复杂度分析

最好时间复杂度

1
每个桶元素是n/m=>O(m * n/m * logn/m)=>O(n*logn/m)，假设到m和n接近时候，时间复杂度是O(n)

最坏时间复杂度：当几乎所有数据都几种在一个桶内时候，复杂度会退化为O(nlogn)

桶排序的试用场景：外部排序

比如有一个10G的用户数据的文件，对某一项属性排序，内存只有几百MB，我们无法将数据都加载到内存中，我们可以利用桶排序，先扫描文件确认属性的范围，将属性分为m个范围，并且分为m个文件，分别将数据插入到这些文件中，之后对这些文件分别排序。当然如果遇到分布不均匀的情况还要继续划分。

如：比如用户10个GB的订单文件，按照金额排序。

计数排序

代码如下：

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

public int[] sort(int[] a) {
    //查找最大值
    int max = getMax(a);
    int[] countArray = new int[max + 1];

    //分桶（申请一个数组），从0---max每个值一个桶，并且做累加
    for (int i = 0; i < a.length; i++) {
        countArray[a[i]] = countArray[a[i]] + 1;
    }

    //遍历桶给桶做累加，记录从min-->max，每个值包含他之前的值总共有多少个，用于后面的排序
    int sum = countArray[0];
    for (int i = 1; i < countArray.length; i++) {
        sum += countArray[i];
        countArray[i] = sum;
    }

    //申请额外空间
    int[] ret=new int[a.length];
    //轮询要排序数组a,a的值就是桶的下标。
    // 1.找到a[i]在countArray中对应的count值；
    // 2.这个(count-1)值对应的是排序之后数组的该值的index，将a[i]插入到新数组的ret[count-1]
    // 3.count--;
    for (int i = 0; i < a.length; i++) {
        int v = a[i];
        int count = countArray[v]-1;
        ret[count] = v;
        countArray[v] =count;
    }

    return ret;
}

private int getMax(int[] a) {
    int ret = a[0];
    for (int i = 1; i < a.length; i++) {
        if (ret <= a[i]) {
            ret = a[i];
        }
    }
    return ret;
}

思路如图：
avator

  1. 找到原数组最大值，申请一个countArray[max+1]
  2. 记录countArray中记录原数组a的每个值的个数，并且对countArray数组每一项求和。这个值就是排序之后的每个元素的下标最大值+1。（意思是这个元素在排序之后的数组中包含他的位置）
  3. 遍历数组a,取v=a[i]的值，取countArray中的count，然后v插入到排序后的数组r的count-1中。

适用场景

  1. 只能给正整数排序
  2. 只能给范围不大的数组排序，比如范围k比数组n大很多那就不合适了