润滑油网站建设,游戏制作公司排名,latex wordpress 怎么用,阆中网站建设快速排序#xff1a;
1.首先找一个基准点#xff08;一般选取最左边第一个#xff09;
2.先从后往前遍历#xff0c;找到第一个小于基准值的元素#xff1b;
3.再从前往后#xff0c;找到第一个大于基准值的元素#xff1b;
4.将这两个元素两两交换
5.当i与j相遇时…快速排序
1.首先找一个基准点一般选取最左边第一个
2.先从后往前遍历找到第一个小于基准值的元素
3.再从前往后找到第一个大于基准值的元素
4.将这两个元素两两交换
5.当i与j相遇时说明找到了排序后当前这个基准值的正确位置将基准点进行归位
6.开始新的一轮以上一轮的基准点为中轴分成左边区域和右边区域分别选取一个新的基准点对新的基准点进行归位即可。 非递归利用队列实现
//进行分区也就是找到基准点排序后的正确位置
int pation(vectorint nums, int left, int right)
{int tmp nums[left];//先将基准点保存起来//循环结束条件i和j相遇while (left right){//从后往前找找到第一个小于基准点的下标while (leftright nums[right]tmp)--right;//将当前这个值赋给左下标的元素if (left right) nums[left] nums[right];//从前往后找到第一个大于基准值的下标while (left right nums[left] tmp)left;将当前这个值赋给右下标的元素if (left right) nums[right] nums[left];}//此时left和right就是基准值的正确位置//将基准值归位nums[left] tmp;return left;
}
//非递归
void quickSort(vectorint nums, int left, int right)
{queueint qu;//通过队列实现非递归如果用栈就是先放右边的值再放左边的值qu.push(left);qu.push(right);while(!qu.empty()){left qu.front(); qu.pop();right qu.front(); qu.pop();//分区int pos pation(nums, left, right);//对左边序列进行排序if (left pos - 1){qu.push(left);qu.push(pos - 1);}//对右边序列进行排序if (right pos 1){qu.push(pos 1);qu.push(right);}}
}
int main()
{cout 请输入数组大小 endl;int n;cin n;vectorint nums(n);for (int i 0; i n; i){cin nums[i];}quickSort(nums, 0, n - 1);cout 排序后的数组 endl;for (auto i:nums){cout i ;}cout endl;return 0;
}
递归
void dfs(vectorint nums, int left, int right)
{//左右边界相遇时直接return结束if (left right) return;int key nums[left];//保存基准值int i left, j right;while (i j){//从后往前找第一个小于基准值的元素while (nums[j]nums[left] ij){j--;}//从前往后找第一个大于基准值的元素while (nums[i] nums[left] ij){i;}//左右边界没有相遇将这两个值两两交换if (i j){swap(nums[j], nums[i]);}}//此时循环结束i或j下标就代表基准值的正确下标位置nums[left] nums[i];nums[i] key;//递归左边区域dfs(nums, left, i - 1);//递归右边区域dfs(nums, i 1, right);
} 注意
快速排序的时间复杂度通常情况下是O(nlogn)
但在特殊情况下比如选取的这个基准点刚好是最大值或是最小值时对n个元素排序需要遍历n次此时时间复杂度为O(n*n);
