快速排序

快速排序

快速排序是交换排序（冒泡排序也是交换排序）的一种,时间复杂度可达到$(nlog_2n)$。快速排序的最坏运行情况是 O(n²)，比如说顺序数列的快排。但它的平摊期望时间是 O(nlogn)，且 O(nlogn) 记号中隐含的常数因子很小，比复杂度稳定等于 O(nlogn) 的归并排序要小很多。所以，对绝大多数顺序性较弱的随机数列而言，快速排序总是优于归并排序。

思路在于分治的策略，该方法的基本思想是：

1．先从数列中取出一个数作为基准数。 找
2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。 分
3．再对左右区间重复第二步，直到各区间只有一个数。 重复

Java代码

package sort.exchange;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

/**
 * @author ShaoYJ
 * @date 2022/10/27 周四
 * @desc 得到升序结果
 */
public class QuickSort {
    public static void main(String[] args) {
        // Integer[] arr = scanNum();
        Integer[] arr = {6, 54, 32, 21, 9, 100};
        // Integer[] arr = {5,4,3,2,1};
        System.out.println("排序前:" + Arrays.toString(arr));
        System.out.println("排序后:" + Arrays.toString(quickSort(arr, 0, arr.length-1)));
    }

    public static Integer[] quickSort(Integer[] arr, int low, int high) {
        if (low > high) {
            return arr;
        }
        int i = low;
        int j = high;
        Integer t;
        //  基址对应元素值
        Integer temp = arr[low];
        //  来回进行交换
        while (i < j) {
//            先从后向前遍历找到符合条件的值
            while (temp <= arr[j] && i < j) {
                j--;
            }
//           从前往后遍历找到符合条件的值
            while (temp >= arr[i] && i < j) {
                i++;
            }
            if (i < j) {
                t = arr[i];
                arr[i] = arr[j];
                arr[j] = t;
            }
        }

        arr[low] = arr[i];
        arr[i] = temp;
        quickSort(arr,low,j-1);
        quickSort(arr,j+1,high);

        return arr;
    }

    public static Integer[] scanNum() {
        Scanner sc = new Scanner(System.in);
        ArrayList<Integer> list = new ArrayList<>();
        System.out.print("输入一串数字，空格分开，以#结束:");
        while (!sc.hasNext("#")) {
            int a = sc.nextInt();
            list.add(a);
        }
//       list 转 Integer : 提供首地址即可
        return list.toArray(new Integer[0]);
    }

}

运行结果

总结

核心思想 分治, 以基准为中心，两头交换，左侧的统一大于（或小于）基准，右侧相反同理。