快速掌握java排序算法-快速排序（图文）

Java  /  管理员 发布于 8年前   404

概念

快速排序属于交换排序，主要步骤是使用基准元素进行比较，把小于基准元素的移动到一边，大于基准元素的移动到另一边。从而把数组分成两部分，然后再从这两部分中选取出基准元素，重复上面的步骤。过程如下：

（推荐视频：java视频教程）

紫色：基准元素
绿色：大于基准元素
黄色：小于基准元素

这种思路叫做分治法。

基准元素

基准元素的选取可随机选取。下面使用中我会使用第一位的元素作为基准元素。

排序过程

排序拆分过程如下图：

紫色为基准元素，（每一轮都重新选取）
绿色为其他元素

第一轮

第二轮

第三轮

如上图所示：

若元素个数为n，因为排序过程中需要和全部元素都比较一遍，所以时间复杂度为O(n)，
而平均情况下排序轮次需要logn轮，因此快速排序的平均时间复杂度为O(nlogn)。

排序的实现方法

实现方法有双边循环法和单边循环法

双边循环法

首选选取基准元素(pivot)4，并设置指针left和right，指向数组最左和最右两个元素，如下：

第一次循环，先从right指针指向的数据(rightData)开始和基准元素比较
若 rightData >= pivot，则right指针向左移动，若 rightData < pivot，则right指针不移动，切换到left指针
left指针指向数据(leftData)与基准元素比较，若 leftData < pivot，则left指针向右移动，若 leftData > pivot，交换left和right指向的元素。

第一轮指针移动完后，得到如下结构：

然后 left和right指向的元素进行交换：

第一轮循环结束，重新切换到right指针，重复上述步骤。

第二轮循环后，得：

第三轮循环后，得：

第四轮循环后，得：

判断到left和right指针指向同一个元素，指针停止移动，使pivot和指针元素进行交换，得：

宣告该轮循环结束，并根据Pivot元素切分为两部分，这两部分的数组再根据上述步骤进行操作。

实现代码

public class DoubleSort {    public static void quickSort(int[] arr, int startIndex, int endIndex) {        //递归结束条件        if (startIndex >= endIndex) {return;        }        // 基准元素位置        int pivotIndex = partition(arr, startIndex, endIndex);        // 根据基准元素，分成两部分进行递归排序        quickSort(arr, startIndex, pivotIndex - 1);        quickSort(arr, pivotIndex + 1, endIndex);    }    public static int partition(int[] arr, int startIndex, int endIndex) {        // 取第一个元素为基准元素，也可以随机抽取        int pivot = arr[startIndex];        int left = startIndex;        int right = endIndex;        while (left != right) {// 控制right指针比较并左移while (left < right && arr[right] >= pivot) {    right--;}// 控制left指针比较并右移while (left < right && arr[left] <= pivot) {    left++;}// 交换left和right指针所指向的元素if (left < right) {    int temp = arr[right];    arr[right] = arr[left];    arr[left] = temp;}        }        arr[startIndex] = arr[left];        arr[left] = pivot;        return left;    }    public static void main(String[] args) {        int[] arr = new int[]{4, 7, 6, 5, 3, 2, 8, 1};        quickSort(arr, 0, arr.length - 1);        System.out.println(Arrays.toString(arr));    }}

单边循环法

双边循环法从数组的两边比较并交换元素，而单边循环法则从数组的一边遍历，一直往后比较和交换，实现起来更加的简单。
过程如下：

首先也是选取基准元素pivot（可以随机选择）
设置一个mark指针指向数组的起始位置，代表小于基准元素的区域边界（不理解的就把它理解成是等会用来交换元素的就好了）

原始数组如下：

从基准元素下一位开始遍历数组
如果该元素大于基准元素，继续往下遍历
如果该元素小于基准元素，mark指针往右移，因为小于基准元素的区域边界增大了1（即小于基准元素的多了1位），所以mark就 +1，并且该元素和mark指向元素进行交换。

遍历到元素3时，因为3 < 4，所以mark右移

然后交换元素

然后就继续遍历，根据上面的步骤进行判断，后面的过程就不写了。

实现代码

public class SingleSort {    public static void quickSort(int[] arr, int startIndex, int endIndex) {        //递归结束条件        if (startIndex >= endIndex) {return;        }        // 基准元素位置        int pivotIndex = partition(arr, startIndex, endIndex);        // 根据基准元素，分成两部分进行递归排序        quickSort(arr, startIndex, pivotIndex - 1);        quickSort(arr, pivotIndex + 1, endIndex);    }    /**     * 分治（单边循环法）     * @param arr     * @param startIndex     * @param endIndex     * @return     */    public static int partition(int[] arr, int startIndex, int endIndex) {        // 取第一个元素为基准元素，也可以随机抽取        int pivot = arr[startIndex];        int mark = startIndex;        for(int i = startIndex + 1; i< arr.length; i++) {if (pivot < arr[i]) {    continue;}mark ++;int temp = arr[mark];arr[mark] = arr[i];arr[i] = temp;        }        arr[startIndex] = arr[mark];        arr[mark] = pivot;        return mark;    }    public static void main(String[] args) {        int[] arr = new int[]{4, 7, 6, 5, 3, 2, 8, 1};        quickSort(arr, 0, arr.length - 1);        System.out.println(Arrays.toString(arr));    }}

总结

本人也是初次接触算法，慢慢的去理解算法的思路和实现过程后，真是为自己以往写的算法感到羞愧。该文章也是为了加深自己对快排算法的印象，若文章有不足之处，恳请各位在下方留言补充。感谢各位的阅读。Thanks♪(･ω･)ﾉ。

参考资料：《小灰的算法之旅》 第四章。

本文来自，java教程栏目，欢迎学习！

以上就是快速掌握java排序算法-快速排序（图文）的详细内容，更多请关注其它相关文章！