快速排序【Java算法】

淡淡的烟草味﹌ 2023-10-14 14:35 12阅读 0赞

#### 文章目录 ####

*   *  1. 概念
     *  2. 思路
     *  3. 代码实现

### 1. 概念 ###

> 快速排序是一种比较高效的排序算法，采用 “分而治之” 的思想，通过多次比较和交换来实现排序，在一趟排序中把将要排序的数据分成两个独立的部分，对这两部分进行排序使得其中一部分所有数据比另一部分都要小，然后继续递归排序这两部分，最终实现所有数据有序。

### 2. 思路 ###

① 给出一组待排序序列，我们取该序列的第一个元素为基准值。什么是基准值？就是相当于参考物吧。接着再取两个哨兵，什么是哨兵？暂且当它为指针吧；

② 那么这个序是怎么个排法？首先，我们在序列的最左边和最右边各放一个哨兵，我们分别称它们为 left 和 right，left 从左往右走寻找比基准值大的数，right 从右往左走寻找比基准值小的数；

③ 规定第一步应该让 right 先迈出，我们让它一直往左走，走到什么地步？直到它找到了比基准值小的数为止，就停下来。right 停下来之后，就轮到 left 走了，同样道理，当 left 找到了比基准值大的数时，它也停了下来，left 和 right 都停了，接下来，交换这两个位置的数值，第一轮互相奔赴的旅途结束；

④ 第一轮结束后，还有下一轮，现在它们两个都停在半路上，没有见到彼此，路途遥远继续走。同样的方法，left 继续 ++ 向右走，right- - 向左走，满足条件时等待双方都停下来，交换数值，交换完继续走；

⑤ 以上所有的奔赴过程，我们都通过 while 循环来实现。其中，外层 while 循环控制双方交换完数值之后继续奔赴，退出条件就是 left 和 right 相撞的那一刻。内层两个 while 循环控制它们各自从一个停止点到另一个停止点的行走过程，退出条件是找到下一个停止点的时候。相当于外层循环发号施令，说开始走，于是内层循环听到了指令，就让 left 和 right 各自走到了自己的下一个停止位置，交换数值之后，静等外层循环的指令，才可以再到下一个目标点；

⑥ 当 left == right 时，循环结束，我们把 left 和 right 相遇位置的数值与基准值互换一下，此时，整体上基准值左边的数均小于基准值右边的数，但是左右两边各自的排序是乱的；

⑦ 道理是一样的，此时我们可以从基准处将序列分为两部分，然后用递归的方法排序这两部分，最终实现所有数据有序排列。

### 3. 代码实现 ###

import java.util.Arrays;
    
    public class Main {
        
        public static void main(String[] args) {
        
            int[] arr = {
        3, 2, 9, 11, 17, 4, 13, 7, 5, 1, 12};
            int[] newArr = quickSort(arr, 0, arr.length - 1);
            System.out.println(Arrays.toString(newArr));
        }
    
        public static int[] quickSort(int[] arr, int low, int high) {
        
            if (low > high) {
        
                return arr;
            }
            int base = arr[low];
            int left = low;
            int right = high;
            while (left != right) {
        
                while (arr[right] >= base && left < right) {
        
                    right--;
                }
                while (arr[left] <= base && left < right) {
        
                    left++;
                }
                int temp;
                temp = arr[right];
                arr[right] = arr[left];
                arr[left] = temp;
            }
            arr[low] = arr[left];
            arr[left] = base;
            quickSort(arr, low, left - 1);
            quickSort(arr, right + 1, high);
            return arr;
        }
    }

![在这里插入图片描述][d832d8ecb98647afb5b052a94e52b7f0.png]

[d832d8ecb98647afb5b052a94e52b7f0.png]: https://img-blog.csdnimg.cn/d832d8ecb98647afb5b052a94e52b7f0.png