关于java:排序算法之快速排序

4次阅读

共计 2185 个字符，预计需要花费 6 分钟才能阅读完成。

疾速排序是由东尼·霍尔所倒退的一种排序算法。在均匀情况下，排序 n 个我的项目要 Ο(nlogn) 次比拟。在最坏情况下则须要 Ο(n2) 次比拟，但这种情况并不常见。事实上，疾速排序通常显著比其余 Ο(nlogn) 算法更快，因为它的外部循环（inner loop）能够在大部分的架构上很有效率地被实现进去。

疾速排序应用分治法（Divide and conquer）策略来把一个串行（list）分为两个子串行（sub-lists）。

从数列中挑出一个元素，称为 “ 基准 ”（pivot）;

从新排序数列，所有元素比基准值小的摆放在基准后面，所有元素比基准值大的摆在基准的前面（雷同的数能够到任一边）。在这个分区退出之后，该基准就处于数列的两头地位。这个称为分区（partition）操作；

递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；

public static void main(String[] args) {
        // 初始化数组
        int[] arr = {5, 3, 1, 4, 2, 7, 8, 6, 10, 9};
        quickSort(arr,0,arr.length -1);
        System.out.println(Arrays.toString(arr));

    }

    private static void quickSort(int[] arr,int l, int r){if(l >= r){return;}

        int left = l; 
        int right = r; 
        int pivot = arr[left];

        while(left < right){while(left < right && arr[right] >= pivot){right --;}

            if(left < right){arr[left] = arr[right];
            }

            while (left < right && arr[left] <= pivot){left ++;}

            if (left < right){arr[right] = arr[left];
            }else{arr[left] = pivot;
            }
        }

        quickSort(arr,l,right -1);
        quickSort(arr,right + 1,r);
    }

正文版本：

 public static void main(String[] args) {
        // 初始化数组
        int[] arr = {5, 3, 1, 4, 2, 7, 8, 6, 10, 9};
        quickSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));

    }


    private static void quickSort(int[] arr, int l, int r) {if (l >= r) {return;}

        int left = l; // 0
        int right = r; // 9
        int pivot = arr[left]; // 5

        while (left < right) {
            /**
             *  第一次循环：0 < 9 && arr[right] (9)   9 >= 5  条件满足  9 --  = 8
             *  第二次循环：0 < 8 && arr[right] (8)   10 >= 5 条件满足  8 --  = 7
             *  第三次循环：0 < 7 && arr[right] (7)   6 >= 5  条件满足  7 --  = 6
             *  第四次循环：0 < 6 && arr[right] (6)   8 >= 5  条件满足  6 --  = 5
             *  第五次循环：0 < 5 && arr[right] (5)   7 >= 5  条件满足  5 --  = 4
             *  第六次循环：0 < 4 && arr[right] (4)   2 >= 5  条件不满足  此时 left = 0; right = 4
             */
            while (left < right && arr[right] >= pivot) {right--;}

            /**
             *  0 < 4
             */
            if (left < right) {
                /**
                 *  arr[left] = 5
                 *  arr[right] = 2
                 *  执行之后，数组变成如下：*  {2, 3, 1, 4, 2, 7, 8, 6, 10, 9};
                 */
                arr[left] = arr[right];
            }

            /**
             *  第一次循环：0 < 4 && arr[left] (2) <= 5 条件满足  0 ++  = 1
             *  第二次循环：1 < 4 && arr[left] (3) <= 5 条件满足  1 ++  = 2
             *  第三次循环：2 < 4 && arr[left] (1) <= 5 条件满足  2 ++  = 3
             *  第四次循环：3 < 4 && arr[left] (4) <= 5 条件满足  3 ++  = 4
             *  第四次循环：4 < 4 条件不满足，此时 left = 4; right = 4
             */
            while (left < right && arr[left] <= pivot) {left++;}

            /**
             *  4 < 4 不满足条件进入 else
             */
            if (left < right) {arr[right] = arr[left];
            } else {
                /**
                 * arr[left] = 2;
                 * pivot = 5;
                 * arr[left] = 5;
                 * 此时数组变成如下：* {2, 3, 1, 4, 5, 7, 8, 6, 10, 9};
                 */
                arr[left] = pivot;
            }
        }

        /**
         * l = 0
         * right = 4
         * {2, 3, 1, 4};
         * quickSort(arr,0,4-1);
         * 排序基准左侧的数
         */
        quickSort(arr, l, right - 1);
        /**
         * right = 4
         * r = 9
         * {7, 8, 6, 10, 9};
         * quickSort(arr,4 + 1,9);
         * 排序基准右侧的数
         */
        quickSort(arr, right + 1, r);
    }