(排序算法总结)快速排序c++实现--将未排序部分的最后一个数作为主元

今天药忘吃喽~ 2022-06-01 01:26 29阅读 0赞
  1. #include <iostream>
  2. using namespace std;
  3. int Partition(int arr[],int low,int high)
  4. { int x=arr[high];
  5. int mid=low-1;
  6. for(int i=low;i<high;i++)
  7. { if(arr[i]<x)
  8. {mid++;
  9. swap(arr[i],arr[mid]);
  10. }
  11. }
  12. swap(arr[high],arr[mid+1]);
  13. return mid+1;
  14. }
  15. void QuickSort(int arr[],int low,int high)
  16. { int k;
  17. if(low<high)
  18. { k = Partition(arr,low,high);//k表示左右区间排序完成之后主元的位置
  19. QuickSort(arr,low,k-1);
  20. QuickSort(arr,k+1,high);
  21. }
  22. return;
  23. }
  24. int main()
  25. { int array1[]={2,4,3,6,15,7,9,13,7};
  26. int sizearray = sizeof(array1) /sizeof(int);
  27. //快速排序
  28. int low=0;
  29. int high=sizearray-1;
  30. QuickSort(array1,low,high);
  31. for(int i=0;i<sizearray;i++)
  32. cout << array1[i] << endl;
  33. return 0;
  34. }

运行结果:

SouthEast

这只是快速排序的一种实现方法,其他请参考https://www.cnblogs.com/mfryf/archive/2012/08/06/2625300.html

注意:其中swap函数是c++标准库自带的函数,定义方式为swap(T&a,T&b),表示引用传递,因此调用的时候不应该写成swap(&x,&y)。详细请参考http://blog.csdn.net/gdut2015go/article/details/49094741

注意:快速排序算法的时间复杂度是O(nlogn),证明方法比较难,想要研究的话可以自行百度。

SouthEast 1

70

https://blog.csdn.net/zhyh1435589631/article/details/51374083

不稳定排序算法记忆口诀:快些选队(快速排序,希尔排序,选择排序,堆排序)

发表评论

表情:
评论列表 (有 0 条评论,29人围观)

还没有评论,来说两句吧...

相关阅读

    相关 排序算法——快速排序

    排序算法——快速排序 > 快速排序通过一趟排序将待排序序列分隔成独立的两部分,其中一部分序列的关键字均比另一部分的关键字小,则可分别对这两部分记录继续进行排序,以达到整个

    相关 排序算法——快速排序

    前言 快速排序采用了分治法,即将原问题划分成为若干个规模更小且与原问题相似的子问题,然后递归地解决这些子问题,最后将他们组合起来。 快速排序的思想是:假设数据元素存放在

    相关 排序算法---快速排序

    基本思路: 快速排序,数组冲两边出发。 首先取一个关键字。 在第一次排序后。 大于和小于 关键字的各在 关键字两边。 然后在对两边 重复上面步骤,取关键字,排序。 直