冒泡、快排、选择三种常用排序的实现以及时间复杂度

时间复杂度：

Java实现：

1、快速排序

public class 快速排序 {
    public static void main(String[] args) {
        int[] a = {5,7,1,3,4,9,8};
        quickSort(a, 0, a.length - 1);
        for (int i : a) {
            System.out.println(i);
        }
    }

    public static void quickSort(int a[], int l, int h){ //low high
        if (l < h){
            int i = l, j = h, tmp = a[l]; //tmp 保存第一个基准数
            while (i < j){
                while (i < j && a[j] >= tmp) // 从右向左找第一个小于tmp的数
                    j--;
                if (i < j) //扫描到了 a[j] < tmp
                    a[i++] = a[j];

                while (i < j && a[i] <= tmp) // 从左向右找第一个大于tmp的数
                    i++;
                if (i < j) //扫描到了 a[i] > tmp
                    a[j--] = a[i];
            }
            // 一轮交换过后，将基准数放到中间位置
    
            a[i] = tmp;
            //递归对左、右两边调用快排
            quickSort(a, l, i - 1);
            quickSort(a, i + 1, h);
        }
    }
}
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

2、冒泡排序

//冒泡排序
public void bubbleSort(int[] a) {
    int t;
    for (int i = 0; i < a.length -1; i++)    //循环数组长度-1次
        for (int j = 0; j < a.length - i - 1; j++) {   //每次少比较一次
            if (a[j] > a[j + 1]) {
                t = a[j];
                a[j] = a[j + 1];
                a[j + 1] = t;
            }
        }
}
1
2
3
4
5
6
7
8
9
10
11
12

3、选择排序

//选择排序
public void selectSort(int[] a) {
    int t;
    //把第一位和其他所有的进行比较，只要比第一位小的，就换到第一个位置来
    for (int i = 0; i < a.length - 1; i++)     
        //比较完后，第一位就是最小的
        for (int j = i + 1; j < a.length; j++) {         
            if (a[i] > a[j]) {
                t = a[i];
                a[i] = a[j];
                a[j] = t;
            }
        }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14