参考文章：https://juejin.im/post/5ab9ae9cf265da23830ae617

排序是算法排在前面的知识内容，已经很久没有回顾了。今天心情凌乱，就把八大排序算法做个小总结吧，算作是一次小小的复习与回顾。

1. 冒泡排序

思路：

  • 两两交换，将大的元素交换到后面（从小到大排序的情况下），没经过一轮，就能确定最后一个元素是最大值。
1
2
3
4
5
6
7
8
9
10
11
12
for (int i = 0; i < arrays.length - 1; i++) { // 外层循环控制排序的趟数
    isChange = 0; // 每比较完一趟就置0
    for (int j = 0; j < arrays.length - i - 1; j++) { // 内层循环控制比较交换的次数
        if (arrays[j] > arrays[j+1]) {
            swap(arrays[j], arrays[j+1]);
        }
        isChange = 1;
    }
    if (isChange == 0) { // 如果当前趟次没有发生交换，则说明排序已经完成
        break;
    }
}

复杂度分析：

  • 时间：O(n^2)
  • 空间：O(1)
  • 稳定

2. 选择排序

思路：

  • 找到数组中的最大值，与数组的最后一个元素交换（从小到大排序的情况下）。
1
2
3
4
5
6
7
8
9
for (int i = 0; i < arrays.length - 1; i++) { // 外层控制排序趟数
    pos = 0; // 新的趟数时，将下标归零
    for (int j = 0; j < arrays.length - i; j++) { // 内层控制选择最大值循环
        if (arrays[j] > arrays[pos]) {
            pos = j;
        }
    }
    swap(arrays[pos], arrays[arrays.length - i - 1]); // 将本趟寻找到的最大值与本趟末尾元素置换
}

复杂度分析：

  • 时间：O(n^2)
  • 空间：O(1)
  • 不稳定

3. 插入排序

思路：

  • 将一个元素插入到已经有序的数组中，初始时将第一个元素当做有序数组。
  • 与有序数组末尾元素进行比较，若大于则直接放入有序数组末尾（即当前位置不动），若小于则插入到合适位置，并进行移动。
1
2
3
4
5
6
7
8
9
10
int temp; // 临时变量
for (int i = 1; i < arrays.length; i++) { // 外层控制排序趟数
    temp = arrays[i];
    int j = i - 1;
    while (j >= 0 && arrays[j] > temp) { // 内层寻找插入位置
        arrays[j+1] = arrays[j]; // 向前交换，找到合适的插入位置
        j--;
    }
    arrays[j+1] = temp; // 将temp元素插入找到的有序数组中的位置
}

算法复杂度：

  • 时间：O(n^2)
  • 空间：O(1)
  • 稳定

4. 快速排序

思路：

  • 在数组中找一个元素，比它小的放在它左边，比它大的放在它右边，一趟下来，比当前元素小的都在左边，大的都在右边。
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
public static void quickSort(int[] arrays, int left, int right) {
    int j = left;
    int i = right;

    int pivot = arrays[(left + right) / 2];

    while (i <= j) {
        while (pivot > arrays[i]) {
            i++;
        }
        while (pivot < arrays[j]) {
            j--;
        }
        if (i <= j) {
            swap(arrays[i], arrays[j]);
            i++;
            j--;
        }
    }

    if (left < j) {
        quickSort(arrays, left, j);
    }
    if (right > i) {
        quickSort(arrays, i, right);
    }
}

算法复杂度：

  • 时间：O(nlogn)
  • 空间：O(nlogn)
  • 不稳定

5. 归并排序

思路：

  • 将两个已经排序好的数组合并成一个有序数组。
    • 将元素分隔开，看成有序数组，进行比较合并；
    • 不断拆分与合并，直到拆分成一个元素为止。
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
public static void mergeSort(int[] arrays, int left, int right) {
    if (left == right) { // 只剩余一个元素的时候，就不需要排序了
        return;
    } else {
        int mid = (left + right) >> 1;
        mergeSort(arrays, left, mid);
        mergeSort(arrays, mid+1, right);
        merge(arrays, left, mid+1, right);
    }
}

static void merge(int[] arrays[], int left, int mid, int right) {
    int[] leftArr = new int[mid - left];
    int[] rightArr = new int[right - mid + 1];

    for (int i = left; i < mid; i++) {
        leftArr[i - left] = arrays[i];
    }
    for (int i = mid; i <= right; i++) {
        rightArr[i - mid] = arrays[i];
    }

    int i = 0, j = 0;
    int k = left; // 指向数组最左端元素

    while (i < leftArr.length && j < rightArr.length) {
        if (leftArr[i] < rightArr[j]) {
            arrays[k] = leftArr[i];
            i++;
            k++;
        } else {
            arrays[k] = rightArr[j];
            j++;
            k++;
        }
    }

    while (i < leftArr.length) {
        arrays[k] = leftArr[i];
        i++;
        k++;
    }
    while (j < rightArr.length) {
        arrays[k] = rightArr[j];
        j++;
        k++;
    }
}

算法复杂度：

  • 时间：O(nlogn)
  • 空间：O(n)
  • 稳定

6. 堆排序

思路：

  • 利用二叉树性质，要求父节点比左右孩子节点都大（大顶堆）。
  • 由于二叉树由数组存储，故对于某个节点i，其左节点下标为2i，右节点下标为2i+1。若存在数组0下标作为哨兵交换节点的情况，则对于节点i，其左节点为2i+1，右节点为2i+2。
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
public static void buildHeap(int[] arrays, int size) {
    for (int i = size-1; i >= 0; i--) {
        heapify(arrays, i, size);
    }
}

static void heapify(int[] arrays, int currentRootNode, int size) {
    if (currentRootNode < size) {
        // arrays[0]作为哨兵，不存值，用于作为交换buffer
        int left = 2 * currentRootNode + 1;
        int right = 2 * currentRootNode + 2;

        int max = currentRootNode;

        if (left < size) {
            if (arrays[max] < arrays[left]) {
                max = left;
            }
        }
        if (right < size) {
            if (arrays[max] < arrays[right]) {
                max = right;
            }
        }

        if (max != currentRootNode) {
            swap(arrays[currentNodeRoot], arrays[max]);
            heapify(arrays, max, size);
        }
    }
}

算法复杂度：

  • 时间：O(nlogn)
  • 空间：O(1)
  • 不稳定

7. 希尔排序

思路：

  • 本质上是插入排序的增强版，希尔排序将数组分隔为n组来进行插入排序，直至总体有序。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
void shellSot(int[] arrays) {
    for (int step = arrays.length / 2; step > 0; step /= 2) {
        for (int i = step; i < arrays.length; i++) {
            int j = i;
            int temp = arrays[j];

            while (j-step >= 0 && arrays[j-step] > temp) {
                arrays[j] = arrays[j-step];
                j -= step;
            }
            arrays[j] = temp;
        }
    }
}

算法复杂度：

  • 时间：O(n^(1.5))
  • 空间：O(1)
  • 不稳定

8. 基数排序（桶排序）

思路：

  • 将数字切割成个、十、百、千位放入到不同的桶子里，放一次就按桶子顺序回收一次，直至最大位数的数字放完。
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
void radixSort(int[] arrays) {
    int max = findMax(arrays, 0, arrays.length-1);

    // 遍历次数由最大值的位数决定
    for (int i = 1; max/i >= 0; i *= 10) {
        int[][] buckets = new int[arrays.length][10];

        // 获取每一位数字放入桶中
        for (int j = 0; j < arrays.length; j++) {
            int num = (arrays[j] / i) % 10;
            buckets[j][num] = arrays[j];
        }

        int k = 0;

        for (int j = 0; j < 10; j++) {
            // 对每个桶中的元素进行回收
            for (int l = 0; l < arrays.length; l++) {
                // 若桶中有数据则回收
                if (buckets[l][j] != 0) {
                    arrays[k++] = buckets[l][j];
                }
            }
        }
    }
}

void findMax(int[] arrays, int left, int right) {
    if (left == right) {
        return arrays[left];
    } else {
        int a = arrays[left];
        int b = findMax(arrays, left+1, right); // 找出整体的最大值

        if (a > b) {
            return a;
        } else {
            return b;
        }
    }
}

算法复杂度：

  • 时间：O(d * (r + n)) 其中，d表示长度，r代表关键字的基数，n代表关键字的个数
  • 空间：O(d * r + n)
  • 稳定