基本排序

2016-06-04 | 分类 algorithm | 标签 ElementarySort

1 选择排序

选择排序是一种非常基本的排序，思想很质朴，对于长度为N的数组，遍历N次，每次选择一个剩余元素中最小的一个排好位置。

1
2
3
4
5
6
7
8
9
10
11
12 public void SelectionSort2(int[] a){
  if(a == null || a.length <= 1) return;
  int hi = a.length-1;
  for (int i = 0; i <= hi; i++) {
    int min = i;
    for (int j = i+1; j <= hi; j++) {
        if(a[j] < a[min]) min = j;
    }
    swap(a,min,i);
  }
}

2 插入排序

插入排序的思想也很简单，使用i为遍历指针，每次将a[i]放到已经有序的数组中的合适位置，成为一个比之前有序数组大1的有序数组。

1
2
3
4
5
6
7    public void InsertionSort2(int[] a,int lo,int hi){
    for (int i = lo; i <= hi; i++) {
      for(int j = i; j > lo && less(a,j,j-1);j--)
        swap(a,j,j-1);
    }
}

3 希尔排序

希尔排序的思想是任意间隔为h的数组都是有序的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 public void ShellSort2(int[] a){
    int h = 1;
    int n = a.length;
    int hi = n - 1;
    while(h < n/3) h = 3 * h + 1;
    while(h >= 1){
      for(int i = h;i <= hi; i++){
        for(int j = i; j >= h  && less(a,j,j-h);j -= h){
          swap(a,j,j-h);
        }
      }
      h = h / 3;
    }
}