常见排序算法要点

常见排序算法要点

一、回顾常见的排序算法

回顾常见的排序算法，通过编码发现容易出错的地方，特意在此记录下来，便于下次回顾的时候，出现错误能够快速定位。

常见的排序算法有四类：

• 选择排序：选择排序O(n^2)、堆排序O(nlogn)
• 交换排序：冒泡排序O(n^2)、快速排序O(nlogn) 、三路快排O(nlogn)
• 插入排序：插入排序O(n^2)、希尔排序(n^1.3)
• 归并排序：从上到下归并排序O(nlogn)、从下到上归并O(nlogn)

下面依次说明算法中的容错点。

二、选择排序

2.1 普通选择排序

每次选择较大值，还是选择较小值，写法上略微有些不同。

2.2 对排序

表面是对角标范围[1,n-1]进行对排序，实际上exch(T[] a, int i, int j) 和less(T[] a, int i, int j)都要错一位进行计算。

    public boolean less(T[] a, int i, int j) {
        return a[i-1].compareTo(a[j-1])<0;
    }

    public void exch(T[] a, int i, int j) {
        T t = a[i-1];
        a[i-1] = a[j-1];
        a[j-1] = t;
    }
1
2
3
4
5
6
7
8
9

三、交换排序

3.1 冒泡排序

注意两层遍历的角标。

for (int i=0; i<a.length-1; i++) {
  for (int j=1; j<a.length-i; j++) {
    //......
  }
}
1
2
3
4
5

3.2 快速排序

采用递归写法

3.3 三路快排

采用递推。

四、插入排序

4.1 普通插入排序

第二层的遍历需要注意：

for (int i=1; i<a.length; i++) {
  T t = a[i];
  int j = i;
  for (; j>=1 && less(t, a[j-1]); j--) {
    //...
  }
}
1
2
3
4
5
6
7

4.2 希尔排序

基于插入排序，注意，第二层循环的判断。

五、归并排序

5.1 从上到下归并

递推

5.2 从下到上归并

递归。