维基百科-快速排序
维基百科-归并排序
cnblog-排序算法

希尔排序

算法描述

希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。

  • 希尔排序是基于插入排序的以下两点性质而提出改进方法的：
  • 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率
  • 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位

步长的选择是希尔排序的重要部分。只要最终步长为1任何步长序列都可以工作。算法最开始以一定的步长进行排序。然后会继续以一定步长进行排序，最终算法以步长为1进行排序。当步长为1时，算法变为普通插入排序，这就保证了数据一定会被排序。

  • 取初始的步长为step(初始值为数组长度arr的一半)
  • 以步长为单位 让arr[step] arr[step 2] … arr[step n]进行插入排序
  • 步长进行除二直至步长单位为1时进行全数列的插入排序

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public void shellSort(int[] arr){
	int step = maxSize / 2;
	while (step >= 1) {
	    for (int i = step; i < arr.length; i += step) {
	        int currentItem = arr[i];
	        int preIndex = i - step;
	        while (preIndex >= 0 && arr[preIndex] > currentItem) {
	            arr[preIndex + step] = arr[preIndex];
	            preIndex -= step;
	        }
	        if (preIndex + step != i) {
	            arr[preIndex + step] = currentItem;
	        }
	    }
	    step /= 2;
	}
}

归并排序

算法描述

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。

递归方案

  • 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
  • 设定两个指针，最初位置分别为两个已经排序序列的起始位置
  • 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
  • 重复步骤3直到某一指针到达序列尾
  • 将另一序列剩下的所有元素直接复制到合并序列尾

代码实现

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
public static void mergeSort(int[] arr) {
    int[] result = new int[arr.length];

    mergeSortRecursive(arr, result, 0, arr.length - 1);
}

public static void mergeSortRecursive(int[] arr, int[] result, int start, int end) {
    if (start >= end) {
        return;
    }

    int length = end - start;
    int mid = start + (length >> 2);

    int start1 = start;
    int start2 = mid + 1;
    int end1 = mid;
    int end2 = end;

    mergeSortRecursive(arr, result, start1, end1);
    mergeSortRecursive(arr, result, start2, end2);

    int k = start;

    while (start1 <= end1 && start2 <= end2) {
        result[k++] = arr[start1] > arr[start2] ? arr[start2++] : arr[start1++];
    }
    while (start1 <= end1) {
        result[k++] = arr[start1++];
    }
    while (start2 <= end2) {
        result[k++] = arr[start2++];
    }

    for (int i = start; i <= end; i++) {
        arr[i] = result[i];
    }
}

动图演示