排序
排序
在数据结构中，排序（Sorting）指的是将一个数据集合中的元素按指定顺序重新排列的过程。排序是计算机科学的基本操作之一，对数据处理和分析具有重要作用。排序的结果通常是按从小到大（升序）或从大到小（降序）排列的有序序列。
排序的基本概念
内部排序和外部排序：
- 内部排序：数据量较小，能够将所有待排序的记录一次性加载到内存中完成排序。
- 外部排序：数据量较大，无法一次加载到内存中，需要借助外存（如硬盘）分批次处理并排序。
稳定性：
- 稳定排序：若两个相等的元素在排序前后的相对位置不变，则排序算法是稳定的。例如，若记录有相同的键值，稳定排序会保持它们的初始顺序。
- 不稳定排序：可能会改变相等元素的相对位置。
时间复杂度：排序算法的时间复杂度通常以 $O(n^2)$ 或 $O(n \log n)$ 为主，决定了其在不同规模数据上的效率。
空间复杂度：算法在排序过程中额外占用的存储空间。部分排序算法只需少量辅助空间（如原地排序），而有些则需要较多的辅助空间。
排序算法的适用场景：根据数据量、数据特性（如是否近似有序）以及稳定性要求，选择合适的排序算法。
常见的排序算法及其特性
1. 冒泡排序（Bubble Sort）：
- 基本思想：通过重复遍历待排序的序列，依次比较相邻元素，将较大或较小的元素向后交换。
- 时间复杂度：$O(n^2)$
- 特点：简单但效率低，适用于数据量小的情况。
- 稳定性：稳定
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
void bubbleSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
bool swapped = false; // 用于检测是否发生交换
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
// 交换 arr[j] 和 arr[j + 1]
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true;
}
}
// 如果在一轮遍历中没有发生交换，说明数组已排序
if (!swapped) {
break;
}
}
}
int main() {
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr) / sizeof(arr[0]);
bubbleSort(arr, n);
std::cout << "Sorted array: ";
for (int i = 0; i < n; i++) {
std::cout << arr[i] << " ";
}
std::cout << std::endl;
return 0;
}
2. 选择排序（Selection Sort）：
- 基本思想：每次从未排序部分选择最小（或最大）元素，放在已排序部分的末尾。
- 时间复杂度：$O(n^2)$
- 特点：减少了交换次数，但依然不适合大型数据。
- 稳定性：不稳定
3. 插入排序（Insertion Sort）：
- 基本思想：将待排序数据分成已排序和未排序两部分，逐个将未排序元素插入已排序部分的正确位置。
- 时间复杂度：$O(n^2)$
- 特点：适用于小规模或近乎有序的序列。
- 稳定性：稳定
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
void insertionSort(int arr[], int n) {
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
// 将当前元素插入到已排序部分
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}
int main() {
int arr[] = {12, 11, 13, 5, 6};
int n = sizeof(arr) / sizeof(arr[0]);
insertionSort(arr, n);
std::cout << "Sorted array: ";
for (int i = 0; i < n; i++) {
std::cout << arr[i] << " ";
}
std::cout << std::endl;
return 0;
}
4. 归并排序（Merge Sort）：
- 基本思想：采用分治法，将数据分成子序列分别排序，再将有序子序列合并为完整序列。
- 时间复杂度：$O(n \log n)$
- 特点：效率高，适用于大型数据集，但需要额外存储空间。
- 稳定性：稳定
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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
void merge(int arr[], int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
// 创建临时数组
int* leftArr = new int[n1];
int* rightArr = new int[n2];
// 拷贝数据到临时数组
for (int i = 0; i < n1; i++)
leftArr[i] = arr[left + i];
for (int j = 0; j < n2; j++)
rightArr[j] = arr[mid + 1 + j];
// 合并临时数组到原数组
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (leftArr[i] <= rightArr[j]) {
arr[k] = leftArr[i];
i++;
} else {
arr[k] = rightArr[j];
j++;
}
k++;
}
// 拷贝剩余元素（如果有）
while (i < n1) {
arr[k] = leftArr[i];
i++;
k++;
}
while (j < n2) {
arr[k] = rightArr[j];
j++;
k++;
}
// 释放临时数组
delete[] leftArr;
delete[] rightArr;
}
void mergeSort(int arr[], int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
// 递归排序左右两部分
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
// 合并排序后的两部分
merge(arr, left, mid, right);
}
}
int main() {
int arr[] = {12, 11, 13, 5, 6, 7};
int n = sizeof(arr) / sizeof(arr[0]);
mergeSort(arr, 0, n - 1);
std::cout << "Sorted array: ";
for (int i = 0; i < n; i++) {
std::cout << arr[i] << " ";
}
std::cout << std::endl;
return 0;
}
5. 快速排序（Quick Sort）：
- 基本思想：同样采用分治法，通过选择一个基准元素将数组分为两部分，再对每部分递归排序。
- 时间复杂度：平均 $O(n \log n)$，最差 $O(n^2)$
- 特点：通常比其他排序算法快，适合大型数据集，但对有序数组性能不佳。
- 稳定性：不稳定
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 swap(int& a, int& b) {
int temp = a;
a = b;
b = temp;
}
int partition(int arr[], int low, int high) {
int pivot = arr[high]; // 选择最后一个元素作为枢轴
int i = low - 1; // i 是较小元素的索引
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
swap(arr[i], arr[j]); // 将较小的元素交换到前面
}
}
swap(arr[i + 1], arr[high]); // 将枢轴放到正确位置
return i + 1; // 返回枢轴的索引
}
void quickSort(int arr[], int low, int high) {
if (low < high) {
int pi = partition(arr, low, high); // 获取分区索引
quickSort(arr, low, pi - 1); // 递归排序左半部分
quickSort(arr, pi + 1, high); // 递归排序右半部分
}
}
int main() {
int arr[] = {10, 7, 8, 9, 1, 5};
int n = sizeof(arr) / sizeof(arr[0]);
quickSort(arr, 0, n - 1);
std::cout << "Sorted array: ";
for (int i = 0; i < n; i++) {
std::cout << arr[i] << " ";
}
std::cout << std::endl;
return 0;
}
6. 堆排序（Heap Sort）：
- 基本思想：利用堆这种数据结构进行排序，将数组构建成最大堆或最小堆，逐步取出堆顶元素排序。
- 时间复杂度：$O(n \log n)$
- 特点：时间复杂度稳定，但不适合小规模数据。
- 稳定性：不稳定
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
47
48
49
50
51
52
53
54
// 将节点 i 及其子树调整为最大堆
void heapify(int arr[], int n, int i) {
int largest = i; // 将当前节点 i 设为最大值
int left = 2 * i + 1; // 左子节点
int right = 2 * i + 2; // 右子节点
// 如果左子节点大于当前最大值
if (left < n && arr[left] > arr[largest]) {
largest = left;
}
// 如果右子节点大于当前最大值
if (right < n && arr[right] > arr[largest]) {
largest = right;
}
// 如果最大值不是当前节点，则交换并递归调整
if (largest != i) {
std::swap(arr[i], arr[largest]);
heapify(arr, n, largest);
}
}
// 主堆排序函数
void heapSort(int arr[], int n) {
// 建立最大堆
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(arr, n, i);
}
// 逐一提取元素，重建最大堆
for (int i = n - 1; i > 0; i--) {
std::swap(arr[0], arr[i]); // 将堆顶元素移到数组末尾
heapify(arr, i, 0); // 对剩余的元素重新进行堆化
}
}
int main() {
int arr[] = {12, 11, 13, 5, 6, 7};
int n = sizeof(arr) / sizeof(arr[0]);
heapSort(arr, n);
std::cout << "Sorted array: ";
for (int i = 0; i < n; i++) {
std::cout << arr[i] << " ";
}
std::cout << std::endl;
return 0;
}
7. 希尔排序（Shell Sort）：
- 基本思想：插入排序的改进版，逐步将数据分组并进行插入排序，最后整体排序。
- 时间复杂度：介于 $O(n)$ 和 $O(n^2)$ 之间，具体取决于增量序列。
- 特点：相对高效，尤其在数据量较大时。
- 稳定性：不稳定
8. 计数排序（Counting Sort）：
- 基本思想：适合数据范围较小的整数序列，通过统计数据出现的次数进行排序。
- 时间复杂度：$O(n + k)$，其中 $k$ 为数值范围。
- 特点：非常高效，但仅适用于特定场景。
- 稳定性：稳定
9. 基数排序（Radix Sort）：
- 基本思想：按数位或字符位置逐步排序，适合整数或字符串等定长数据。
- 时间复杂度：$O(d \times (n + k))$，其中 $d$ 是位数，$k$ 为基数。
- 特点：适用于数值或字符数据，效率高。
- 稳定性：稳定代码说明:
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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
// 获取数组中最大元素的值
int getMax(int arr[], int n) {
int max = arr[0];
for (int i = 1; i < n; i++) {
if (arr[i] > max) {
max = arr[i];
}
}
return max;
}
// 计数排序，用于按特定位数对数组排序
void countSort(int arr[], int n, int exp) {
int* output = new int[n]; // 输出数组
int count[10] = {0}; // 计数数组（基数范围为 0 到 9）
// 统计在当前位数出现的次数
for (int i = 0; i < n; i++) {
count[(arr[i] / exp) % 10]++;
}
// 计算累积和，更新 count 数组
for (int i = 1; i < 10; i++) {
count[i] += count[i - 1];
}
// 构建输出数组，按当前位数排序
for (int i = n - 1; i >= 0; i--) {
int index = (arr[i] / exp) % 10;
output[count[index] - 1] = arr[i];
count[index]--;
}
// 将排序好的数据拷贝回原数组
for (int i = 0; i < n; i++) {
arr[i] = output[i];
}
delete[] output;
}
// 基数排序的主函数
void radixSort(int arr[], int n) {
int max = getMax(arr, n); // 获取最大元素以确定最高位数
// 对每一位数进行计数排序
for (int exp = 1; max / exp > 0; exp *= 10) {
countSort(arr, n, exp);
}
}
int main() {
int arr[] = {170, 45, 75, 90, 802, 24, 2, 66};
int n = sizeof(arr) / sizeof(arr[0]);
radixSort(arr, n);
std::cout << "Sorted array: ";
for (int i = 0; i < n; i++) {
std::cout << arr[i] << " ";
}
std::cout << std::endl;
return 0;
}
getMax函数用于找到数组中的最大值，确定排序过程中最高的位数。countSort函数实现了针对当前位数的计数排序。exp表示当前处理的位数（例如，个位、十位等），通过arr[i] / exp % 10提取该位上的数字。radixSort函数调用countSort，从最低位开始对数组进行多轮排序，直到最高位。
基数排序的时间复杂度为 $O(d \cdot (n + k))$，其中 $d$ 是数字的最大位数，$n$ 是数组长度，$k$ 是基数（通常为10）。在处理整数的情况下，它通常被认为是线性时间排序算法。
10. 桶排序（Bucket Sort）：
- 基本思想：将数据分到不同的桶中，然后对每个桶进行排序，最后合并桶。
- 时间复杂度：平均 $O(n + k)$
- 特点：适合数据分布均匀的情况。
- 稳定性：稳定（取决于桶内排序方法）
选择排序算法的依据
根据数据特性和需求，选择排序算法时一般考虑以下因素：
- 数据规模：数据规模小可以选择简单算法（如插入、选择、冒泡），规模较大可以考虑快速排序或归并排序。
- 数据特性：若数据接近有序，选择插入排序；对于整数范围较小的数据，可以选择计数排序。
- 稳定性要求：需要稳定的排序算法可以选择归并排序、计数排序、基数排序等。
- 空间要求：对空间要求较高的场景可优先考虑堆排序或快速排序（可原地排序）。
All articles on this blog are licensed under CC BY-NC-SA 4.0 unless otherwise stated.
Comments
