算法思路
Source
Edit
History

undefined

排序

常见的排序算法：冒泡排序、插入排序、选择排序、归并排序、快速排序、计数排序、基数排序、桶排序

排序算法 时间复杂度 是否基于比较 稳定性
冒泡 n2 是 稳定
插入 n2 是 稳定
选择 n2 是 不稳定
快排 n logn 是 不稳定
归并 nlogn 是 稳定
桶排序 n 否 稳定
计数排序 n+k（k是数据范围） 否 稳定
基数排序 dn（d是维度） 否 稳定
堆排序
希尔排序

一、冒泡

冒泡排序每次操作相邻的两个元素进行比较，看是否满足大小关系，如果不满足就互换；一次冒泡至少让一个元素到达他应该的位置，重复n次，也就完成了排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 冒泡排序
// 优化，当在冒泡的时候，如果发现有一趟没有进行过数据交换，则说明已经排好序了
void bubbleSort(std::vector<int>& vec) {
    int len = vec.size();
    for (int i = 0; i < len; i++) {
        bool flag = false;
        for (int j = 0; j < len-i-1; j++) {
            if (vec[j] > vec[j+1]) {
                int tmp = vec[j];
                vec[j] = vec[j+1];
                vec[j+1] = tmp;
                flag = true;
            }
        }
        if (!flag) break;
    }
}

二、插入排序

插入排序将数组中的数据分为两个区间，已排序区间和未排序区间。初始已排序区间只有一个元素，就是数组的第一个元素。插入算法的核心思想是取未排序区间中的元素，在已排序区间中找到合适的插入位置将其插入，并保证已排序区间数据一直有序。重复这个过程，直到未排序区间中元素为空，算法结束。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void insertSort(std::vector<int>& vec) {
    for (int i = 1; i < vec.size(); i++) {
        int tmp = vec[i];
        int j = i-1;
        for (; j >= 0; j--) {
            if (tmp < vec[j]) {
                vec[j+1] = vec[j];
            } else {
                break;
            }
        }
        vec[j+1] = tmp;
    }
}

关注希尔排序

三、选择排序

不稳定、不稳定、不稳定

因为选择排序每次都要找剩余未排序元素中的最小值，并和前面的元素交换位置，这样破坏了稳定性。

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
// 选择排序
// 注意点：最大值的地方存的最小值，最小值的地方存的是最大值。造成的重复交换问题或者最值被换走的情况
void SelectSort(std::vector<int>& vec) {
    int left = 0, right = vec.size()-1;
    while (left < right) {
        int min_sub = left, max_sub = right;
        for (int i = left; i <= right; i++) {
            if (vec[min_sub] > vec[i]) {
                min_sub = i;
            }
            if (vec[max_sub] < vec[i]) {
                max_sub = i;
            }
        }
        std::swap(vec[min_sub], vec[left]);
        if (left != max_sub) {
            // left 位置存的不是最大值，那就正常换
            std::swap(vec[max_sub], vec[right]);
        } else {
            // left 位置存的是最大值，已经被换到 min_sub 位置了，因为和 min_sub 交换
            std::swap(vec[min_sub], vec[right]);
        }
        left++;
        right--;
    }
}

四、归并排序

稳定的

利用分治思想，将一个大问题分解成子问题；将一个数组分解成两个数组，在这两个数组的基础上再进行分解；而最终的子问题是两个只有一个元素的数组，对这两个元素进行排序（交换）即可；最后再将子问题进行合并。

归并排序的执行效率与要排序的原始数组的有序程度无关，所以其时间复杂度是非常稳定的，不管是最好情况、最坏情况，还是平均情况，时间复杂度都是 O(nlogn)。

1. 如何计算时间复杂度呢？

我们假设对 n 个元素进行归并排序需要的时间是 T(n)，那分解成两个子数组排序的时间都是 T(n/2)。我们知道，merge() 函数合并两个有序子数组的时间复杂度是 O(n)。所以，套用前面的公式，归并排序的时间复杂度的计算公式就是：

1
2
3
4
5
6
7
8
9
10
T(1) = C； n=1时，只需要常量级的执行时间，所以表示为C。
T(n) = 2*T(n/2) + n； n>1

T(n) = 2*T(n/2) + n
     = 2*(2*T(n/4) + n/2) + n = 4*T(n/4) + 2*n
     = 4*(2*T(n/8) + n/4) + 2*n = 8*T(n/8) + 3*n
     = 8*(2*T(n/16) + n/8) + 3*n = 16*T(n/16) + 4*n
     ......
     = 2^k * T(n/2^k) + k * n
     ......

通过这样一步一步分解推导，我们可以得到 T(n) = 2^kT(n/2^k)+kn。当 T(n/2^k)=T(1) 时，也就是 n/2^k=1，我们得到 k=log2n 。我们将 k 值代入上面的公式，得到 T(n)=Cn+nlog2n 。如果我们用大 O 标记法来表示的话，T(n) 就等于 O(nlogn)。所以归并排序的时间复杂度是 O(nlogn)。

2. 空间复杂度

尽管每次合并操作都需要申请额外的内存空间，但在合并完成之后，临时开辟的内存空间就被释放掉了。在任意时刻，CPU 只会有一个函数在执行，也就只会有一个临时的内存空间在使用。临时内存空间最大也不会超过 n 个数据的大小，所以空间复杂度是 O(n)。

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
void Merge(std::vector<int>& vec, int left1, int right1, int left2, int right2) {
    int i = 0;
    int begin = left1;
    std::vector<int> tmp(right2-left1+1, 0);
    while (left1 <= right1 && left2 <= right2) {
        if (vec[left1] < vec[left2]) {
            tmp[i++] = vec[left1++];
        } else {
            tmp[i++] = vec[left2++];
        }
    }
    while (left1 <= right1) {
        tmp[i++] = vec[left1++];
    }
    while (left2 <= right2) {
        tmp[i++] = vec[left2++];
    }
    for (int i = 0; i < tmp.size(); i++) {
        vec[begin+i] = tmp[i]; 
    }
}

void MergeSort_c(std::vector<int>& vec, int left, int right) {
    if (left >= right) return;
    int mid = left + (right-left)/2;
    MergeSort_c(vec, left, mid);
    MergeSort_c(vec, mid+1, right);
    Merge(vec, left, mid, mid+1, right);
}

// 归并排序
void MergeSort(std::vector<int>& vec) {
    MergeSort_c(vec, 0, vec.size()-1);
}

五、快速排序

不稳定、不稳定，数据的交换导致的相同元素顺序不一定一致

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int partition(std::vector<int>& vec, int left, int right) {
    int pivot = vec[right];
    int j = left;
    for (int i = left; i <= right-1; i++) {
        if (vec[i] < pivot) {
            std::swap(vec[i], vec[j]);
            j++;
        }
    }
    std::swap(vec[j], vec[right]);
    return j;
}

void QuickSort_c(std::vector<int>& vec, int left, int right) {
    if (left >= right) return;
    int pivot = partition(vec, left, right);
    QuickSort_c(vec, left, pivot-1);
    QuickSort_c(vec, pivot+1, right);
}

// 快速排序
void QuickSort(std::vector<int>& vec) {
    QuickSort_c(vec, 0, vec.size()-1);
}

时间复杂度 nlogn

1. 如何求一个数组中第K大的元素呢

使用快排的思想。快排在求 pivot 的时候，pivot 左侧的数都是小于 pivot 的，pivot 右侧的数都是大于 pivot 的，则 pivot 的值就为第 pivot 大的数。

我们选择数组区间 A[0…n-1]的最后一个元素 A[n-1]作为 pivot，对数组 A[0…n-1]原地分区，这样数组就分成了三部分，A[0…p-1]、A[p]、A[p+1…n-1]。如果 p+1=K，那 A[p]就是要求解的元素；如果 K>p+1, 说明第 K 大元素出现在 A[p+1…n-1]区间，我们再按照上面的思路递归地在 A[p+1…n-1]这个区间内查找。

我们再来看，为什么上述解决思路的时间复杂度是 O(n)？第一次分区查找，我们需要对大小为 n 的数组执行分区操作，需要遍历 n 个元素。第二次分区查找，我们只需要对大小为 n/2 的数组执行分区操作，需要遍历 n/2 个元素。依次类推，分区遍历元素的个数分别为、n/2、n/4、n/8、n/16.……直到区间缩小为 1。如果我们把每次分区遍历的元素个数加起来，就是：n+n/2+n/4+n/8+…+1。这是一个等比数列求和，最后的和等于 2n-1。所以，上述解决思路的时间复杂度就为 O(n)。

2. 快速排序的优化

如果数据原来就是有序的或者接近有序的，每次分区点都选择最后一个数据，那快速排序算法就会变得非常糟糕，时间复杂度就会退化为 O(n2)。实际上，这种 O(n2) 时间复杂度出现的主要原因还是因为我们分区点选得不够合理。

  • 优化分区算法：三数取中法

我们从区间的首、尾、中间，分别取出一个数，然后对比大小，取这 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
// 三数取中
int dealPartition(std::vector<int>& vec, int left, int right) {
    int mid = left + (right-left)/2;
    if (vec[left] > vec[mid]) {
        std::swap(vec[left], vec[mid]);
    }
    if (vec[left] > vec[right]) {
        std::swap(vec[left], vec[right]);
    }
    if (vec[mid] > vec[right]) {
        std::swap(vec[mid], vec[right]);
    }
    std::swap(vec[mid], vec[right]);
    return vec[right];
}

// 快速排序优化：使用三数取中法得到 partition 位置
int partition_2(std::vector<int>& vec, int left, int right) {
    int pivot = dealPartition(vec, left, right);
    int j = left;
    for (int i = left; i <= right-1; i++) {
        if (pivot > vec[i]) {
            std::swap(vec[i], vec[j]);
            j++;
        }
    }
    std::swap(vec[j], vec[right]);
    return j;
}

void QuickSort_c(std::vector<int>& vec, int left, int right) {
    if (left >= right) return;
    int pivot = partition_2(vec, left, right);
    QuickSort_c(vec, left, pivot-1);
    QuickSort_c(vec, pivot+1, right);
}

// 快速排序
void QuickSort(std::vector<int>& vec) {
    QuickSort_c(vec, 0, vec.size()-1);
}

3. 思考题目

  • 现在你有 10 个接口访问日志文件，每个日志文件大小约 300MB，每个文件里的日志都是按照时间戳从小到大排序的。你希望将这 10 个较小的日志文件，合并为 1 个日志文件，合并之后的日志仍然按照时间戳从小到大排列。如果处理上述排序任务的机器内存只有 1GB，你有什么好的解决思路，能“快速”地将这 10 个日志文件合并吗？

合并归并的思路

六、桶排序

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

如果要排序的数据有 n 个，我们把它们均匀地划分到 m 个桶内，每个桶里就有 k=n/m 个元素。每个桶内部使用快速排序，时间复杂度为 O(k * logk)。m 个桶排序的时间复杂度就是 O(m * k * logk)，因为 k=n/m，所以整个桶排序的时间复杂度就是 O(n*log(n/m))。当桶的个数 m 接近数据个数 n 时，log(n/m) 就是一个非常小的常量，这个时候桶排序的时间复杂度接近 O(n)。

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

桶排序适合外部排序，所谓的外部排序就是数据存储在外部磁盘中，数据量比较大，内存有限，无法将数据全部加载到内存中。

1. 例子

  • 比如说我们有 10GB 的订单数据，我们希望按订单金额（假设金额都是正整数）进行排序，但是我们的内存有限，只有几百 MB，没办法一次性把 10GB 的数据都加载到内存中。这个时候该怎么办呢？
  • 借助桶排序的处理思想来解决这个问题。我们可以先扫描一遍文件，看订单金额所处的数据范围。假设经过扫描之后我们得到，订单金额最小是 1 元，最大是 10 万元。我们将所有订单根据金额划分到 100 个桶里，第一个桶我们存储金额在 1 元到 1000 元之内的订单，第二桶存储金额在 1001 元到 2000 元之内的订单，以此类推。每一个桶对应一个文件，并且按照金额范围的大小顺序编号命名（00，01，02…99）。理想的情况下，如果订单金额在 1 到 10 万之间均匀分布，那订单会被均匀划分到 100 个文件中，每个小文件中存储大约 100MB 的订单数据，我们就可以将这 100 个小文件依次放到内存中，用快排来排序。等所有文件都排好序之后，我们只需要按照文件编号，从小到大依次读取每个小文件中的订单数据，并将其写入到一个文件中，那这个文件中存储的就是按照金额从小到大排序的订单数据了。不过，你可能也发现了，订单按照金额在 1 元到 10 万元之间并不一定是均匀分布的 ，所以 10GB 订单数据是无法均匀地被划分到 100 个文件中的。有可能某个金额区间的数据特别多，划分之后对应的文件就会很大，没法一次性读入内存。这又该怎么办呢？针对这些划分之后还是比较大的文件，我们可以继续划分，比如，订单金额在 1 元到 1000 元之间的比较多，我们就将这个区间继续划分为 10 个小区间，1 元到 100 元，101 元到 200 元，201 元到 300 元….901 元到 1000 元。如果划分之后，101 元到 200 元之间的订单还是太多，无法一次性读入内存，那就继续再划分，直到所有的文件都能读入内存为止。

七、计数排序

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

// 计数排序，a是数组，n是数组大小。假设数组中存储的都是非负整数。
public void countingSort(int[] a, int n) {
  if (n <= 1) return;

  // 查找数组中数据的范围
  int max = a[0];
  for (int i = 1; i < n; ++i) {
    if (max < a[i]) {
      max = a[i];
    }
  }

  int[] c = new int[max + 1]; // 申请一个计数数组c，下标大小[0,max]
  for (int i = 0; i <= max; ++i) {
    c[i] = 0;
  }

  // 计算每个元素的个数，放入c中
  for (int i = 0; i < n; ++i) {
    c[a[i]]++;
  }

  // 依次累加
  for (int i = 1; i <= max; ++i) {
    c[i] = c[i-1] + c[i];
  }

  // 临时数组r，存储排序之后的结果
  int[] r = new int[n];
  // 计算排序的关键步骤，有点难理解
  for (int i = n - 1; i >= 0; --i) {
    int index = c[a[i]]-1;
    r[index] = a[i];
    c[a[i]]--;
  }

  // 将结果拷贝给a数组
  for (int i = 0; i < n; ++i) {
    a[i] = r[i];
  }
}

计数排序只能用在数据范围不大的场景中，如果数据范围 k 比要排序的数据 n 大很多，就不适合用计数排序了。而且，计数排序只能给非负整数排序，如果要排序的数据是其他类型的，要将其在不改变相对大小的情况下，转化为非负整数。

八、基数排序

比如 10w 个手机号码，可以先排序第一位，在排第二位；依次向后。如果遇到长度不一样，则可以补齐一样长。

1
基数排序对要排序的数据是有要求的，需要可以分割出独立的“位”来比较，而且位之间有递进的关系，如果 a 数据的高位比 b 数据大，那剩下的低位就不用比较了。除此之外，每一位的数据范围不能太大，要可以用线性排序算法来排序，否则，基数排序的时间复杂度就无法做到 O(n) 了。

九、qsort 的实现

  1. 对于小数据量的排序使用归并排序，典型的空间换时间
  2. 排序数据量较大时使用快速排序，而且使用三数取中法选择分区节点
  3. qsort 用于递归的栈是自己实现的，防止堆栈溢出
  4. 当元素数量小于等于4时，qsort 退化为插入排序