插入排序（稳）n^2,1

将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数增 1 的有序表。

使用双层循环

  • 外层循环对除了第一个元素之外的所有元素
  • 内层循环将当前元素和前面的元素比较，不满足排序要求则交换这两个元素位置。

时间复杂度 O(n^2) 空间复杂度O(1)

伪代码：

1
2
3
4
5
6
7
8
9
10
for (int i=1; i<length; ++i) {
    for ( j = i-1; j >= 0; --j){
        if(array[j]和array[j+1]不满足排序顺序){
            swap(array,j,j+1);
        }
        else{
            break;
        }
    }
}

过程图示：

insert1

insert2

insert3

insert4

冒泡排序（稳）n^2,1

每轮冒泡，相邻两数，前面的数字大于后面的数字就交换，这样一轮过后，最大的数放在了最后

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

空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
public static void bubbleSort1(int [] a, int n){
    int i, j;

    for(i=0; i<n; i++){//n轮冒泡
        for(j=1; j<n-i; j++){
            if(a[j-1] > a[j]){
                int temp = a[j-1];
                a[j-1] = a[j];
                a[j]=temp;
            }
        }
    }
}

归并排序（稳）nlogn,n

往下做二分递归，往上合并两个排好序的数组递归回去。

时间复杂度：O(nlogn)，往上的时候深度是logn，合并两个排好序的数组最多需要n次，相乘。

空间复杂度：O(n)，需要存储两个排好序的数组

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
public static void mergeSort(int[] a, int low, int high) {
    int mid = (low + high) / 2;
    if (low < high) {
        mergeSort(a, low, mid);
        mergeSort(a, mid + 1, high);
        merge(a, low, mid, high);
    }
}

public static void merge(int[] a, int low, int mid, int high) {
    int[] temp = new int[high - low + 1];
    int i = low;// 左指针
    int j = mid + 1;// 右指针
    int k = 0;
    // 把较小的数先移到新数组中
    while (i <= mid && j <= high) {
        if (a[i] < a[j]) {
            temp[k++] = a[i++];
        } else {
            temp[k++] = a[j++];
        }
    }
    // 把左边剩余的数移入数组
    while (i <= mid) {
        temp[k++] = a[i++];
    }
    // 把右边边剩余的数移入数组
    while (j <= high) {
        temp[k++] = a[j++];
    }
    // 把新数组中的数覆盖nums数组
    for (int k2 = 0; k2 < temp.length; k2++) {
        a[k2 + low] = temp[k2];
    }
}

快速排序 nlogn,logn

分治思想，取出一个数，小于它的放左边，大于的放右边，在分别对左右子序列操作，直到区间只有1个数。

时间复杂度：最优 O(nlogn) ，最差 O(n^2)

最优就是每次划分都是正好一半，遍历是n,每次少一半相当于二分是logn,相乘就是nlogn

最差就是正序或者倒序，每次划分都只是减少1个项，遍历是n，总共n次，相乘就是n^2

空间复杂度：最优 O(logn) ，最差 O(n)

空间复杂度就是递归树深度，最优logn次递归，最差n次递归

整个划分函数partition主要涉及两个指针i和j，一开始 i = l-1 , j = l。我们需要实时维护两个指针使得任意时候，对于任意数组下标k，我们有如下条件成立:

  1. l ≤ k ≤ i时,nums[k] ≤ pivot。
  2. i＋1 ≤ k ≤ j-1时，nums[k] > pivot。

我们每次移动指针j，如果nums[j] > pivot，我们只需要继续移动指针j，即能使上述三个条件成立，否则我们需要将指针i加一，然后交换nums[i]和nums[j]，再移动指针j才能使得三个条件成立。

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
class Solution {
    public int[] sort(int[] nums) {
        quicksort(nums, 0, nums.length - 1);
        return nums;
    }

    public void quicksort(int[] nums, int l, int r) {
        if (l < r) {
            int pos = partition(nums, l, r);
            quicksort(nums, l, pos - 1);
            quicksort(nums, pos + 1, r);
        }
    }

    public int partition(int[] nums, int l, int r) {
        int pivot = nums[r];
        int i = l - 1;
        for (int j = l; j <= r; ++j) {
            if (nums[j] <= pivot) {
                i = i + 1;
                swap(nums, i, j);
            }
        }
        return i;
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

主元是最后一个，两个指针，i从l-1开始，j从l开始，先移动j，不满足条件就交换++i和j

堆排序 nlogn,1

每一次下沉（siftDown）都能把最大的值放到堆顶，然后再把堆顶和数组尾交换，就能把最大的放到数组后面。

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

    public int[] sortArray(int[] nums) {
        int len = nums.length;
        heapify(nums);//建堆
        for (int i = len - 1; i >= 1; ) {
            swap(nums, 0, i);
            i--;
            siftDown(nums, 0, i);
        }
        return nums;
    }
    
    private void heapify(int[] nums) {
        int len = nums.length;
        for (int i = (len - 1) / 2; i >= 0; i--) {
            siftDown(nums, i, len - 1);
        }
    }

    private void siftDown(int[] nums, int k, int end) {
        while (2 * k + 1 <= end) {
            int j = 2 * k + 1;
            if (j + 1 <= end && nums[j + 1] > nums[j]) {
                j++;
            }
            if (nums[j] > nums[k]) {
                swap(nums, j, k);
            } else {
                break;
            }
            k = j;
        }
    }

    private void swap(int[] nums, int index1, int index2) {
        int temp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = temp;
    }
}