发表更新【算法】 / 数据结构与算法0次访问

排序算法(1)

排序算法在整个算法体系中属于比较基础的知识，以致于大多数人并没有意识到它对于构建当今计算机庞大技术体系所发挥的巨大作用。

对于很多算法问题而言，要想直接找到更小时间复杂度的方案非常困难，但是一旦将数据排好序，问题就会迎刃而解，所以排序算法扮演着算法基石的作用。

计算机科学家们很早就开始研究各种排序算法，排序算法时间复杂度的每一次微小降低，都会在计算机世界引起轰动。

概述

分类

  • 内排序 & 外排序：待排序数据是否都在内存中
  • 原址排序 & 非原址排序：是否需要辅助空间（允许常量辅助空间，比如交换元素时的辅助变量）
  • 稳定排序 & 非稳定排序：相等的数在在排序后相对位置是否会发生变化
  • 比较排序 & 非比较排序：比较排序最好的时间复杂度是O(nlogn)

具体算法

排序算法很多，大家谈论比较多的、也是学生时代必学的排序算法主要有：冒泡排序、选择排序、插入排序、希尔排序、归并排序、堆排序、快速排序、计数排序、基数排序、桶排序等。本文会对它们一一介绍。

当今世界，数据量呈现爆炸式增长，外部排序能有效解决超大规模数据的排序问题，有必要一窥其究竟。

在经典语言标准库中，排序并不是简单使用上述某种方案，更多是结合多种排序算法的优点改造形成，本文也会对这进行适当扩展。

时间复杂度O(n2)

冒泡排序

冒泡排序是最直观的排序方式，存在若干优化：

  • 如果一趟下来没有发生元素交换，则说明数组有序，停止排序。
  • 最后没有发生交换的元素是有序的，不用在下一趟比较重进行元素交换。
  • 可以同时进行顺向和逆向的对比交换，以解决不对称的局部无序情况。

以下代码仅展示第一步优化。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void BubbleSort(int data[], int n) {
  if (n == 1) return;
  
  for (int i = 0; i <= n - 2; i++) {
    // 定义一个布尔类型的标识符，指示数组是否有序
    int flag = 1;
    for (int j = 0; j <= n - 2 - i; j++) {
      if (data[j] > data[j + 1]) {
        int temp = data[j];
        data[j] = data[j + 1];
        data[j + 1] = temp;
        // 一旦有交换说明数组可能无序
        if (flag == 1) flag = 0;
      }
    }
    // 如果有序则不进行接下来的换位
    if (flag) break;
  }
}

选择排序

选择排序每次选择未排序元素的最小者，交换到前面。

1
2
3
4
5
6
7
8
9
10
11
12
13
void SelectSort(int data[], int n) {
  for (int i = 0; i < n - 1; i++) {
    int index = i;
    for (int j = i + 1; j < n; j++)
      if (data[j] < data[index])
        index = j;
    if (index != i) {
      int temp = data[index];
      data[index] = data[i];
      data[i] = temp;
    }
  }
}

插入排序

插入排序每次将未排序元素的第一个向前插入到合适的位置。

1
2
3
4
5
6
7
8
9
10
11
void InsertSort(int data[], int n) {
  for (int i = 1; i < n; i++) {
    if (data[i] >= data[i - 1]) continue;
    
    int temp = data[i];
    int j;
    for (j = i - 1; j >= 0 && temp < data[j]; j--)
      data[j + 1] = data[j];
    data[j + 1] = temp;
  }
}

时间复杂度O(nlogn)~O(n2)

希尔排序

希尔排序基于一个增量数组（增量数组的最后一个元素是1），每一个增量都对应一趟插入排序。

增量序列选取非常关键，理论上最后一个增量为1的序列都可以，希尔增量比较简单，增量元素依次折半，本文采用该方法。

很多研究给出了高效希尔排序的增量序列，主要有Hibbard增量和Sedgewick增量，后者的时间复杂度更小。

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
void ShellSort(int data[], int n) {
  // 求shell序列
  int *delta = (int*)malloc(sizeof(int) * (n / 2));
  int k = n;
  int i = 0;
  while (k > 0) {
    k /= 2;
    delta[i++] = k;
  }
  
  i = 0;
  int dk;
  while ((dk = delta[i++]) > 0) {
    for (k = dk; k < n; ++k) {
      if (data[k] >= data[k - dk]) continue;
      int t = data[k];
      int j;
      for (j = k - dk; j >= 0 && t < data[j]; j -= dk)
        data[j + dk] = data[j];
      data[j + dk] = t;
    }
  }
  // 释放增量数组
  free(delta);
}

时间复杂度O(nlogn)

归并排序

归并排序基于分治思想，每次将数组从中间划分成两个数组，将两个数组分别排序后再合并成一个有序数组。

核心算法：两个有序数组的归并，需要依赖一个同等大小的临时数组。

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
void MSort(int data[], int left, int right) {
  if (left >= right) return;
  int n = right - left + 1;
  
  int center = (left + right) / 2;
  MSort(data, left, center);
  MSort(data, center + 1, right);
  
  // 两个有序数组的合并（以下是最容易理解的方式）
  int *tempArray = (int*)malloc(sizeof(int) * n);
  int l = left, r = center + 1;
  for (int i = 0; i < n; i++) {
    if (l > center)
      tempArray[i] = data[r++];
    else if (r > right)
      tempArray[i] = data[l++];
    else if (data[l] < data[r])
      tempArray[i] = data[l++];
    else
      tempArray[i] = data[r++];
  }
  free(tempArray);
}

void MergeSort(int data[], int n) {
  if (n <= 1) return;
  MSort(data, 0, n - 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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
// 下沉操作
void Sink(int data[], int n, int index) {
  if (index < 0 || index >= n)
    return;
  
  for (int j = index; 2 * j + 1 < n;) {
    // 有左、右儿子
    if (2 * j + 2 < n) {
      if (data[j] >= data[2 * j + 1] && data[j] >= data[2 * j + 2])
        break;
      
      if (data[2 * j + 1] >= data[2 * j + 2] ) {
        swap(&data[2 * j + 1], &data[j]);
        j = 2 * j + 1;
      } else {
        swap(&data[2 * j + 2], &data[j]);
        j = 2 * j + 2;
      }
    }
    // 只有左儿子
    else {
      if (data[j] < data[2 * j + 1])
        swap(&data[2 * j + 1], &data[j]);
      // 这是关键，容易疏忽
      j = 2 * j + 1;
    }
  }
}

// 构建大根堆（升序排序）
void BuildHeap(int data[], int n) {
  // 对所有非叶节点逆序进行下滤操作
  for (int i = (n - 2) / 2; i >= 0; i--)
    Sink(data, n, i);
}

void HeapSort(int data[], int n) {
  // 构建大根堆
  BuildHeap(data, n);
  
  // 开始排序
  for (int i = n - 1; i > 0; i--) {
    swap(&data[0], &data[i]);
    Sink(data, i, 0);
  }
}

从感性角度理解下沉和上浮操作，是深入掌握堆这种数据结构的关键：

  • 从无序数组构建堆时，对非叶节点进行逆序下沉，从而保证每一条根到叶的路径都是有序的，这里等同于多路插入排序。
  • 当堆有序时，如果破坏了堆序，就需要进行恢复。通用情况是，任何一个元素发生了变化，视其大小进行上浮和下沉即可恢复。

快速排序

快速排序基于分治思想，对一个数组排序时先选择一个枢纽元，按照该枢纽元将数组分成两部分；再采用相同的方式对两部分进行排序。

核心算法：基于枢纽元的数组分割。

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
void QSort(int data[], int left, int right) {
  int n = right - left + 1;
  if (n <= 1) return;
  if (n == 2) {
    if (data[left] > data[right])
      swap(&data[left], &data[right]);
    return;
  }
  
  // 计算枢轴元，采用三值取中值的方式
  int center = (left + right) / 2;
  if (data[left] > data[center])
    swap(&data[left], &data[center]);
  if (data[left] > data[right])
    swap(&data[left], &data[right]);
  if (data[center] > data[right])
    swap(&data[center], &data[right]);
  swap(&data[center], &data[right - 1]);
  int pivot = data[right - 1];
  
  // 数组分割
  int l = left;
  int r = right - 1;
  while (1) {
    while (data[++l] < pivot) {}
    while (data[--r] > pivot) {}
    if (l < r)
      swap(&data[l], &data[r]);
    else
      break;
  }
  swap(&data[l], &data[right - 1]);
  
  // 对划分的两个子数组进行排序
  QSort(data, left, l - 1);
  QSort(data, l + 1, right);
}

void QuickSort(int data[], int n) {
  QSort(data, 0, n - 1);
}

评论

分类

×