java 快速排序

你的名字 2022-06-14 08:47 142阅读 0赞

快排简介：

通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，直到每一部分的元素个数为1为止。

java实现：

public static void main(String[] args) {
            int[] rawArr = {49, 38, 65, 97, 76, 13, 27, 49};
            new Demo().quickSort(rawArr, 0, rawArr.length - 1);
            for (int i = 0; i < rawArr.length; i++) {
                System.out.println(rawArr[i]);
            }
        }
    
        public void quickSort(int[] arr, int left, int right) {
            // 取得第一个数为基准数
            int i = left, j = right, temp = arr[left];
            // 一趟排序
            while (i < j) {
                // 从右边开始，取得第一个小于基准数的元素的下标
                while (i < j && temp <= arr[j]) {
                    j--;
                }
                // 交换该元素与基准数，此时第一个比基准数小的数字在最左边，此数不需要再在这一趟排序中参与，故i++
                if (i < j) {
                    arr[i] = arr[i] ^ arr[j];
                    arr[j] = arr[i] ^ arr[j];
                    arr[i] = arr[i] ^ arr[j];
                    i++;
                }
                // 从左边开始，取得第一个大于基准数的元素的下标
                while (i < j && temp >= arr[i]) {
                    i++;
                }
                // 交换该元素与基准数，此时第二个比基准数小的数字在最右边，此数不需要再在这一趟排序中参与，故i--
                if (i < j) {
                    arr[i] = arr[i] ^ arr[j];
                    arr[j] = arr[i] ^ arr[j];
                    arr[i] = arr[i] ^ arr[j];
                    j--;
                }
            }
            //一趟排序完成，此时i>=j，如果i不为最左边的数的下标，这个数组的左边还要进行一趟排序，即这个数组的基准数的左边元素数量大于1
            if (i > left)
                quickSort(arr, left, j - 1);
            //一趟排序完成，此时i>=j，如果j不为最右边的数的下标，这个数组的右边还要进行一趟排序，即这个数组的基准数的右边元素数量大于1
            if (j < right)
                quickSort(arr, i + 1, right);
        }