数据结构排序算法总结
2021-12-30 本文已影响0人
欢喜树下种西瓜
前言
此文章记录个人数据结构——排序算法的点滴心得，以备以后查阅代码实现。
冒泡排序
核心思想
每次循环确定一个最大值，而且是通过前后一一比较交换得来。
每次循环，总循环次数-1
评价
冒泡排序非常中庸，简单但排序速度慢，稳定。没啥用
#include <iostream>
#include <vector>
using namespace std;
int bubbleSort(vector<int> &data) {
int Length = data.size();
for (int i = 0; i < Length - 1; i++) {
for (int j = 0; j < Length - i - 1; j++) {
if (data[j] > data[j + 1]) {
// 交换
int tmp = data[j];
data[j] = data[j + 1];
data[j + 1] = tmp;
}
}
}
}
选择排序
核心思想
每次循环选择出一个最小值，将其放到其对应的位置
评价
不稳定，且复杂度稳定于O(N2)
连冒泡都不如……
void selectSort(vector<int> &data) {
int Length = data.size();
for (int i = 0; i < Length; i++) {
int min = i;
for (int j = i; j < Length; j++) {
if (data[j] < data[min]) {
min = j;
}
}
// 寻找到当前位置对应的最小值,并交换
int tmp = data[i];
data[i] = data[min];
data[min] = tmp;
}
}
插入排序
核心思想
每次循环找到当前循环的最小值，并将其插入到合适的位置【插入时需要将每个元素都挪动】
评价
插入排序是简单排序中最实用的，速度比冒泡快，而且具有稳定性的特征。
void insertSort(vector<int> &data) {
int Length = data.size();
for (int i = 1; i < Length; i++) {
int j = i - 1;
int keyValue = data[i];
while (j >= 0 && (data[j] > keyValue)) {
data[j + 1] = data[j];
j--;
}
data[j + 1] = keyValue;
}
}
希尔排序
核心思想
先对数组的内容按gap进行分组，分组的数字进行插入排序。每次gap = gap / 2；直至gap = 1时，即对整个数组进插入排序，这样就完成了一次希尔排序。
最关键是，组内排序并不是严格地完成当前组内排序的。而是类似时间片式地进行组内排序！
评价
这个不稳定，而且时间复杂度O(n^1.3)。不及快排，相比快排，希尔排序显得很无力……
void shellSort(vector<int> &data) {
int Length = data.size();
for (int gap = Length / 2; gap >= 1; gap = gap / 2) {
// 分组
for (int i = gap; i < Length; i++) {
// 遍历每一组
int keyValue = data[i];
int j = i - gap;
for (j = i - gap; j >= 0 && data[j] > keyValue; j = j - gap) {
// 组内排序，这里结合了插入排序
// 务必遵循插入排序的标准写法，这样问题才少！
data[j + gap] = data[j];
}
data[j + gap] = keyValue;
}
}
}
快速排序
核心思想
快排核心就是给一个指定数字（哨兵）寻找到其合适的位置，即它的左边的数都比它小，右边的数都比它大。
再利用递归，如法炮制对其左右两个集合进行同样操作【分而治之】
- 例子
10(i) 9 16 5(j) 数组进行排序
i指向10，j指向5
以10哨兵，排序目标是在10左边的都比10小，在10右边的都比10大。
这里核心思想是，把10右边的比10小的放到10的左边，把10左边的比10大的放到10的右边即可！
故：
- 5(i) 9 16 10(j)
5比10小。j向左移动，找到一个比10小的数字，并与10互换。故交换
- 5 9 10(i) 16(j)
i向右移动，找到一个比10小的数字，并与10互换。
这里一直移动到16处，才找到比10大的数字，故16与10交换。
- 此时，j向左移动。
5 9 10(i)(j) 16
此时i和j重合，此次快排结束。
对[0, i -1]和[j + 1, length]两个集合递归执行上序操作，完成所有递归后，快排结束！
评价
快排是非常实用的排序！
void sort(vector<int> &data, int left, int right) {
int i = left;
int j = right;
// 这里默认以第一个为哨兵
int key = data[left];
if (i >= j) {
// 设定了终止条件
return;
}
while (i < j) {
// 先看右边比左边小的
while (data[j] > key && i < j) {
j--;
}
// 不使用互换是为了后续的循环还需要保留原先的值
// 这里是将右边的值放到哨兵左边，故将右边的值赋值给左边
data[i] = data[j];
// 再看左边有无比右边小的.上下需有一个加=，以解决出现相同数字的情况
while (key >= data[i] && i < j) {
i++;
}
// 这里是将左边的值放到哨兵右边，故将左边的值赋值给右边
data[j] = data[i];
}
// 此时i和j是相等的……
data[i] = key;
sort(data, left, i - 1);
sort(data, i + 1, right);
}
void quickSort(vector<int> &data) {
int Length = data.size();
sort(data, 0, Length - 1);
}
归并排序
思想
将两个有序的序列合并成一个有序序列
合并时是通过比较谁的头部元素最小的方法来进行合并的！
评价
归并排序类似与选择排序，其复杂度能稳定在O(nlogn)。而且稳定（这点比快排优秀，拥有与快排相近的速度）。但是归并排序需要额外的空间去辅助。
#include <iostream>
using namespace std;
void merge(int arr[], int tmpArr[], int left, int right, int mid) {
// 标记左半区第一个未排序的元素
int l_pos = left;
// 标记右半区第一个未排序的元素
int r_pos = mid + 1;
// 临时数组的下标
int pos = left;
// 合并
while (l_pos <= mid && r_pos <= right) {
// 左半区第一个剩余元素更小
if (arr[l_pos] < arr[r_pos]) {
tmpArr[pos++] = arr[l_pos++];
} else {
tmpArr[pos++] = arr[r_pos++];
}
}
// 合并左半区剩余元素
while (l_pos <= mid) {
tmpArr[pos++] = arr[l_pos++];
}
// 合并右半区剩余元素
while (r_pos <= right) {
tmpArr[pos++] = arr[r_pos++];
}
// 临时数组内容复原到原来的数组
while (left <= right) {
arr[left] = tmpArr[left];
left++;
}
}
void msort(int arr[], int tmpArr[], int left, int right) {
if (left < right) {
int mid = (left + right) / 2;
msort(arr, tmpArr, left, mid);
msort(arr, tmpArr, mid + 1, right);
merge(arr, tmpArr, left, right, mid);
}
}
void mergeSort(int data[], int length) {
int *tmpArr = new int[length];
msort(data, tmpArr, 0, length - 1);
delete tmpArr;
// 展示排列后的数组
for (int i = 0; i < length; i++) {
cout << data[i] << endl;
}
}
void test() {
int data[] = {10, 8, 7, 5, 15, 3};
int length = sizeof(data) / sizeof(int);
mergeSort(data, length);
}
int main() {
test();
return 0;
}
总结
| 排序算法 | 平均时间复杂度 | 空间复杂度 | 稳定性 |
|---|---|---|---|
| 冒泡排序 | O(n^2) | O(1) | 稳定 |
| 选择排序 | O(n^2) | O(1) | 不稳定 |
| 插入排序 | O(n^2) | O(1) | 稳定 |
| 希尔排序 | O(n^1.3) | O(1) | 稳定 |
| 快速排序 | O(nlogn) | O(logn) | 不稳定 |
| 归并排序 | O(nlogn) | O(n) | 稳定 |
- 冒泡、插入与选择排序都是非常简单的排序算法，这类算法一般优先使用插入排序，插入排序稳定、不使用辅助空间且不受元素分布影响。
- 归并排序、快速排序都算得上较复杂的排序算法，这两者时间复杂度能达到O（nlogn）。其中快排不稳定，但空间占用得少。而归并排序稳定，但空间占用得多，在最差情况下归并排序速度要比快排快，实际中酌情使用。
还有部分排序算法未实现，待日后补充
