# 1、快排&冒泡排&选择排&擂台

# AcWing 785. 快速排序

package javatest;

import java.util.Scanner;

public class ACWing {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int len = sc.nextInt();
        int[] shuzu = new int[len];
        for (int i = 0; i < len; i++) {
            shuzu[i] = sc.nextInt();
        }

//        quickSort(shuzu, len, 0, len - 1);
//        maopaoSort(shuzu, len);
//        selectSort(shuzu, len);
        leitaiSort(shuzu, len);
        for (int i = 0; i < shuzu.length; i++) {
            System.out.print(shuzu[i] + " ");
        }
    }

    //快速排序
    static int[] quickSort(int[] s, int len, int l, int r) {
        if (l >= r)
            return s;
        int flag = s[l];
        int p_i = l, p_j = r;
        while (p_i < p_j) {
            while (p_i < p_j && s[p_j] >= flag) p_j--;
            while (p_i < p_j && s[p_i] <= flag) p_i++;
            int temp = s[p_i];
            s[p_i] = s[p_j];
            s[p_j] = temp;
            if (p_i >= p_j) {
                int temp0 = s[l];
                s[l] = s[p_i];
                s[p_i] = temp0;
            }
        }
        quickSort(s, len, l, p_i - 1);
        quickSort(s, len, p_i + 1, r);
        return s;
    }

    //冒泡排序
    static int[] maopaoSort(int[] s, int len) {
        for (int i = 0; i < len - 1; i++)
            for (int j = 0; j < len - i - 1; j++)
                if (s[j] > s[j + 1]) {
                    int temp = s[j];
                    s[j] = s[j + 1];
                    s[j + 1] = temp;
                }
        return s;
    }

    //选择排序
    static int[] selectSort(int[] s, int len) {
        for (int i = 0; i < len - 1; i++)
            for (int j = i + 1; j < len; j++)
                if (s[j] < s[i]) {
                    int temp = s[j];
                    s[j] = s[i];
                    s[i] = temp;
                }
        return s;
    }

    //选择-擂台排序
    static int[] leitaiSort(int[] s, int len) {
        for (int i = 0; i < len - 1; i++) {
            int k = i;
            for (int j = i + 1; j < len; j++) if (s[j] < s[k]) k = j;
            int temp = s[k];
            s[k] = s[i];
            s[i] = temp;
        }
        return s;
    }
}

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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82