选择排序

选择排序

        int[] arr = {3, 2, 4, 5, 1, 9, 5, 2};

        for (int i = 0; i < arr.length - 1; i++) {
            int index = i;
            //每次把最小的放最前面
            //第二趟的时候只需要从第二个开始，所以+i
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[index]) {
                    index = j;
                }
            }
            if (index != i) {
                int tmp = arr[index];
                arr[index] = arr[i];
                arr[i] = tmp;
            }

        }
        for (int result : arr) {
            System.out.println(result);
        }

冒泡排序

        int[] arr = {3, 2, 4, 5, 1, 9, 5, 2};
        for (int i = 0; i < arr.length - 1; i++) {
            //每次把最大的往后放
            //第一趟把最大的放最后，第二趟的时候只需要比较到倒数第二个所以-i
            for (int j = 0; j < arr.length - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    int tmp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = tmp;
                }
            }

        }
        for (int result : arr) {
            System.out.println(result);
        }

        //减少交换版本
        int[] arr = {3, 2, 4, 5, 1, 9, 5, 2};
        for (int i = 0; i < arr.length - 1; i++) {
            int maxIndex = 0;
            //每次从第二个往后找最大的，记录最大的下标
            //每趟比较到倒数第二个 -i
            for (int j = 1; j < arr.length - i; j++) {
                if (arr[maxIndex] < arr[j]) {
                    maxIndex = j;
                }
            }
            if (maxIndex != i) {
                int tmp = arr[maxIndex];
                arr[maxIndex] = arr[arr.length - i - 1];
                arr[arr.length - i - 1] = tmp;
            }
        }
        for (int result : arr) {
            System.out.println(result);
        }

插入排序

        int[] arr = {3, 2, 4, 5, 1, 9, 5, 2};
        for (int i = 1; i < arr.length; i++) {
            int pre = i - 1;
            int val = arr[i];
            while (pre >= 0 && val < arr[pre]) {
                arr[pre + 1] = arr[pre];
                pre--;
            }
            arr[pre + 1] = val;
        }
        for (int result : arr) {
            System.out.println(result);
        }

        int[] arr = {3, 2, 4, 5, 1, 9, 5, 2};
        for (int i = 1; i < arr.length; i++) {
            int j;
            int val = arr[i];
            for (j = i; j > 0 && val < arr[j - 1]; j--) {
                arr[j] = arr[j - 1];
            }
            arr[j] = val;
        }
        for (int result : arr) {
            System.out.println(result);
        }

qsort

   public static int partition(int[] arr, int l, int r) {
        int val = arr[l];
        while (l < r) {
            while (l < r && arr[r] >= val) {
                r--;
            }
            if (l < r) {
                arr[l] = arr[r];
            }
            while (l < r && arr[l] <= val) {
                l++;
            }
            if (l < r) {
                arr[r] = arr[l];
            }
        }
        arr[l] = val;
        return l;
    }

    public static void qSort(int[] arr, int l, int r) {
        if (l >= r) {
            return;
        }
        int index = partition(arr, l, r);
        qSort(arr, l, index - 1);
        qSort(arr, index + 1, r);

    }


        int[] arr = {3, 2, 4, 5, 1, 9, 5, 2};

        qSort(arr, 0, arr.length - 1);
        for (int result : arr) {
            System.out.println(result);
        }