交换排序

冒泡排序和快速排序

/**
 * @Author leijs
 * @date 2021/8/16
 */
public class ExchangeSort {
    public static void main(String[] args) {
        int[] arr = {1, 4, 3, 6, 8, 4, 9, 6, 2};
        int[] arr1 = bubbleSort(arr);
        for (int i = 0; i < arr1.length; i++) {
            System.out.print(arr1[i]);
        }
        System.out.println();
        int[] arr2 = quickSort(arr);
        for (int i = 0; i < arr2.length; i++) {
            System.out.print(arr2[i]);
        }
    }
    /**
     * 冒泡排序：
     * 对于当前还未排好序的范围内的全部数，自上而下对相邻的两个数依次进行比较和调整，
     * 让最大的数往下沉，较小的往上冒
     * 每当相邻的数比较之后发现和排序要求相反，则交换
     *
     * @param arr
     * @return
     */
    public static int[] bubbleSort(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr.length - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
        return arr;
    }
    /**
     * 快速排序
     * 选择一个基准元素，通过选择第一个元素或者最后一个元素，通过一次排序，
     * 将待排序的列分为两个部分，一部分比基准元素小，一部分比基准元素大
     * 此时基准元素在其排好序后的正确位置，然后再用同样的方法递归的排序划分的两部分
     *
     * @param arr
     * @return
     */
    public static int[] quickSort(int[] arr) {
        if (arr.length > 0) {
            quickSort(arr, 0, arr.length - 1);
        }
        return arr;
    }
    private static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int middle = getMiddle(arr, low, high);
            quickSort(arr, 0, middle - 1);
            quickSort(arr, middle + 1, high);
        }
    }
    private static int getMiddle(int[] arr, int low, int high) {
        int temp = arr[low];
        while (low < high) {
            // 找到比基准元素小的元素位置
            while (low < high && arr[high] >= temp) {
                high--;
            }
            arr[low] = arr[high];
            while (low < high && arr[low] <= temp) {
                low++;
            }
            arr[high] = arr[low];
        }
        arr[low] = temp;
        return low;
    }
}