网站如何连接微信支付,设计家官网室内设计,世界建筑网站,桂林骏程网站建设1. 基本思想 分治快速排序#xff08;Quick Sort#xff09;是一种基于分治法的排序算法#xff0c;采用递归的方式将一个数组分割成小的子数组#xff0c;并通过交换元素来使得每个子数组元素按照特定顺序排列#xff0c;最终将整个数组排序。
快速排序的基本步骤#…1. 基本思想 分治快速排序Quick Sort是一种基于分治法的排序算法采用递归的方式将一个数组分割成小的子数组并通过交换元素来使得每个子数组元素按照特定顺序排列最终将整个数组排序。
快速排序的基本步骤
选择基准元素从数组中选择一个元素作为基准pivot。分区操作将数组分成两个部分左边的部分所有元素都小于基准元素右边的部分所有元素都大于基准元素。此时基准元素已经排好序。递归排序对基准元素左侧和右侧的子数组递归进行快速排序。
快速排序的核心思想
分治法通过每次选择一个基准元素将数组分割成两个子数组然后递归地对两个子数组进行排序。每次选择基准元素后通过分区将数组划分为两个部分左侧部分的元素都小于基准右侧部分的元素都大于基准。递归对子数组进行排序直到每个子数组的长度为 1 或 0排序完成。
// 分区函数返回基准元素的正确位置
int Partition(vectorint arr, int low, int high) {int pivot arr[high]; // 选择最后一个元素作为基准int i low - 1; // i 是小于基准元素的子数组的最后一个元素的索引// 遍历数组将小于基准的元素移动到数组的前面for (int j low; j high; j) {if (arr[j] pivot) {i;swap(arr[i], arr[j]);}}// 将基准元素放到正确的位置swap(arr[i 1], arr[high]);return i 1; // 返回基准元素的索引
}// 快速排序函数
void QuickSort(vectorint arr, int low, int high) {if (low high) {// 找到基准元素的索引int pi Partition(arr, low, high);// 递归排序基准元素左边和右边的子数组QuickSort(arr, low, pi - 1); // 排序左边子数组QuickSort(arr, pi 1, high); // 排序右边子数组}
} 2. 快速选择算法 快速选择算法Quickselect 是一种基于快速排序Quick Sort的算法用于在未排序的数组中找到第 k 小大的元素。与快速排序不同快速选择只对包含第 k 小大元素的部分进行排序而不需要对整个数组进行排序因此它的时间复杂度通常较低。
快速选择的核心思想是
与快速排序一样通过选择一个“基准”元素并进行分区Partition操作将数组分成左右两个部分。如果基准元素的位置正好是 k则基准元素即为第 k 小的元素。如果基准元素的位置小于 k则继续在右侧子数组中查找第 k 小元素。如果基准元素的位置大于 k则继续在左侧子数组中查找第 k 小元素。
通过将数组分成三个部分小于基准、等于基准、大于基准从而更有效地找到第 k 小的元素。相较于传统的快速选择算法使用三个部分分区可以加速查找过程特别是在处理重复元素时。
下面是一个示例这类问题可以以此为模板通过适当修改来实现不同的目标。
int qsort(vectorint nums, int l, int r, int k){if(l r) return nums[l];//1.随机选择基准数int key getRandom(nums, l, r);//2.根据基准数将数组分成三组int left l - 1, right r 1, i l;while(i right){if(nums[i] key) swap(nums[left], nums[i]);else if(nums[i] key) i;else swap(nums[--right], nums[i]); }//3.分情况讨论int c r - right 1, b right - left - 1;if(c k)return qsort(nums, right, r, k);else if(b c k) return key;else return qsort(nums, l, left, k - b - c);}int getRandom(vectorint nums, int left, int right){int r rand();return nums[r % (right - left) left];}
3. 颜色分类 解法三指针
排序时数组被分成四个部分[0, left] 区间都是0(left, i)区间都是1[i, right]区间是未排序的部分[right , n - 1]区间都是2.
排序完成后i与right相等数组被分成三个部分[0, left]都是1(left, i)都是0[right , n - 1]都是2 class Solution {
public:void sortColors(vectorint nums) {int i 0, n nums.size();int left -1, right n;while(i right){if(nums[i] 0) swap(nums[i], nums[left]);else if(nums[i] 1) i;else if(nums[i] 2) swap(nums[i], nums[--right]);}}
};
75. 颜色分类 - 力扣LeetCode
4. 排序数组 使用将数组分成三部分的思想实现快排效率会更高 class Solution {
public:vectorint sortArray(vectorint nums) {srand(time(NULL));qsort(nums, 0, nums.size() - 1);return nums;}void qsort(vectorint nums, int l, int r){if(l r) return;int key getRanNum(nums, l, r);//获取随机基准值int i l, left l - 1, right r 1;while(i right){if(nums[i] key) swap(nums[left], nums[i]);else if(nums[i] key) i;else swap(nums[--right], nums[i]);}qsort(nums, l, left);qsort(nums, right, r);}int getRanNum(vectorint nums, int left, int right){int r rand();return nums[r % (right - left) left];}
};
912. 排序数组 - 力扣LeetCode
5. 数组中第k个最大元素 快速选择算法 class Solution {
public:int findKthLargest(vectorint nums, int k) {srand(time(NULL));return qsort(nums, 0, nums.size() - 1, k);}int qsort(vectorint nums, int l, int r, int k){if(l r) return nums[l];//返回条件//1.随机选择基准数int key getRandom(nums, l, r);//2.根据基准数将数组分成三组int left l - 1, right r 1, i l;while(i right){if(nums[i] key) swap(nums[left], nums[i]);else if(nums[i] key) i;else swap(nums[--right], nums[i]); }//3.分情况讨论int c r - right 1, b right - left - 1;if(c k)return qsort(nums, right, r, k);else if(b c k) return key;else return qsort(nums, l, left, k - b - c);}int getRandom(vectorint nums, int left, int right){int r rand();return nums[r % (right - left) left];}
};
215. 数组中的第K个最大元素 - 力扣LeetCode
6. 库存管理 法一排序 O(nlogn)
法二堆排序 O(nlogk)
法三快速选择算法 O(n)
class Solution {
public:vectorint inventoryManagement(vectorint stock, int cnt) {srand(time(NULL));qsort(stock, 0, stock.size() - 1, cnt);return {stock.begin(), stock.begin() cnt};}void qsort(vectorint stock,int l, int r, int cnt){if(l r) return;//1.随机选择基准数int key getRandom(stock, l, r);//2.根据基准数将数组分成三组int left l - 1, right r 1, i l;while(i right){if(stock[i] key) swap(stock[left], stock[i]);else if(stock[i] key) i;else swap(stock[--right], stock[i]); }//3.分情况讨论int a left - l 1, b right - left - 1;if(cnt a) qsort(stock, l, left, cnt);else if(cnt a b) return;else qsort(stock, right, r, cnt - a - b);}int getRandom(vectorint stock, int left, int right){int r rand();return stock[r % (right - left) left];}
};
