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++刷题】的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
-
el-table 开启定时器下,表格的选中状态会消失是什么原因-icode9专业技术文章分享10-04
-
如何安装和初始化飞牛私有云 fnOS？-icode9专业技术文章分享10-03
-
如何安装 App 并连接到飞牛 NAS？-icode9专业技术文章分享10-03
-
如何安装飞牛 TV 并连接到影视服务器？-icode9专业技术文章分享10-03
-
如何在PVE和ESXI上安装飞牛私有云 fnOS？-icode9专业技术文章分享10-03
-
fnOS国产最强NAS安装系统异常情况处理-icode9专业技术文章分享10-03
-
飞牛NAS如何创建存储空间？-icode9专业技术文章分享10-03
-
fnOS国产最强NAS硬盘会自动休眠吗？-icode9专业技术文章分享10-03
-
fnOS国产最强NAS如何安装飞牛影视和创建媒体库？-icode9专业技术文章分享10-03
-
fnOS国产最强NAS如何为家人朋友开通影视账号？-icode9专业技术文章分享10-03
-
fnOS国产最强NAS创建媒体库时无法选择文件夹？-icode9专业技术文章分享10-03
-
fnOS国产最强NAS如何修改错误匹配的影片信息?-icode9专业技术文章分享10-03
-
如何免费远程访问到飞牛NAS？-icode9专业技术文章分享10-03
-
fnOS国产最强NAS如何备份手机照片？-icode9专业技术文章分享10-03
-
fnOS国产最强NAS如何共享相册给设备内其他用户？-icode9专业技术文章分享10-03
栏目导航
