排序方法

冒泡排序、插入排序、选择排序、快速排序、归并排序、计数排序、基数排序、桶排序。

复杂度归类

冒泡排序、插入排序、选择排序 O(n^2)

快速排序、归并排序 O(nlogn)

计数排序、基数排序、桶排序 O(n)

算法的执行效率

  • 最好、最坏、平均情况时间复杂度
  • 时间复杂度的系数、常数和低阶
  • 比较次数，交换（或移动）次数

排序算法的稳定性

稳定性概念

如果待排序的序列中存在值相等的元素，经过排序之后，相等元素之间原有的先后顺序不变。

稳定性重要性

可针对对象的多种属性进行有优先级的排序。

排序算法的内存损耗

原地排序算法：特指空间复杂度是O(1)的排序算法。

冒泡排序

冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较，看是否满足大小关系要求，如果不满足就让它俩互换。

稳定性

冒泡排序是稳定的排序算法。

空间复杂度

冒泡排序是原地排序算法。

时间复杂度

最好情况：O(n)。

最坏情况：O(n^2)。

平均情况：平均时间复杂度为O(n^2)。

1
2
3
4
5
6
7
8
9
10
11
12
13
public void sort(T[] num) {
    int N = num.length;
        boolean isSorted = false;
        for (int i = N - 1; i > 0 && !isSorted; i--) {
            isSorted=true;
            for (int j = 0; j <i ; j++) {
                if (less(num[j+1],num[j])){
                    isSorted=false;
                    swap(num,j,j+1);
                }
            }
    }
}

插入排序

插入排序将数组数据分成已排序区间和未排序区间。初始已排序区间只有一个元素，即数组第一个元素。

在未排序区间取出一个元素插入到已排序区间的合适位置，直到未排序区间为空。

稳定性

插入排序是稳定的排序算法。

空间复杂度

插入排序是原地排序算法。

时间复杂度

\1. 最好情况：O(n)。

\2. 最坏情况：O(n^2)。

\3. 平均情况：O(n^2)。

1
2
3
4
5
6
7
8
public void sort(T[] num) {
    int N = num.length;
    for (int i = 1; i < N; i++) {
        for (int j = i; j > 0 && less(num[j], num[j - 1]); j--) {
            swap(num, j, j - 1);
        }
    }
}

选择排序

选择排序将数组分成已排序区间和未排序区间。初始已排序区间为空。

每次从未排序区间中选出最小的元素插入已排序区间的末尾，直到未排序区间为空。

稳定性

选择排序不是稳定的排序算法。

空间复杂度

选择排序是原地排序算法。

时间复杂度

都是O(n^2)）

1
2
3
4
5
6
7
8
9
10
11
public void sort(T[] a) {
    for (int i = 0; i < a.length; i++) {
        int min = i;
        for (int j = i + 1; j < a.length; j++) {
            if (less(a[j], a[min])) {
                min = j;
            }
        }
        swap(a, i, min);
    }
}

思考

冒泡排序和插入排序的时间复杂度相同都是O(n^2)，为什么插入排序比冒泡排序更受欢迎？

参考这里

  • 对于部分有序的小区间 N，冒泡排序需要排序 N次，而插入排序效率更高
  • 对于冒泡排序可以改进（参考代码），如果循环完没有做任何交换，说明已经是有序的

如果数据存储在链表中，三种排序方法的时间复杂会变成怎样？

假定只能改变节点位置

冒泡排序，比较次数不变，因为指针，交换数据更加复杂。

插入排序，比较次数不变，但可以直接插入数据，不需要一个个地后移数据。

选择排序，比较次数不变，因为指针，交换数据更加复杂。