java 快速排序

快速排序

对冒泡排序的一种改进
思路:
一趟排序后,选取一个中间值,数组被分为比中间值小的部分,比中间值大的部分;再对左右两部分分别递归排序
代码实现

import java.util.Arrays;

public class QuickSort {
    public static void main(String[] args) {
        int[] arr = {-9, 78, 0, 23, -567, 70};
        System.out.println("排序前---");
        System.out.println(Arrays.toString(arr));
        quickSort(arr, 0, arr.length - 1);
        System.out.println("排序后---");
        System.out.println(Arrays.toString(arr));
    }

    public static void quickSort(int[] arr, int start, int end) {
        //结束左右递归
        if (start < end) {
//找到基准数,中间值,标准数
            //把数组中第0个数字作为标准数
            //start从开始取标准数
            int stard = arr[start];
            //记录需要排序的下标,从开始到结尾
            int low = start;
            int high = end;
            //循环地去找比标准数大与小的数,结束条件为low==high
            while (low < high) {
                //先找高的这边
                //如果高的比标准数小则交换,如果大则下标往前走
                while (low < high && stard <= arr[high]) {
                    high--;
                }
                //结束循环时,就已经找到了要交换的数字下标
                //右边的数字换到左边
                arr[low] = arr[high];
                while (low < high && stard >= arr[low]) {
                    low++;
                }
                //左边的数字换到右边
                arr[high] = arr[low];
            }
            //当low与high重合时,标准数就要放入合适的位置
            //或arr[high]都可以
            arr[low] = stard;
            //递归处理左右两边的排序
            //左边 开始位置 --> 到低的位置
            quickSort(arr, start, low);
//右边 从低的位置加1 -->结束位置
            //或++low
            quickSort(arr, low + 1, end);
        }
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

无注释版

import java.util.Arrays;

public class TestQuickSort {
    public static void main(String[] args) {

        int[] arr = {-9, 78, 0, 23, -567, 70};
        System.out.println("排序前---");
        System.out.println(Arrays.toString(arr));
        Sort(arr, 0, arr.length - 1);
        System.out.println("排序后---");
        System.out.println(Arrays.toString(arr));
    }

    private static void Sort(int[] arr, int start, int end) {
        if (start < end) {
            int middle = arr[start];
            int left = start;
            int right = end;
            while (left < right) {
                while (left < right && middle <= arr[right]) {
                    right--;
                }
                arr[left] = arr[right];
                while (left < right && middle >= arr[left]) {
                    left++;
                }
                arr[right] = arr[left];
            }
            arr[left] = middle;
            Sort(arr, start, left);
            Sort(arr, left + 1, end);
        }
    }
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

参考腾讯课堂