排序算法之归并和希尔排序！

归并排序

归并排序核心是分治思想:

先把数组从中间分成前后两部分，然后对前后两部分分别排序，再将排好序的两部分合并在一起，这样整个数组就都有序了。

若将两个有序表合并成一个有序表，称为二路归并。

归并排序是稳定的排序算法。

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
public class MergeSort {
  public static void main(String[] args) {
    int data[] = { 9, 5, 6, 8, 0, 3, 7, 1 };
    megerSort(data, 0, data.length - 1);
    System.out.println(Arrays.toString(data));
  }
 
  public static void mergeSort(int data[], int left, int right) { // 数组的两端
    if (left < right) { // 相等了就表示只有一个数了 不用再拆了
      int mid = (left + right) / 2;
      mergeSort(data, left, mid);
      mergeSort(data, mid + 1, right);
      // 分完了 接下来就要进行合并，也就是我们递归里面归的过程
      merge(data, left, mid, right);
    }
  }
 
  public static void merge(int data[], int left, int mid, int right) {
    int temp[] = new int[data.length];    //借助一个临时数组用来保存合并的数据
    
    int point1 = left;    //表示的是左边的第一个数的位置
    int point2 = mid + 1; //表示的是右边的第一个数的位置
    
    int loc = left;   //表示的是我们当前已经到了哪个位置了
    while(point1 <= mid && point2 <= right){
      if(data[point1] < data[point2]){
        temp[loc] = data[point1];
        point1 ++ ;
        loc ++ ;
      }else{
        temp[loc] = data[point2];
        point2 ++;
        loc ++ ;
      }
    }
    
    while(point1 <= mid){
      temp[loc ++] = data[point1 ++];
    }
    while(point2 <= right){
      temp[loc ++] = data[point2 ++];
    }
    for(int i = left ; i <= right ; i++){
      data[i] = temp[i];
    }
  }
}

希尔排序

基本思想：

将要排序的一组数按某个增量d（n/2，n为要排序数的个数）分成若干组。

每组中记录的下标相差d，对每组中全部元素进行直接插入排序。

然后再用一个较小的增量（d/2）对它进行分组，在每组中再进行直接插入排序。

当增量减到1时，进行直接插入排序后，排序完成。

希尔排序法(缩小增量法) 属于插入类排序，是将整个无序列分割成若干小的子序列分别进行插入排序的方法。

假如：数组的长度为10，数组元素为：25、19、6、58、34、10、7、98、160、0。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static int[] ShellSort(int[] array) {
  int len = array.length;
  int temp, gap = len / 2;
  while (gap > 0) {
    for (int i = gap; i < len; i++) {
      temp = array[i];
      int preIndex = i - gap;
      while (preIndex >= 0 && array[preIndex] > temp) {
        array[preIndex + gap] = array[preIndex];
        preIndex -= gap;
      }
      array[preIndex + gap] = temp;
    }
    gap /= 2;
  }
  return array;
}