YuriCode
0%

排序算法大合集

发表于 更新于 分类于
本文字数： 2.8k 阅读时长 ≈ 3 分钟

排序算法

排序算法是指将一组元素按某种顺序排列的算法。通常，排序的目的是为了使得数据能够更加高效地查找、检索或处理。排序算法的应用非常广泛，几乎在所有需要数据排列的地方都能找到它的身影，比如：数据库查询、数据分析、图像处理、搜索引擎等

冒泡排序（Bubble Sort）

原理
通过不断交换相邻的元素，将较大的元素逐渐“冒泡”到数组的末端

1
2
3
4
5
6
7
8
9
10
template<typename T>
void bubbleSort(vector<T>& arr, int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j + 1] < arr[j]) {
                swap(arr[j + 1], arr[j]);
            }
        }
    }
}

最坏时间复杂度：O(n²)
在逆序的情况下，外层和内层循环都会遍历数组，导致平方级别的时间开销
最好时间复杂度：O(n)
如果数组已经是有序的，在这种情况下，算法只会进行一次遍历，比较次数为 n - 1 次，且不需要任何交换
空间复杂度：O(1)

优点
1、简单
2、稳定性

选择排序（Selection Sort）

原理：
从未排序的部分中选择最小的元素，并将其与未排序部分的第一个元素交换

1
2
3
4
5
6
7
8
9
10
11
12
template<typename T>
void selectionSort(vector<T>& arr, int n) {
    for (int i = 0; i < n - 1; i++) { 
        int min = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[min]) {
                min = j;
            }
            swap(arr[i], arr[min]);
        }
    }
}

时间复杂度：O(n²)
空间复杂度：O(1)

优点
1、无

插入排序（Insertion Sort）

原理
将数组中的每个元素逐个插入到已排序部分的合适位置来实现排序。它的工作方式类似于打扑克牌时，我们将一张牌一张一张地插入到已经有序的牌堆中

1
2
3
4
5
6
7
8
9
10
11
12
template<typename T>
void insertionSort(vector<T>& 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--;
        }
        arr[j + 1] = key;
    }
}

最坏时间复杂度：O(n²)
当数组逆序时，每次插入都需要比较和移动很多元素
最好时间复杂度：O(n)
当数组已经有序时，只需要进行少量的比较
空间复杂度：O(1)

优点
1、稳定性

计数排序（Counting Sort）

原理：
通过计算数组中每个元素出现的次数（即”计数”）来确定元素的最终位置

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
template<typename T>
void countingSort(vector<T>& arr, int n) {
    // 找到数组中最大和最小的元素
    T maxElement = arr[0], minElement = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] > maxElement) maxElement = arr[i];
        if (arr[i] < minElement) minElement = arr[i];
    }

    // 计算范围
    int range = maxElement - minElement + 1;

    // 创建计数数组，初始化为0
    vector<int> count(range, 0);

    // 填充计数数组
    for (int i = 0; i < n; i++) {
        count[arr[i] - minElement]++;
    }

    // 重新构建排序后的数组
    int index = 0;
    for (int i = 0; i < range; i++) {
        while (count[i] > 0) {
            arr[index++] = i + minElement;
            count[i]--;
        }
    }
}

时间复杂度：O(n + k)
其中 n 是输入数组的大小，k 是输入数据的最大值和最小值之间的范围。对于数据范围较小的情况，计数排序可以非常高效。遍历输入数组和填充计数数组的时间复杂度是 O(n)，累加计数数组和重建排序数组的时间复杂度是 O(k)，因此总体时间复杂度为 O(n + k)
空间复杂度：O(k)
需要额外的 count 数组来存储每个元素出现的次数，数组的大小为 k，即最大值和最小值之间的范围

优点
1、高效
2、稳定性
3、线性时间复杂度
缺点
1、空间消耗大
2、适用范围有限

快速排序

1
2
3
4
5
6
7
8
9
10
11
void quick_sort(int q[], int l, int r)
{
	if (l == r) return;
	int i = l - 1, j = r + 1, x = q[l + r >> 1];
	while(i < j){
		do i++; while(q[i] < x);
		do j--; while(q[j] > x);
		if (i < j) swap(q[i], q[j]);
	} 
	quick_sort(q, l, j); quick_sort(q, j + 1, r);
}

归并排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void merge_sort(int arr[], int l, int r) {
	if (l == r) return;
	int temp[r + 1];
	int mid = l + r >> 1;
	merge_sort(arr, l ,mid); merge_sort(arr, mid + 1, r);
	int k = 0, i = l, j = mid + 1;
	while(i <= mid && j <= r) {
		if (arr[i] <= arr[j]) temp[k++] = arr[i++];
		else temp[k++] = arr[j++];
	}
	while(i <= mid) temp[k++] = arr[i++];
	while(j <= r) temp[k++] = arr[j++];
	for (i = l, j = 0; i <= r; i++, j++) {
		arr[i] = temp[j];
	}	
}