当前位置:   article > 正文

分治思想之快速排序(Quicksort)_基于分治法思想的快速排序排序

基于分治法思想的快速排序排序

【分治算法】

【算法本质】

将一个大规模的问题分解为若干个规模较小的相同子问题,分而治之。

【解题思路】

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. 再对基准元素的左右两部分,分别进行上述过程。

【动画展示】

  • 先确定基准元素 6 ,然后指针 j 从后往前找第一个比基准元素小的数
    在这里插入图片描述
  • 指针 i 从左往右找第一个比基准元素大的元素在这里插入图片描述
  • 当两方都找到后,进行交换

在这里插入图片描述

  • 然后继续寻找

  • 直到两个指针指向同一个位置
    在这里插入图片描述
  • 将该位置与基准元素进行交换

这样我们的一趟快速排序就结束了,然后左右划分区间,重复上述过程

【C++代码实现】

  1. #include<iostream>
  2. using namespace std;
  3. int n;
  4. int nums[10];
  5. void QuickSort(int left, int right)
  6. {
  7. if (left > right)
  8. return;
  9. int begin = left;
  10. int end = right;
  11. int target = left;
  12. while (left < right)
  13. {
  14. //从右往左找,找到一个比target小的值
  15. while (left < right && nums[right] >= nums[target])
  16. {
  17. --right;
  18. }
  19. //从左往右找,找到一个比target大的值
  20. while (left < right && nums[left] <= nums[target])
  21. {
  22. ++left;
  23. }
  24. swap(nums[left], nums[right]);
  25. }
  26. swap(nums[target], nums[right]);
  27. QuickSort(begin, right - 1);
  28. QuickSort(right + 1, end);
  29. }
  30. int main()
  31. {
  32. cin >> n;
  33. for (int i = 1; i <= n; i++) cin >> nums[i];
  34. QuickSort(1, n);
  35. for (int i = 1; i <= n; i++) cout << nums[i] << " ";
  36. }

运行截图: 

动画展示部分摘自八大排序之快速排序C++详解/C++快速排序/快排_c++ 快速排序解析_不知名唐某人的博客-CSDN博客

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/喵喵爱编程/article/detail/842820
推荐阅读
相关标签
  

闽ICP备14008679号