排序算法笔记1

发表于 |

一些碎碎念
切实感到了自己体质的差劲, 家里人病倒了过去照顾了几天, 自己也被传染了, 一个月感冒发烧两次真的是破了自己这辈子的记录了.

  1. 选择排序 Selection Sort

思路: 从所有字符里找出最小的, 放到第一个位置, 继续对剩下的字符找出最小的, 放到第二个位置, 以此类推.

数据移动: N次(最少), 运行时间和输入(eg.部分有序或部分相同)无关
比较: N2/2次, 复杂度n2

实现思路: 为了方便实现, 程序实现往往和算法本身的思路会有一些区别.
在比较寻找最小的过程中, 用一个变量min来记录最小值的index, 随着每次比较(j和min)不断刷新min的index即可.

1
2
3
4
5
6
7
8
9
10
11
12
public class SelectionSort {
    public static void sort(int[] a){
        for(int i = 0; i<a.length; i++){
            int min = i;//<--!!!不是0!!!-L-
            for(int j=i+1; j<a.length; j++){
                if(a[min]>a[j])   min = j;
            }
            //swap三板斧 a[i]<->a[min]
            int temp = a[i]; a[i]=a[min]; a[min]=temp;
        }
    }
}
  1. 插入排序 Insertion Sort
    一张一张插到合适的位置, 和整理牌类似

思路: 当前索引左边都是有序的, 但位置还不确定因为可能会插入新数字, 当索引到达最右端, 排序完成.

运行时间和输入有关, 接近整理好的数组的排序时间会远小于杂乱的数组.
交换: ~N2/4次(平均), ~N2/2次(最差-完全倒序), 0次(最优)
比较: ~N2/4次(平均), ~N2/2次(最差-完全倒序), N-1次(最优)

复杂度n2

实现思路: 虽然左侧序列是不确定的, 但在每次循环都只是多加了1个或者不加而已, 还是基本确定的(加一个也只是一次往前交换而已), 所以索引只要从0开始+1+1就可以了. 

1
2
3
4
5
6
7
8
public static void insertionSort(int[] a){
        for (int i = 0; i<a.length; i++){
            for(int j=i; j>0 && a[j-1]>a[j]; j--){
                //swap
                int temp = a[j]; a[j]=a[j-1]; a[j-1]=temp;
            }
        }
    }

插入排序对于部分有序/小规模的数组非常高效.

  1. 希尔排序 Shell Sort

希尔排序的思想是使数组中任意间隔为h的元素都是有序的.