4. 希尔排序
希尔排序其实是插入排序的一种优化，其思路是将排序的数组按照一定的增量将数据分组，每个分组用插入排序进行排序，然后增量逐步减小，当增量减小为1的时候，算法便终止，所以希尔排序又叫做“缩小增量排序”。
示意图如下：
图中的示例，每次依次将数组分为若干组，每组分别进行插入排序。代码实现如下：
public class ShellSort { public static void shellSort(int[] data) { int length = data.length; int step = length / 2; while (step >= 1){ for (int i = step; i < length; i++) { int val = data[i]; int j = i - step; for (; j >= 0; j -= step){ if (data[j] > val){ data[j + step] = data[j]; } else { break; } } data[j + step] = val; } step = step / 2; } } }
5. 归并排序
归并排序使用到了分治思想，分治思想即将大的问题分解成小的问题，小的问题解决了，大的问题也就解决了。蕴含分治思想的问题，一般可以使用递归技巧来实现。
归并排序的思路是：首先将数组分解，局部进行排序，然后将排序的结果进行合并，这样整个数组就有序了，你可以结合下图理解：
代码实现：
public class MergeSort { public static void mergeSort(int[] data){ mergeInternally(data, 0, data.length - 1); } private static void mergeInternally(int[] data, int p, int r){ if (p >= r){ return; } int q = (p + r) / 2; //分治递归 mergeInternally(data, p, q); mergeInternally(data, q + 1, r); //结果合并 merge(data, p, q, r); } private static void merge(int[] data, int p, int q, int r){ int[] temp = new int[r - p + 1]; int k = 0; int i = p; int j = q + 1; //比较并合并 while (i <= q && j <= r){ if (data[i] < data[j]){ temp[k ++] = data[i ++]; } else { temp[k ++] = data[j ++]; } } //合并可能出现的剩余元素 int start = i; int end = q; if (j <= r){ start = j; end = r; } while (start <= end){ temp[k ++] = data[start ++]; } //拷贝回原数组 if (r - p + 1 >= 0) { System.arraycopy(temp, 0, data, p, r - p + 1); } } }
6. 快速排序
快速排序也用到了分治的思想，只不过它和归并排序的思路刚好是相反的，快速排序使用数组中一个数据作为分区点（一般可以选取数组第一个或最后一个元素），比分区点小的，放在左侧，比分区点大的，放在右侧。然后左右两侧的数据再次选择分区点，循环进行这个操作，直到排序完成。
示意图如下（图中是以第一个元素作为分区点）：
代码实现：
public class QuickSort { public static void quickSort(int[] data){ quickSortInternally(data, 0, data.length - 1); } private static void quickSortInternally(int[] data, int p, int r){ if (p >= r){ return; } int q = partition(data, p, r); quickSortInternally(data, p, q - 1); quickSortInternally(data, q + 1, r); } /** * 获取分区点函数 */ private static int partition(int [] data, int p, int q){ int pivot = data[q]; int i = 0; int j = 0; while (j < q){ if (data[j] <= pivot){ swap(data, i, j); i ++; } j ++; } swap(data, i, q); return i; } /** * 交换数组两个元素 */ private static void swap(int[] data, int i, int j){ int temp = data[i]; data[i] = data[j]; data[j] = temp; } }
7. 堆排序
基于堆的排序比较常用，时间复杂度为 O(nlogn)，并且是原地排序，主要的步骤分为建堆和排序。
建堆
思路是从堆中第一个非叶子节点，依次从上往下进行堆化，如下图：
排序
建堆完成之后，假设堆中元素个数为 n，堆顶元素即是最大的元素，这时候直接将堆顶元素和堆中最后一个元素进行交换，然后将剩余的 n - 1 个元素构建成新的堆，依次类推，直到堆中元素减少至 1，则排序完成。示意图如下：
代码实现：
public class HeapSort { /** * 排序 */ public void heapSort(int[] data){ int length = data.length; if (length <= 1){ return; } buildHeap(data); while (length > 0){ swap(data, 0, -- length); heapify(data, length, 0); } } /** * 建堆 */ private void buildHeap(int[] data){ int length = data.length; for (int i = (length - 2) / 2; i >= 0; i --) { heapify(data, length, i); } } /** * 堆化函数 */ private void heapify(int[] data, int size, int i){ while (true){ int max = i; if ((2 * i + 1) < size && data[i] < data[2 * i + 1]) { max = 2 * i + 1; } if ((2 * i + 2) < size && data[max] < data[2 * i + 2]) { max = 2 * i + 2; } if (max == i){ break; } swap(data, i, max); i = max; } } /** * 交换数组中两个元素 */ private void swap(int[] data, int i, int j){ int temp = data[i]; data[i] = data[j]; data[j] = temp; } }
