快速排序

女爷i 2022-08-01 12:28 15阅读 0赞

关于快速排序的学习,请参考这一篇博文,讲得清楚明了:
http://blog.csdn.net/morewindows/article/details/6684558

快速排序,是冒泡排序的升级版,属于交换类排序。
原理,挖坑填数:
在待排序数列中,选定一个基准数。小于这个基准树的数据移到前面,大于这个基准数的放到后面,在分别对前面部分的数据,和后面部分的数据,进行选基准数移动。依次递归,可得到一个有序数列。
(每一部分,都和其所在部分的基准数比较,进行移动)
因此,快速排序是一种不稳定的排序算法。

算法的时间复杂度:O(N * logN)

代码即结果如下:

  1. #include <iostream>
  2. using namespace std;
  3. //快速排序,注意l和r是序号,而不是数值
  4. void quick_sort(int s[], int l, int r)
  5. {
  6. if (l < r)
  7. {
  8. int i = l, j = r, x = s[l];
  9. while (i < j)
  10. {
  11. while(i < j && s[j] >= x) // 从右向左找第一个小于x的数
  12. j--;
  13. // 跳出就说明,已找到 s[j] < x
  14. if(i < j)
  15. s[i++] = s[j];
  16. while(i < j && s[i] < x) // 从左向右找第一个大于等于x的数
  17. i++;
  18. if(i < j)
  19. s[j--] = s[i];
  20. }
  21. s[i] = x;
  22. quick_sort(s, l, i - 1); // 递归调用
  23. quick_sort(s, i + 1, r);
  24. }
  25. }
  26. void show(int a[],int n)
  27. {
  28. int i;
  29. for(i = 0; i < n; i++)
  30. cout << a[i] << ' ';
  31. cout << endl;
  32. }
  33. int main()
  34. {
  35. int a[10] = {
  36. 1,2,0,5,8,9,7,3,6,4};
  37. cout << "排序前:" << endl;
  38. show(a,10);
  39. cout << "排序后:" << endl;
  40. quick_sort(a,0,9);
  41. show(a,10);
  42. return 0;
  43. }

这里写图片描述

/点滴积累,我的一小步O(∩_∩)O~/

发表评论

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

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

相关阅读