算法：插入排序归并排序快速排序堆排序

说明

对排序实现的总结，以下都是基于升序排序[1,2,3…]：

插入排序：
两层循环嵌套，第一层从第二位开始，index逐步递增；
第二层，innerIndex从index-1逐步递减，，在index之前都为有序，如果data[innerIndex] > data[index]，则innerIndex++腾出位置(这是插入排序的特点)，一直到条件失败，退出内存循环，交换innerIndex 跟index。平均时间复杂度为O(n^2)

归并排序: 递归实现，先逐层一分为二，一直到只有一个数字，然后把拆解出来的数字逐层合并回来。复杂度分解为二叉树，合并为倒二叉树，时间复杂度为O(nlogn)

快速排序：快速排序的特点是取一个值为参考值pivot，小于pivot的在左边，大于pivot的在右边，这样左边的数据就不需要跟右边的数据比较，效率明显提高。但是，极端情况下，取得pivot一边都是只有一个值，就退化为另一边都是满数据，退化为冒泡排序了。为了逆序导致的复杂度退化为O(n^2), 这里用三者取中值法，来实现快速排序。平均时间复杂度为O(nlogn).

堆排序：堆实际为完全二叉树，也就是用数组为容器。
大顶堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]
先建大顶堆，然后把顶端的值跟最后的值交换，堆大小减一，再次构建大顶堆。重复以上步骤，一直到堆减少为空，数组就是一个递增序列。
分析复杂度：建堆的时候，从节点开始遍历，length/2 - 1为index最大的节点，因为叶子节点2*(length/2 - 1) + 1 = length -1, 反证法如果length/2为index最大的节点，那么叶子节点2*(length/2) + 1 = length +1, 超过容量。建堆每个节点排序时间复杂度为O(logn), 所以建堆复杂度为n/2 * logn；每次去掉最大值再次建堆，时间复杂度小于 n* logn。两个过程的和小于3n/2 *logn，时间复杂度为O(nlogn).

代码 – 插入排序

import java.util.Arrays;public class InsertionSort {public void insertSort(int[] data) {for (int i = 1; i < data.length; i++) {int currentNumber = data[i];int j = i - 1;while (j >= 0 && data[j] > currentNumber) {data[j + 1] = data[j];j--;}data[j+1] = currentNumber;}}public static void main(String[] args) {int[] data = new int[]{4, 6, 5, 3, 7, 1, 2};System.out.println(Arrays.toString(data));InsertionSort obj = new InsertionSort();obj.insertSort(data);System.out.println(Arrays.toString(data));}}

代码 – 归并排序

import java.util.Arrays;public class MergeSort {public void mergeSort(int[] data) {int[] temp = new int[data.length];subMergeSort(data, 0, data.length - 1, temp);}public void subMergeSort(int[] data, int left, int right, int[] temp) {if (left < right) {int mid = left + (right - left) / 2;subMergeSort(data, left, mid, temp);subMergeSort(data, mid + 1, right, temp);merge(data, left, mid, right, temp);}}public void merge(int[] data, int left, int mid, int right, int[] temp) {int i = left;int k = mid + 1;int t = 0;while (i <= mid && k <= right) {if (data[i] < data[k]) {temp[t++] = data[i++];} else {temp[t++] = data[k++];}}while (i <= mid) {temp[t++] = data[i++];}while (k <= right) {temp[t++] = data[k++];}t = 0;while (left <= right) {data[left++] = temp[t++];}}public static void main(String[] args) {int[] data = new int[]{4, 6, 5, 3, 7, 1, 2};System.out.println(Arrays.toString(data));MergeSort obj = new MergeSort();obj.mergeSort(data);System.out.println(Arrays.toString(data));}}

代码 – 快速排序

import java.util.Arrays;public class QuickSort {public static void quickSort(int[] data) {// divide to left, right indexsubQuickSort(data, 0, data.length - 1);}public static void subQuickSort(int[] data, int leftIndex, int rightIndex) {if (leftIndex >= rightIndex) {return;}// pivot data: mid of the three number, and swap to right -1buildPivotCloseToRight(data, leftIndex, rightIndex);int i = leftIndex;int k = rightIndex - 1;int pivot = data[k];// two point from two side, ++left, --rightwhile (true) {// while ++left > pivotwhile ((i+1) < rightIndex && data[++i] < pivot) {}// while --right < pivotwhile ((k - 1) > leftIndex && data[--k] > pivot) {}// left < right, then swapif (i < k) {swap(data, i, k);} else {break;}}// if left < pivotIndex ,swapif (i < rightIndex - 1) {swap(data, i, rightIndex - 1);}// divide two sub quick sortsubQuickSort(data, leftIndex, i);subQuickSort(data, i + 1, rightIndex);}public static void buildPivotCloseToRight(int[] data, int leftIndex, int rightIndex) {int midIndex = leftIndex + (rightIndex - leftIndex) / 2;// swap small in left, between left, midif (data[leftIndex] > data[midIndex]) {swap(data, leftIndex, midIndex);}// swap small in left, between left, rightif (data[leftIndex] > data[rightIndex]) {swap(data, leftIndex, rightIndex);}// swap big in right, between mid, rightif (data[midIndex] > data[rightIndex]) {swap(data, midIndex, rightIndex);}// swap pivot int right -1swap(data, midIndex, rightIndex - 1);}public static void swap(int[] data, int i, int k) {int temp = data[i];data[i] = data[k];data[k] = temp;}public static void main(String[] args) {int[] data = new int[]{4, 6, 5, 3, 7, 1, 2};System.out.println(Arrays.toString(data));quickSort(data);System.out.println(Arrays.toString(data));}}

代码 – 堆排序

import java.util.Arrays;public class HeapSort {public static void heapSort(int[] data) {// build top big heapfor (int i = data.length/2 -1; i >= 0; i--) {// build heapbuildHeap(data, i, data.length);}// change seat between the first and the last, length--for (int k = data.length - 1; k >=0; k--) {// change seat between first and last oneswap(data, 0, k);// build heapbuildHeap(data, 0, k);}}public static void buildHeap(int[] data, int nodeIndex, int length) {int temp = data[nodeIndex];for (int k = nodeIndex * 2 + 1; k < length; k = k * 2 + 1) {if (k + 1 < length && data[k] < data[k + 1]) {k = k + 1;}if (data[k] > temp) {data[nodeIndex] = data[k];nodeIndex = k;} else {break;}}data[nodeIndex] = temp;}public static void swap(int[] data, int i, int j) {int temp = data[i];data[i] = data[j];data[j] = temp;}public static void main(String[] args) {int[] data = new int[]{4, 6, 5, 3, 7, 1, 2};System.out.println(Arrays.toString(data));heapSort(data);System.out.println(Arrays.toString(data));}}