冒泡排序

时间复杂度： O(n ^ 2)

稳定性：稳定

每次把两个相邻数进行比较，大的那个换到后面

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public void bubbleSort(int[] arr) {
    int length = arr.length;
    for (int i = 0; i < length - 1; i++) {
        for (int j = 0; j < length - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(arr, j, j + 1);
            }
        }
    }
}

// 元素交换
private void swap(int[] arr, int i, int j) {
    int temp = arr[j];        
    arr[j] = arr[i];
    arr[i] = temp;
}

选择排序

时间复杂度： O(n ^ 2)

稳定性：稳定

每次遍历数组选出一个最小（大）的放到数组前面

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 选择排序
public void SelectionSort(int[] arr) {
    int length = arr.length;
    for (int i = 0; i < length - 1; i++) {
        int minIndex = i;
        // 找到最小的值的下标
        for (int j = i + 1; j < length; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        // 每次循环更新剩余数组的第一位
        swap(arr, minIndex, i);
    }
}

插入排序

时间复杂度： O(n ^ 2)

稳定性：稳定

每次从当前位置往前比较，找到合适的插入位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 插入排序
public void InsertSort(int[] arr) {
    int length = arr.length;
    for (int i = 1; i < length; i++) {
        int temp = arr[i];
        int j = i;
        // 从当前位置往前找到要插入的位置
        while (j > 0 && temp < arr[j - 1]) {
            // 把前面的数往后移动一位
            arr[j] = arr[j - 1];
            j--;
        }
        // 插入
        arr[j] = temp;
    }
}

快速排序

时间复杂度： O(n * logn)

稳定性：不稳定

自上而下，递归子问题，根据pivot把数据分成三个区间

  1. 小于 pivot
  2. pivot
  3. 大于 pivot
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 void quickSort(int[] arr) {
    quickSort(arr, 0, arr.length - 1);
}

public void quickSort(int[] arr, int left, int right) {
    if (left > right) return;
    // partitionIndex是数组下标
    int partitionIndex = partition(arr, left, right);
    quickSort(arr, left, partitionIndex - 1);
    quickSort(arr, partitionIndex + 1, right);
}

private int partition(int[] arr, int left, int right) {
    // pivot 是 基准值，此时左区间长度为1
    int pivot = left;
    // index 是 左区间的右边界（包含） + 1
    int index = pivot + 1;
    for (int i = index; i <= right; i++) {
        if(arr[i] < arr[pivot]){
            swap(arr, i, index);
            index++;
        }
    }
    // 基准值交换到左区间的右边界，那么左区间的右边界就是index-2
    swap(arr, pivot, index - 1);
    // [0 index-2] index-1 [index length-1] 
    // 返回基准值
    return index - 1;
}

归并排序

时间复杂度： O(n * logn)

稳定性：稳定

自上而下的递归子问题，用小问题解决大问题

自下而上的适合链表，先归并短的链表，再归并长的链表

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
 // 归并排序
private int[] MergeSort(int[] arr) {
    return MergeSort(arr, 0, arr.length - 1);
}

private int[] MergeSort(int[] arr, int left, int right) {
    if(left > right) return null;
    if(left == right) return new int[]{arr[left]};
    int mid = (left + right) / 2;
    return merge(MergeSort(arr, left, mid), MergeSort(arr, mid + 1, right));
}

// 合并有序数组
private int[] merge(int[] arr1, int[] arr2) {
    int[] result = new int[arr1.length + arr2.length];
    int index = 0;
    int p1 = 0, p2 = 0;
    while (p1 < arr1.length && p2 < arr2.length) {
        int num;
        if (arr1[p1] < arr2[p2]) {
            num = arr1[p1++];
        } else {
            num = arr2[p2++];
        }
        result[index++] = num;
    }
    while (p1 < arr1.length) {
        result[index++] = arr1[p1++];
    }
    while (p2 < arr2.length) {
        result[index++] = arr2[p2++];
    }
    return result;
}