处处逢归路，头头达故乡；本来成现事，何必待思量。

手撕三种经典的排序

快速排序

核心代码模式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {

    public void dfs(int[] nums, int l, int r){
        if(l >= r) return ;
        int i = l - 1, j = r + 1, x = nums[(l + r) >> 1];
        while(i < j){
            do i ++; while(nums[i] < x);
            do j --; while(nums[j] > x);
            if(i < j){
                int t = nums[i];
                nums[i] = nums[j];
                nums[j] = t;
            }
        }
        dfs(nums, l, j);
        dfs(nums, j + 1, r);
    }

    public int[] sortArray(int[] nums) {
        int n = nums.length;
        dfs(nums, 0, n - 1);
        return nums;
    }
}

ACM模式

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
public class quicksort {

    public static void dfs(int[] nums, int l, int r){
        if(l >= r) return ;
        int i = l - 1, j = r + 1, x = nums[(l + r) >> 1];
        while(i < j){
            do i ++; while(nums[i] < x);
            do j --; while(nums[j] > x);
            if(i < j) {
                int t = nums[i];
                nums[i] = nums[j];
                nums[j] = t;
            }
        }
        dfs(nums, l, j);
        dfs(nums, j + 1, r);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] nums = new int[n];
        for(int i = 0; i < n; i ++) nums[i] = sc.nextInt();
        dfs(nums, 0, n - 1);
        for(int i = 0; i < n; i ++) {
            System.out.printf("%d ", nums[i]);
        }
    }
}

归并排序

核心代码模式

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
class Solution {
    int[] t;
    public void dfs(int[] nums, int l, int r){
        if(l >= r) return;
        int n = nums.length;
        int k = 0, mid = (l + r) >> 1;
        dfs(nums, l, mid);
        dfs(nums, mid + 1, r);
        int i = l, j = mid + 1;
        while(i <= mid && j <= r){
            if(nums[i] <= nums[j]) t[k ++] = nums[i ++];
            else t[k ++] = nums[j ++];
        }
        while(i <= mid) t[k ++] = nums[i ++];
        while(j <= r) t[k ++] = nums[j ++];
        for(int a = l, b = 0; a <= r;){
            nums[a ++] = t[b ++]; 
        }
    }

    public int[] sortArray(int[] nums) {
        int n = nums.length;
        t = new int[n];
        dfs(nums, 0, n - 1);
        return nums;
    }
}

ACM模式

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
public class mergesort {

    static void dfs(int[] nums, int l, int r){
        int n = nums.length;
        int[] tmp = new int[n];
        if(l >= r) return;
        int mid = (l + r) >> 1;
        dfs(nums, l, mid);
        dfs(nums, mid + 1, r);
        int i = l, j = mid + 1, k = 0;
        while(i <= mid && j <= r){
            if(nums[i] <= nums[j]) tmp[k ++] = nums[i ++];
            else tmp[k ++] = nums[j ++];
        }
        while(i <= mid) tmp[k ++] = nums[i ++];
        while(j <= r) tmp[k ++] = nums[j ++];
        for(int a = l, b = 0; a <= r;) {
            nums[a ++] = tmp[b ++];
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] nums = new int[n];
        for(int i = 0; i < n; i ++) nums[i] = sc.nextInt();
        dfs(nums, 0, n - 1);
        for(int i = 0; i < n; i ++) System.out.printf("%d ", nums[i]);
    }
}

堆排序

核心代码模式

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
class Solution {
    int n, len;

    public void down(int[] nums, int u){
        int t = u;
        if(2 * u <= n && nums[2 * u - 1] < nums[t - 1]) t = 2 * u;
        if(2 * u + 1 <= n && nums[2 * u] < nums[t - 1]) t = 2 * u + 1;
        if(t != u){
            int tmp = nums[t - 1];
            nums[t - 1] = nums[u - 1];
            nums[u - 1] = tmp;
            down(nums, t);
        }
    }

    public int[] sortArray(int[] nums) {
        n = nums.length;
        len = n;
        int[] res = new int[n];
        for(int i = n / 2; i >= 1; i --) down(nums, i);
        for(int i = 1; i <= len; i ++){
            res[i - 1] = nums[0];
            nums[0] = nums[n - 1];
            n --;
            down(nums, 1);
        }
        return res;
    }
}

ACM模式

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
public class Heapsort {
    private static int n;
    private static int[] nums;

    static void down(int u){
        int t = u;
        if(2 * u <= n && nums[2 * u] < nums[t]) t = 2 * u;
        if(2 * u + 1 <= n && nums[2 * u + 1] < nums[t]) t = 2 * u + 1;
        if(t != u){
            int tmp = nums[t];
            nums[t] = nums[u];
            nums[u] = tmp;
            down(t);
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        nums = new int[n + 1];
        for(int i = 1; i <= n; i ++) nums[i] = sc.nextInt();
        for(int i = n / 2; i >= 1; i --) down(i);
        int len = n;
        for(int i = 1; i <= len; i ++){
            System.out.println(nums[1]);
            nums[1] = nums[n];
            n --;
            down(1);
        }

    }
}