常用排序算法之快速排序

拼搏现实的明天。 2022-02-01 08:29 185阅读 0赞

package com.dalingjia.Interview.sort;
    /**
     * 快速排序
     */
    public class QuickSort {
        /**
         *
         * @param arr       需要排序的数组
         * @param left      数组第一个数
         * @param right     数组最后一个数
         */
        public static void quickSort(int[] arr, int left , int right){
    
            int i = 0;      //哨兵i所处的位置
            int j = 0;      //哨兵j所处的位置
            int mark = 0;   //基准数
            int temp = 0;
    
            if(left >= right){
                return;
            }
            i = left;
            j = right;
            mark = arr[left];
    
            //当i<j说明没有相遇
            while (i < j){
                while (i < j && arr[j] >= mark){
                    j--;
                }
                while (i < j && arr[i] <= mark){
                    i++;
                }
                //哨兵i,j没有相遇，且分别找到大于和小于基准数的数，进行交换
                if(i < j){
                    temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
            }
    
            //当i==j说明已经相遇，和基准数进行交换
            arr[left] = arr[i];
            arr[i] = mark;
    
            //递归排列子数组
            quickSort(arr, left, i - 1);
            quickSort(arr, i+1, right);
    
        }
        public static void main(String[] args) {
            int[] arr = new int[]{6, 1, 2 ,7 ,9 ,3 ,4 ,6 ,10 ,8};
            quickSort(arr, 0, arr.length-1);
            for (int i : arr){
                System.out.print(i + ",");
            }
        }
    }

注意：**如果选定的基数是最左边的，那么快排一定要从最右边开始**。是为了保证交换时的那个数是小于等于基数的。看下面的例子：

int[] arr = {4, 2, 3, 9};

按照从小到大排序，选定左边的4位基数，如果从左边开始寻找第一个大于4的数，找到的是9，然后从右边开始找数，找到9就停止了，9和4进行交换，得到数组：9，2，3，4；显然不是从小到大的排序，不是我们相要的结果；  
但如果从右边开始排序，寻找一个小于基数4的数，找到2；从左边开始找一个大于基数4的数，找到2停止；2和4交换，得到数组：2，4，3，9。没毛病！！！

另外，**Arrays.sort()排序就是基于快速排序的**。

Java提供了Collections.sort()来对数组进行排序，其内部采取的是归并排序；此外还提供了Arrays.sort()，Arrays.sort()采用了2种排序算法 – 基本类型数据使用快速排序法，对象数组使用归并排序。