赞
踩
将一个大规模的问题分解为若干个规模较小的相同子问题,分而治之。
1.分解
将要解决的问题分解为若干个规模较小、相互独立、与原问题形式相同的子问题。
2.治理
求解各个子问题。由于各个子问题与原问题形式相同,只是规模较小而已,而当子问题划分得足够小时,就可以用简单的方法解决。
3.合并
按原问题的要求,将子问题的解逐层合并构成原问题的解。
给定一个整数数组nums,请利用快速排序算法将该数组升序排列
示例1:
输入:nums=[6,1,2,7,9,3,4,5,10,8]
输出:[1,2,3,4,5,6,7,8,9,10]
快速排序的基本思想:先确定一个基准元素,通过一趟排序将要排序的数组分割成以基准元素为轴心的两部分,前半部分比基准元素小,后半部分比基准元素大,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,最终得到一个有序数组。
1. 默认数组的第一个元素作为基准元素;
2. 设置双指针 i、j,排序开始时 i=0,j=N-1;
3. 指针 i 从前往后找第一个比基准元素大的元素;指针 j 从后往前找第一个比基准元素小的元素;
4. 当找到一个比基准元素大的元素和一个比基准元素小的元素时,交换两个数据;
5. 直到两个指针指向同一位置,交换基准元素与指针指向的元素,基准元素将数组划分为两个部分,本趟排序结束;
6. 再对基准元素的左右两部分,分别进行上述过程。
这样我们的一趟快速排序就结束了,然后左右划分区间,重复上述过程
- #include<iostream>
- using namespace std;
- int n;
- int nums[10];
- void QuickSort(int left, int right)
- {
- if (left > right)
- return;
- int begin = left;
- int end = right;
- int target = left;
- while (left < right)
- {
- //从右往左找,找到一个比target小的值
- while (left < right && nums[right] >= nums[target])
- {
- --right;
- }
- //从左往右找,找到一个比target大的值
- while (left < right && nums[left] <= nums[target])
- {
- ++left;
- }
- swap(nums[left], nums[right]);
- }
- swap(nums[target], nums[right]);
- QuickSort(begin, right - 1);
- QuickSort(right + 1, end);
- }
- int main()
- {
- cin >> n;
- for (int i = 1; i <= n; i++) cin >> nums[i];
- QuickSort(1, n);
- for (int i = 1; i <= n; i++) cout << nums[i] << " ";
- }

运行截图:
动画展示部分摘自八大排序之快速排序C++详解/C++快速排序/快排_c++ 快速排序解析_不知名唐某人的博客-CSDN博客
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。