快速排序的核心思想和Java实现

￡神魔★判官ぃ 2022-02-26 18:18 157阅读 0赞

**算法步骤**  
1、从数列中挑出一个元素，称为 “基准”（pivot）;  
2、重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；  
3、递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；  
在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。

这里有一个可以优化的点：  
就是基准的选择，可以不直接选择最左边的元素，也可以选择其他具有特别意义的数，比如中位数之类的，然后跟最左边的数字swap一下就可以按照原来的方法继续快排了。

**Java代码实现**

import java.util.Arrays;
    
    /**
     * author: zzw5005
     * date: 2019/2/28 16:25
     */
    
    /**
     * 核心思想:
     * 1、从数列中挑出一个元素，称为 “基准”（pivot）;
     *
     * 2、重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。
     * 在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
     *
     * 3、递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；
     *
     * 每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。
     */
    public class QuickSort{
    
        public int[] sort(int[] sourceArray){
            //对 arr 进行拷贝，不改变参数内容
            int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
    
            return quickSort(arr, 0, arr.length - 1);
        }
    
        private int[] quickSort(int[] arr, int left, int right) {
            if (left < right) {
                int partitionIndex = partition(arr, left, right);
                //对于枢纽值的左半部分和枢纽值的右半部分，分别递归调用函数进行快排
                quickSort(arr, left, partitionIndex - 1);
                quickSort(arr, partitionIndex + 1, right);
            }
            return arr;
        }
    
        /**
         * 将枢纽值 pivot 放到数组合适的位置。具体说，就是数组中，枢纽值大于在它左边的元素值，小于等于在它右边元素的值
         * @param arr
         * @param left
         * @param right
         * @return
         */
        private int partition(int[] arr, int left, int right) {
            //设定基准值（pivot）
            int pivot = left;
            int index = pivot + 1;  //index左边的值都小于等于pivot，右边的值都大于pivot
    
            for (int i = index; i <= right; i++) {
                if (arr[i] < arr[pivot]) {  //遇到小于pivot的值，就把index和i的值交换，index++
                    swap(arr, i, index);
                    index++;
                }
            }
            swap(arr, pivot, index - 1);  //将index-1与pivot交换，则此时pivot大于左边的值，小于右边的值
            return index - 1;
        }
    
        /**
         * 交换数组给定的两个索引的值
         * @param arr
         * @param i
         * @param j
         */
        private void swap(int[] arr, int i, int j) {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    
        public static void main(String[] args) {
            QuickSort quickSort = new QuickSort();
    
            int[] arr = {3,4,6,5,1,2};
            int[] newArr =  quickSort.sort(arr);
    
            for(int i : newArr){
                System.out.print(i + " ");
            }
        }
    }