java简单快速排序实例解析

一、基本概念

      找出一个元素（理论上可以随便找一个）作为基准(pivot),然后对数组进行分区操作,使基准左边元素的值都不大于基准值,基准右边的元素值 都不小于基准值，如此作为基准的元素调整到排序后的正确位置。递归快速排序，将其他n-1个元素也调整到排序后的正确位置。最后每个元素都是在排序后的正 确位置，排序完成。所以快速排序算法的核心算法是分区操作，即如何调整基准的位置以及调整返回基准的最终位置以便分治递归。

二、选择基准元

固定基准元

      如果输入序列是随机的，处理时间是可以接受的。如果数组已经有序时，此时的分割就是一个非常不好的分割。因为每次划分只能使待排序序列减一，此时为最坏情况，快速排序沦为冒泡排序，时间复杂度为Θ(n^2)。而且，输入的数据是有序或部分有序的情况是相当常见的。因此，使用第一个元素作为基准元是非常糟糕的，应该立即放弃这种想法。

随机基准元

      这是一种相对安全的策略。由于基准元的位置是随机的，那么产生的分割也不会总是会出现劣质的分割。在整个数组数字全相等时，仍然是最坏情况，时间复杂度是O(n^2）。实际上，随机化快速排序得到理论最坏情况的可能性仅为1/(2^n）。所以随机化快速排序可以对于绝大多数输入数据达到O（n×log(n))的期望时间复杂度。

三数取中

      最佳的划分是将待排序的序列分成等长的子序列，最佳的状态我们可以使用序列的中间的值，也就是第N/2个数。可是，这很难算出来，并且会明显减慢快速排序的速度。这样的中值的估计可以通过随机选取三个元素并用它们的中值作为基准元而得到。事实上，随机性并没有多大的帮助，因此一般的做法是使用左端、右端和中心位置上的三个元素的中值作为基准元。

三、partition算法

      partition算法是快速排序的核心，在学习快排之前，可以先学习一下这个算法。下面先贴代码:

  public int partition(int[] num,int left,int right){    if(num==null || num.length<=0 || left<0 || right>=num.length){      return 0;    }    int prio=num[left+(right-left)/2];  //获取数组中间元素的下标    while (left<=right){         //从两端交替向中间扫描      while (num[left]<prio)        left++;      while (num[right]>prio)        right--;      if (left<=right){        swap(num,left,right);    //最终将基准数归位         left++;        right--;      }    }    return left;  }

猜你喜欢

AI推送时光机

java简单快速排序实例解析

后端开发2023-05-31

Python实现快速排序算法及去重的快速排序的简单示例

后端开发2022-06-04

Java快速排序案例讲解

后端开发2024-04-02

Python快速排序算法实例分析

后端开发2022-06-04

Excel如何简单快速地实现颜色排序

后端开发2024-04-17

Java实现快速排序和堆排序的示例代码

后端开发2022-12-22

Java快速排序与归并排序及基数排序图解示例

后端开发2024-04-02

随机化快速排序（Java 实例代码）

后端开发2023-08-31

图文详解JAVA实现快速排序

后端开发2024-04-02

java实现快速排序图文详解

后端开发2024-04-02

排序算法图解之Java快速排序的分步刨析

后端开发2022-11-13

比较排序之快速排序(实例代码)

后端开发2023-05-31

C++快速排序算法简明理解

后端开发2024-04-02

Java归并排序和快速排序怎么实现

后端开发2023-06-04

图文解说JS冒泡排序 简单明了快速掌握

后端开发冒泡排序算法2024-12-02

Java的堆排序、快速排序、归并排序怎么实现

后端开发2023-06-26

JAVA十大排序算法之快速排序详解

后端开发2024-04-02

快速排序的算法思想及Python版快速排序的实现示例

后端开发2022-06-04

java中如何实现快速排序

后端开发2018-05-13

Java排序算法之归并排序简单实现

后端开发2023-05-30