宜昌便宜做网站,网站 做内容分发资格,龙岩天宫山缆车多少钱,樱花16q808a创作不易#xff0c;本篇文章如果帮助到了你#xff0c;还请点赞 关注支持一下♡#x16966;)!! 主页专栏有更多知识#xff0c;如有疑问欢迎大家指正讨论#xff0c;共同进步#xff01; 更多算法分析与设计知识专栏#xff1a;算法分析#x1f525; 给大家跳… 创作不易本篇文章如果帮助到了你还请点赞 关注支持一下♡)!! 主页专栏有更多知识如有疑问欢迎大家指正讨论共同进步 更多算法分析与设计知识专栏算法分析 给大家跳段街舞感谢支持ጿ ኈ ቼ ዽ ጿ ኈ ቼ ዽ ጿ ኈ ቼ ዽ ጿ ኈ ቼ ዽ ጿ ኈ ቼ 目录 一、挖坑填补法二、区间分割法三、快排的优化 快排的基本思想先确定一个标准值将比标准值小的元素放在标准值的左侧比标准值大的元素放在右侧左右部分分别重复以上的操作直到整个数组有序。 快速排序是基于分治策略的排序算法 一、挖坑填补法
选择一个基准元素将基准元素挖出形成一个坑从右向左遍历数组找到第一个比基准元素小的元素将其填入空坑中并将此位置视为新的坑从左向右遍历数组找到第一个比基准元素大的元素将其填入新的空坑中并将此位置视为新的坑重复过程直到左右指针相遇最后将基准元素填入坑中此时基准元素左边的所有元素都比它小右边的所有元素都比它大。对基准元素左边和右边的子数组递归地进行上述操作直到整个数组有序 C代码
#include iostream
#include cmath
using namespace std;int partition(int arr[], int left, int right)
{// 确定标准值保存起来int standard arr[left];//使用双指针从两端开始将比标准值大的数放到标准值右侧小于标准值的放到左侧while (left right){//从右到左(right到left)找到比标准值小的//如果遇到的值大于等于标准值则跳过 right--while (left right arr[right] standard){right--;}//找到了比标准值小的值arr[right]放到左边的left坑中arr[left] arr[right];//从左到右(left到right)找到比标准值大的//如果遇到的值小于等于标准值则跳过 leftwhile (left right arr[left] standard){left;}//找到了比标准值大的值arr[left]放到左边的right坑中arr[right] arr[left];}//中间的坑放入标准值arr[left] standard;//返回标准值的下标return left;
}void quicksort(int arr[], int left, int right)
{if (arr NULL || left right) return;int standard partition(arr, left, right);quicksort(arr, left, standard - 1);quicksort(arr, standard 1, right);
}void print(int arr[], int len)
{if (arr NULL || len 0) return;for (int i 0; i len; i){std::cout arr[i] ;}std::cout endl;
}int main()
{int arr[] { 5, 1, 7, 0, 4, 3, 4, 9, 6 };int len sizeof(arr) / sizeof(arr[0]);cout ------------------------------ endl 原始序列;print(arr, len);quicksort(arr, 0, len - 1);cout ------------------------------ endl 排序后序列;print(arr, len);return 0;
}二、区间分割法
#include iostream
#include cmath
using namespace std;int partition(int arr[], int left, int right)
{int nSmall left - 1;for (left; left right; left){if (arr[left] arr[right]){//小区间扩张if (nSmall ! left){arr[nSmall] arr[nSmall] ^ arr[left];arr[left] arr[nSmall] ^ arr[left];arr[nSmall] arr[nSmall] ^ arr[left];}}}//将标准值放入if (nSmall ! right){arr[nSmall] arr[nSmall] ^ arr[right];arr[right] arr[nSmall] ^ arr[right];arr[nSmall] arr[nSmall] ^ arr[right];}return nSmall;
}
void print(int arr[], int len)
{if (arr NULL || len 0) return;for (int i 0; i len; i){std::cout arr[i] ;}std::cout endl;
}int main()
{int arr[] { 5, 1, 7, 0, 4, 3, 4, 9, 6 };int len sizeof(arr) / sizeof(arr[0]);cout ------------------------------ endl 原始序列;print(arr, len);quicksort(arr, 0, len - 1);cout ------------------------------ endl 排序后序列;print(arr, len);return 0;
}三、快排的优化
1.标准值的选取选取三个数字头、尾、中间选择大小为中间值的2.分割到数据较少时不再使用快排使用插入排序3.使用栈取代递归4.尾递归
以下为使用了标准值三选一、按情况使用插入排序的优化后代码
class Solution {
public:void swap (vectorint nums, int i, int j) { int temp nums[i];nums[i] nums[j];nums[j] temp;} void insertSort (vectorint nums, int left, int right) {for (int i left1; i right; i) {int temp nums[i];int j i-1;for (j i-1; j 0; j--) {if (temp nums[j]) {nums[j1] nums[j];continue;} break;}nums[j1] temp;}} int place(vectorint nums,int left,int right){//标准值三选一int mid left (right-left)/2;if (nums[left] nums[right]) swap(nums,left,right);if (nums[mid] nums[right]) swap(nums,mid,right);if (nums[mid] nums[left]) swap(nums,mid,left); int standard nums[left];while(left right){while(leftrightnums[right]standard){right--;}nums[left] nums[right];while(leftrightnums[left]standard){left;}nums[right] nums[left];}nums[left] standard;return left;}void quickSort(vectorint nums,int left,int right){//分割到数据较少时不再使用快排使用插入排序if (right - left 5) {insertSort(nums,left,right);return;} if(nums.size() 0 || left right) return;int standard place(nums,left,right);quickSort(nums,left,standard-1);quickSort(nums,standard1,right);}vectorint sortArray(vectorint nums) {quickSort(nums,0,nums.size()-1);return nums;}
};大家的点赞、收藏、关注将是我更新的最大动力 欢迎留言或私信建议或问题。
大家的支持和反馈对我来说意义重大我会继续不断努力提供有价值的内容如果本文哪里有错误的地方还请大家多多指出(●◡●)
