排序算法之快速排序

小咪咪 2022-11-03 04:11 264阅读 0赞
  1. 快速排序。
  2. * 从数组中取出一个基准数,遍历数组中的每个元素,与基准数比较大小,将小于基准数的元素放在其左侧,大于基准数的元素放在其右侧,
  3. * 在分好后的两侧内递归执行上述操作
  4. 时间复杂度O(nlog2n);
  5. 空间复杂度O(log2n);
  6. **不稳定
  1. static void quickSort(int[] array, int left, int right) {
  2. if (left >= right) {
  3. return;
  4. }
  5. int i = left, j = right, x = array[left];
  6. while (i < j) {
  7. // 从右向左找第一个小于x的数
  8. while (i < j && array[j] >= x) {
  9. j--;
  10. }
  11. if (i < j) {
  12. array[i++] = array[j];
  13. }
  14. // 从左向右找第一个大于等于x的数
  15. while (i < j && array[i] < x) {
  16. i++;
  17. }
  18. if (i < j) {
  19. array[j--] = array[i];
  20. }
  21. }
  22. array[i] = x;
  23. // 递归调用此方法排序左侧部分
  24. quickSort(array, left, i - 1);
  25. // 递归调用此方法排序右侧部分
  26. quickSort(array, i + 1, right);
  27. }

发表评论

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

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

相关阅读

    相关 排序算法快速排序

    快速排序是一种基于分治思想的排序算法。它的基本思想是通过一趟排序将待排数据分割成独立的两部分,其中一部分的所有元素都比另一部分的所有元素小,然后再分别对这两部分继续进行排序,重

    相关 排序算法快速排序

    \[交换排序-快速排序\] 1.算法思想: 选择一个元素作为基准,先从右向左遍历数组寻找比基准小的数a,然后从左向右寻找比基准大的数b,交换a和b的值,当左右会面

    相关 排序算法快速排序

    > 快速排序。 > 从数组中取出一个基准数,遍历数组中的每个元素,与基准数比较大小,将小于基准数的元素放在其左侧,大于基准数的元素放在其右侧, >

    相关 排序算法快速排序

    同样的先上这张图  ![Center][] 下面分析交换排序之快速排序: 快速排序的思想是先选择一个基准元素(一般取第一个元素),然后对剩下的元素作两端遍历,左边找

    相关 排序算法快速排序

    快速排序的基本思想是:通过一趟排序将要排序的[数据分割][Link 1]成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行

    相关 排序算法快速排序

    快速排序是冒泡排序的改进版,也是最好的一种内排序,也是作为程序员必须掌握的一种排序方法。 快速排序的基本思想是 > 1、先从数列中取出一个数作为基准数 > 2、分区过程,

    相关 排序算法快速排序

    快速排序是一种高效的排序算法,它采用分而治之的思想,把大的拆分成小的,小的再拆分为更小的。 其原理是:对于给定的数组,通过一趟排序之后,将原序列分为两部分,其中前一部分的所