408代码类复习--八大排序

Author：Joanh_Lan

Personal Blog Links：Joanh_LanのCSDN博客
备注：

个人复习版本，能用OJ检测的均已检测通过

不保证完全正确，理性参考（不背锅i哦）

（：（：（：

欢迎阅读！！！
如果需要电子版请私信我，这个专栏不收取任何费用。

八大排序

quick_sort

平均时间复杂度: O( $nlog_2{n}$ )

最坏时间复杂度:O( $n^2$ )

快速排序通常明显快于其他排序算法，但对于相等元素的顺序可能会被改变，稳定性较差，它的时间复杂度为 O( $nlog_2n$ )，**空间复杂度为 O( $log_2n$ ) **有栈开销。

// quick_sort#include <iostream>
#define MAXSIZE 100009
using namespace std;
int arr[MAXSIZE];
void myswap(int& a, int& b) {int t = a;a = b;b = t;
}
int partition(int arr[], int low, int high) {int standard = arr[low];int l = low, r = high;while (l < r){while (l < r && arr[r] >= standard)	r--;while (l < r && arr[l] <= standard) l++;if (l < r)myswap(arr[l], arr[r]);}myswap(arr[l], arr[low]);return l;
}
void quick_sort(int arr[], int low, int high) {if (low >= high)	return;int idx = partition(arr, low, high);quick_sort(arr, low, idx - 1);quick_sort(arr, idx + 1, high);
}
int main()
{int n;	cin >> n;for (int i = 0; i < n; i++)	cin >> arr[i];quick_sort(arr, 0, n - 1);for (int i = 0; i < n; i++)	cout << arr[i] << " \n"[i == n-1];
}

quick_selection

寻找第k小数

quick_sort改一下就成

时间复杂度:O(n)

空间复杂度:O( $log_2n$ ) 注：可以优化成 O(1)

#include <iostream>
#define MAXSIZE 100009
using namespace std;
int arr[MAXSIZE];
int quick_selection(int arr[], int low ,int high, int k){int standard = arr[low];int l = low, r = high;while (l < r){while (l < r && arr[r] >= standard)	r--;while (l < r && arr[l] <= standard)	l++;if (l < r)	swap(arr[l], arr[r]);}swap(arr[l], arr[low]);if (l == k - 1)	return arr[l];else if (l < k - 1)	return quick_selection(arr, l + 1, high, k);else return quick_selection(arr, low, l - 1, k);
}
int main()
{int n;	cin >> n;for (int i = 0; i < n; i++)	cin >> arr[i];int k; 	cin >> k;int	idx = quick_selection(arr, 0, n - 1, k);cout << arr[idx] << '\n';
}

若想将空间优化成O(1)

参考下述代码

     int quick_select(vector<int>& nums, int l, int r, int k) {while(true) {if (l == r) return nums[l];int i = l - 1, j = r + 1, x = nums[l + r >> 1]; // 选取 nums[l], 极端样例 时间会很久// int x = nums[rand() % (r - l + 1) + l], i = l - 1, j = r + 1; // 随机选取while (i < j) {do i ++ ; while (nums[i] > x);do j -- ; while (nums[j] < x);if (i < j) swap(nums[i], nums[j]);}// 将 递归 的 参数l,r,k变化 改为 while 循环中 l,r,k 更新, 省去递归栈空间// if (k <= j - l + 1) return quick_select(nums, l, j, k);if (k <= j - l + 1) r = j;// else return quick_select(nums, j + 1, r, k - (j - l + 1));else k = k - (j - l + 1), l = j + 1; // 注意 k更新用到 l, 所以 l 更新应该在 k更新之后}}作者：YXC

merge_sort

归并排序是一种分治算法，它将数据分为两个子序列并对每个子序列进行排序，最后将两个有序子序列合并成一个有序序列。归并排序的稳定性很好，即相等元素的顺序会被保持不变。归并排序的时间复杂度为 O( $nlog_2n$ )，空间复杂度为 O(n)。

#include <iostream>
#define MAXSIZE 100009
using namespace std;
int arr[MAXSIZE];
int t[MAXSIZE]; //辅助数组 
void merge_sort(int arr[], int low, int high){if (low >= high)	return;int mid = (low + high) >> 1;merge_sort(arr, low, mid);merge_sort(arr, mid + 1, high);int i = low, j = mid + 1, idx = 0;while(i <= mid && j <= high){if (arr[i] < arr[j])	t[idx++] = arr[i++];else t[idx++] = arr[j++];}while (i <= mid)	t[idx++] = arr[i++];while (j <= high)	t[idx++] = arr[j++];for (int p = low, q = 0; p <= high; p++, q++)arr[p] = t[q];return;
} 
int main()
{int n;	cin >> n;for (int i = 0; i < n; i++)	cin >> arr[i];merge_sort(arr, 0, n - 1);for (int i = 0; i < n; i++)	cout << arr[i] << " \n"[i == n - 1];
}

merge_sort在求逆序对个数的时候是一把利器

只需要做以下修改：

int ans = 0;//在最前面定义while(i <= mid && j <= high){if (arr[i] < arr[j])	t[idx++] = arr[i++];else {ans += mid - i + 1;t[idx++] = arr[j++];}}ans的值就是逆序对的个数

easy_selection_sort

时间复杂度: O( $n^2$ )

空间复杂度:O(1)

#include <iostream>
#define MAXSIZE 100009
using namespace std;
int arr[MAXSIZE]; 
void easy_selection_sort(int arr[], int low ,int high){for (int i = low; i <= high; i++){int idx = i;for (int j = i; j <= high; j++)if (arr[j] < arr[idx])	idx = j;swap(arr[i], arr[idx]);}return;
}
int main()
{int n;	cin >> n;for (int i = 0; i < n; i++)	cin >> arr[i];easy_selection_sort(arr, 0, n - 1);for (int i = 0; i < n; i++)	cout << arr[i] << " \n"[i == n - 1];
}

insert_sort

插入排序是一种简单的排序算法，它将数据分为已排序和未排序两个部分，每次从未排序部分取出一个元素，并将其插入到已排序部分的合适位置。插入排序的稳定性是很好的，它对于相等的元素是保持原来的顺序不变。插入排序的时间复杂度为 O( $n^2$ )，空间复杂度为 O(1)，在数据规模较小的情况下表现良好。

最好时间复杂度：O(n) 序列的前面已经是有序的情况
平均时间复杂度：O( $n^2$ )
最差时间复杂度：O( $n^2$ ) 倒序

#include <iostream>
#define MAXSIZE 100009
using namespace std;
int arr[MAXSIZE];
void insert_sort(int arr[], int low ,int high){for (int i = low + 1; i <= high; i++){if (arr[i] >= arr[i - 1])	continue;int j = i;while (j != 0 && arr[j] < arr[j - 1])	swap(arr[j], arr[j - 1]), j--;}return;
}
int main()
{int n;	cin >> n;for (int i = 0; i < n; i++)	cin >> arr[i];insert_sort(arr, 0, n - 1);for (int i = 0; i < n; i++)	cout << arr[i] << " \n"[i == n - 1];
}

shell_sort

希尔排序的稳定性较差，即相等元素的顺序可能会被改变,空间复杂度为 O(1)。在数据规模较大时表现良好。

希尔排序的平均时间复杂度通常被认为是介于O(n)和O( $n ^ 2$ )之间，具体取决于选取的间隔序列。在实际应用中，常用的希尔排序的时间复杂度为O( $n^1.3$ )，这是基于经验得出的一个较好的估计。但需要注意的是，希尔排序的时间复杂度并不是一个确定的值，而是与输入数据的特性和选取的间隔序列有关。

#include <iostream>
#define MAXSIZE 100009
using namespace std;
int arr[MAXSIZE];
void shell_sort(int arr[], int low ,int high){for (int d = (high - low + 2) >> 1; d >= 1; d = (d + 1) >> 1){for (int i = low + d; i <= high; i += d){if (arr[i] >= arr[i - d])	continue;int j = i;while (j - d >= 0 && arr[j] < arr[j - d])swap(arr[j], arr[j - d]), j -= d;}if (d == 1) return;}
}
int main()
{int n;	cin >> n;for (int i = 0; i < n; i++)	cin >> arr[i];shell_sort(arr, 0, n - 1);for (int i = 0; i < n; i++)	cout << arr[i] << " \n"[i == n - 1];
}

Bubble sort

It’s too simple to explain

冒泡排序是一种简单的排序算法，它通过重复地交换相邻元素将未排序部分的最大元素“冒泡”到已排序部分的末尾。冒泡排序的稳定性很好，即相等元素的顺序会被保持不变。冒泡排序的时间复杂度为 O($n^2)，空间复杂度为 O(1)。

// 冒泡排序
void BubbleSort(int* a, int n)
{for (int i = 0; i < n; i++) // 外层循环控制比较轮数{for (int j = 1; j < n - i; j++) // 内层循环从第一个元素开始，依次比较相邻的两个元素{if (a[j - 1] > a[j]) // 如果前一个元素大于后一个元素，则交换它们的位置{Swap(&a[j - 1], &a[j]);}}}
}

heap_sort

堆排序是一种通过维护一个二叉堆来实现的排序算法，它将未排序部分的最大元素与已排序部分的末尾交换，然后重建堆，稳定性较差。堆排序的时间复杂度为 O( $nlog_2 n$ )，空间复杂度为 O(1)，但对于相等元素的顺序可能会被改变。

// 维护小根堆，大根堆类别即可
#include <iostream>
#define MAXSIZE 100009
using namespace std;
int heap[MAXSIZE];
int cnt = 0;void down(int rt)
{if (rt > cnt)	return;int idx = rt;int lchild = rt << 1;int rchild = lchild + 1;if (lchild <= cnt && heap[idx] > heap[lchild])	idx = lchild;if (rchild <= cnt && heap[idx] > heap[rchild])	idx = rchild;if (idx != rt)swap(heap[rt], heap[idx]), down(idx);
}int main()
{int n;	cin >> n;cnt = n;for (int i = 1; i <= n; i++)	cin >> heap[i];for (int i = cnt >> 1; i >= 1; i--)	down(i);for (int i = 1; i <= n; i++) {cout << heap[1] << " \n"[i == n];heap[1] = heap[cnt--];down(1);}
}

counting_sort

计数排序是一种非比较的排序算法，它的思想是统计每个元素在数组中出现的次数，并根据元素出现的次数依次输出元素。计数排序的稳定性很不好，就没有顺序可言。计数排序的时间复杂度为 O(n+k)，其中，k是待排序数组中最大元素减去最小元素再加1的值，空间复杂度也是 O(n+k)。

#include <iostream>
#include <cmath>
#define MAXSIZE 100009
using namespace std;
int arr[MAXSIZE];void counting_sort(int arr[], int low, int high){int min_n = 0x3f3f3f3f, max_n = (int)((unsigned int)(1<<32 - 1));for (int i = low; i <= high; i++)	min_n = min(min_n, arr[i]), max_n = max(max_n, arr[i]);int len = max_n - min_n + 1;int *b = (int*)malloc(sizeof(int) * len);for (int i = 0; i < len; i++) b[i] = 0;for (int i = low; i <= high; i++)b[arr[i] - min_n]++;for (int i = 0; i < len; i++)while (b[i]--)	cout << i + min_n << ' ';
}int main()
{int n; cin >> n;for (int i = 0; i < n; i++)	cin >> arr[i];counting_sort(arr, 0, n - 1);
}