C/C++教程
（四）排序【C++刷题】
本文主要是介绍（四）排序【C++刷题】，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！
排序数组
Leetcode：https://leetcode-cn.com/problems/sort-an-array/
1.问题描述
给定一个整数数组nums，将该数组升序排列。
2.输入输出
- Input：[5, 2, 3, 1]
- Output：[1, 2, 3, 5]
3.算法分析
1.【选择排序】首先找到数组中最小的那个元素，其次，将它和数组中第一个元素交换位置（如果第一个元素就是最小元素那么它和子集交换）。再次，在剩下的元素中找到最小的元素，将它与数组的第二个元素交换位置。如此循环往复。
- 时间复杂度：\(O(n^2)\)
- 空间复杂度：\(O(1)\)
2.【插入排序】将每个元素插入到其他已经有序的元素中的适当位置。为了给插入的元素腾出空间，需要将其余所有元素在插入之前都向右移动一位。
- 时间复杂度：\(O(n)-O(n^2)\)取决于输入元素的排列情况
- 空间复杂度：\(O(1)\)
3.【希尔排序】是数组中任意间隔h的元素都是有序的，对于每个h，用插入排序将h个子数组独立地排序。h从n/3开始递减至1。
- 时间复杂度：\(O(nlogn)\)
- 空间复杂度：\(O(1)\)
4.【归并排序】分治思想，将大数组划分成两个子数组进行排序，通过归并两个子数组来将整个数组排序，原地归并需要将涉及到地元素复制到一个辅助数组中，再将归并的结果放回原数组。
- 时间复杂度：\(O(nlogn)\)
- 空间复杂度：\(O(n)\)
5.【快速排序】将一个数组分成两个子数组，将两部分独立地排序。切分地位置取决于数组的内容。先随意取第一个元素作为切分元素，从数组左端开始向右扫描直到找到一个大于等于它的元素，在从数组右端开始向左扫描找到一个小于等于它的元素，交换这两个元素的位置，直到两个指针相遇，最后和切分元素交换位置即可。
- 时间复杂度：\(O(nlogn)\)
- 空间复杂度：\(O(logn)\)
6.【堆排序】在堆的构造阶段中，将原始数组重新组织安排进一个堆中，在下沉排序阶段，从堆中按递减顺序取出所有元素并得到排序结果。
- 时间复杂度：\(O(nlogn)\)
- 空间复杂度：\(O(1)\)
7.【冒泡排序】一边比较一边向后两两交换，将最大值冒泡到最后一位，当不再发生交换时排序停止。
- 时间复杂度：\(O(n^2)\)
- 空间复杂度：\(O(1)\)
8.【桶排序】实现线性排序，但当元素间值的大小有较大差距时会带来内存空间较大浪费。首先，找出待排序列中的最大元素max，申请内存为max+1的桶（数组）并初始化为0；然后，遍历排序数组，并依次将每个元素作为下标的桶元素值自增1，最后遍历桶元素，并依次将值非0的元素下标值载入排序数列（桶元素>1表明有值大小相等的元素，此时依次将他们载入排序序列），遍历完成，排序序列为有序序列。
- 时间复杂度：\(O(n)\)
- 空间复杂度：\(O(n)\)
9.【二分（折半）插入排序】顺序的把待排序的序列中的各个元素按关键字的大小，通过折半查找插入到已排序的序列的适当位置。
- 时间复杂度：\(O(n^2)\)
- 空间复杂度：\(O(1)\)
10.【基数排序】十个桶，每次取数的（个十百）…位放入桶中，重复这个过程
- 时间复杂度：\(O（n）\)
- 空间复杂度：\(O(n)\)
4.编程实现
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
class Solution{
public:
void selectSort(vector<int> &nums) {
int n = nums.size();
for (int i = 0; i < n; i++) {
int minIndex = i;
for (int j = i+1; j < n; j++) { // 找到剩余数组最小值
if (nums[j] < nums[minIndex]) minIndex = j;
}
// 交换最小值 swap(nums[i], nums[minIndex)
int tmp = nums[i];
nums[i] = nums[minIndex];
nums[minIndex] = tmp;
}
}
void insertSort(vector<int> &nums) {
int n = nums.size();
for (int i = 1; i < n; i++) {
for (int j = i; j > 0 && nums[j] < nums[j-1]; j--) {
// 交换元素 swap(nums[j], nums[j-1])
int tmp = nums[j];
nums[j] = nums[j-1];
nums[j-1] = tmp;
}
}
}
void shellSort(vector<int> &nums) {
int n = nums.size();
int h = 1;
while (h < n/3) h = 3*h + 1;
while (h >= 1) { // 将数组变为h有序
for (int i = h; i < n; i++) { // 将nums[i] 插入到nums[i-h], nums[i-2h], nums[i-3h]…中
for (int j = i; j >= h && nums[j] < nums[j-h]; j -= h) {
// 交换nums[j]和nums[j-h]——swap(nums[j]和nums[j-h])
int tmp = nums[j];
nums[j] = nums[j-h];
nums[j-h] = tmp;
}
}
h = h/3;
}
}
void mergeSort(vector<int> &nums, int left, int right, vector<int> &temp) {
if (left == right) return; // 递归出口
// 分
int mid = left + (right - left) / 2;
mergeSort(nums, left, mid, temp);
mergeSort(nums, mid+1, right, temp);
// 治
int i = left, j = mid+1;
for (int k = left; k <= right; k++) { // 合并
if ((j > right) || (i <= mid && nums[i] <= nums[j])) {
temp[k] = nums[i++];
} else {
temp[k] = nums[j++];
}
}
for (int k = left; k <= right; k++) nums[k] = temp[k]; // 复制
}
void quickSort(vector<int> &nums, int left, int right) {
if (left+1 >= right) return;
int first = left, last = right - 1, key = nums[first];
while (first < last) {
// 从右往左找到第一个大于key的值
while (first < last && nums[last] >= key) --last;
nums[first] = nums[last];
// 从左往右找到第一个小于key的值
while (first < last && nums[first] <= key) ++first;
nums[last] = nums[first];
}
nums[first] = key;
quickSort(nums, left, first);
quickSort(nums, first+1, right);
}
//堆排序
void adjust(vector<int> &nums, int len, int index){
int left = 2 * index + 1; // index的左子节点
int right = 2 * index + 2;// index的右子节点
int maxIdx = index;
if (left < len && nums[left] > nums[maxIdx]) maxIdx = left;
if (right < len && nums[right] > nums[maxIdx]) maxIdx = right;
if (maxIdx != index) {
swap(nums[maxIdx], nums[index]);
adjust(nums, len, maxIdx);
}
}
// 堆排序
void heapSort(vector<int> &nums, int size){
for(int i = size / 2 - 1; i >= 0; i--){
adjust(nums, size, i);
}
for(int i = size - 1; i >= 1; i--){
swap(nums[0], nums[i]);
adjust(nums, i, 0);
}
}
void bubbleSort(vector<int> &nums, int n) {
bool swapped;
for (int i = 1; i < n; i++) {
swapped = false;
for (int j = 1; j < n-i+1; j++) {
if (nums[j] < nums[j-1]) {
swap(nums[j], nums[j-1]);
swapped = true;
}
}
if (!swapped) break;
}
}
void bucketSort (vector<int>& nums) {
int bk[50000 * 2 + 1];
memset(bk, 0, sizeof(bk)); // 清零
for(int i = 0; i < nums.size(); i++){
bk[nums[i] + 50000] += 1;
}
int ar = 0;
for(int i = 0; i < 100001; i++){
for(int j = bk[i]; j > 0; j--){
nums[ar++] = i - 50000;
}
}
}
void hInsertSort(vector<int> &nums, int n) {
int i,j,low,high,mid;
for (i = 0; i < n; i++ ){
int tmp = nums[i];
low = 0; high = i-1;
while(low <= high) {
mid = low + (high - low) / 2;
if(nums[mid] > tmp){
high = mid - 1;
}else{
low = mid + 1;
}
}
for(j = i-1; j >= high+1; j--){
nums[j+1] = nums[j];
}
nums[high+1] = tmp;
}
}
void radixSort(vector<int> &nums) {
int n = nums.size(), max=abs(nums[0]);
for(int i = 1; i < n; i++){
if(max < abs(nums[i]))
max = abs(nums[i]);
}
int w = 0;
while(max > 0) {
max /= 10;
w++;
}
int flag = 1;
vector<int> ans(n);
for(int i = 0; i < w; i++) {
vector<int> bucket(19, 0);
for(int j = 0; j < n; j++) {
int temp = nums[j] / flag % 10 + 9;
bucket[temp]++;
}
for(int j = 1; j < 19; j++)
bucket[j] += bucket[j-1];
for(int j = n-1; j >= 0; j--) {
int temp = nums[j] / flag % 10 + 9;
ans[--bucket[temp]] = nums[j];
}
nums.swap(ans);
flag *= 10;
}
}
vector<int> sortArray(vector<int>& nums) {
int n = nums.size();
// 1.选择排序
// selectSort(nums);
// 2.插入排序
// insertSort(nums);
// 3.希尔排序
// shellSort(nums);
// 4.原地归并排序
// vector<int> temp(n);
// mergeSort(nums, 0, n-1, temp);
// 5.快速排序
// quickSort(nums, 0, n);
// 6.堆排序
// heapSort(nums, n);
// 7.冒泡排序
// bubbleSort(nums, n);
// 8.桶排序
// bucketSort(nums);
// 9.折半插入排序
// hInsertSort(nums, n);
// 10.基数排序
radixSort(nums);
return nums;
}
};
int main() {
vector<int> nums = {2, 1, 5, 3, 4};
Solution sol;
// 排序
sol.sortArray(nums);
for (const int & val: nums) {
cout << val << " ";
}
return 0;
}
数组中的第K个最大元素
leetcode：https://leetcode-cn.com/problems/kth-largest-element-in-an-array/
1.问题描述
给定整数数组 nums和整数 k，请返回数组中第 k个最大的元素。
2.输入输出
- Input：[3,2,1,5,6,4] ，k = 2
- Output：5
3.算法分析
【快速旋转】快速旋转一般用于求解k-th Element问题，只需要找到第k大的枢（pivot）即可，不需要对其左右再进行排序。与快速排序一样，一般需要先打乱数组，注意只需要快排数组大小
- 时间复杂度：O（n）
- 空间复杂度：O（1）
4.编程实现
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
int len = nums.size()-1;
int value = quickSort(nums, len-k, 0, nums.size()-1);
return value;
}
int quickSelection(vector<int>& nums, int k, int left, int right) {
int first = left, last = right, key = nums[first];
while (first < last) {
while (first < last && nums[last] >= key) --last;
nums[first] = nums[first];
while (first < last && nums[first] <= key) ++first;
nums[last] = nums[first];
}
nums[first] = key;
if (first == k) {
return nums[k];
} else if (first < k) {
return quickSelection(nums, k, first+1, right);
} else {
return quickSelection(nums, k, left, first-1);
}
}
};
int main(){
vector<int> nums = {3, 2, 1, 5, 6, 4};
int k = 2;
Solution sol;
cout << sol.findKthLargest(nums, k) << endl;
return 0;
}
这篇关于（四）排序【C++刷题】的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
-
增量更新怎么做？-icode9专业技术文章分享11-23
-
压缩包加密方案有哪些？-icode9专业技术文章分享11-23
-
用shell怎么写一个开机时自动同步远程仓库的代码？-icode9专业技术文章分享11-23
-
webman可以同步自己的仓库吗？-icode9专业技术文章分享11-23
-
在 Webman 中怎么判断是否有某命令进程正在运行？-icode9专业技术文章分享11-23
-
如何重置new Swiper?-icode9专业技术文章分享11-23
-
oss直传有什么好处？-icode9专业技术文章分享11-23
-
如何将oss直传封装成一个组件在其他页面调用时都可以使用？-icode9专业技术文章分享11-23
-
怎么使用laravel 11在代码里获取路由列表？-icode9专业技术文章分享11-23
-
怎么实现ansible playbook 备份代码中命名包含时间戳功能？-icode9专业技术文章分享11-22
-
ansible 的archive 参数是什么意思？-icode9专业技术文章分享11-22
-
ansible 中怎么只用archive 排除某个目录？-icode9专业技术文章分享11-22
-
exclude_path参数是什么作用？-icode9专业技术文章分享11-22
-
微信开放平台第三方平台什么时候调用数据预拉取和数据周期性更新接口？-icode9专业技术文章分享11-22
-
uniapp 实现聊天消息会话的列表功能怎么实现？-icode9专业技术文章分享11-22
栏目导航
