排序
快速排序
快速排序算法采用分而治之的思想，从数组中选择一个“基准”元素，根据小于或大于基准将其他元素划分为两个子数组，然后递归对子数组进行排序。
1 public int partition(int[] nums, int l, int r) {
2 int key = nums[l];
3 while (l < r) {
4 while (l < r && nums[r] >= key) {
5 r--;
6 }
7 nums[l] = nums[r];
8 while (l < r && nums[l] < key) {
9 l++;
10 }
11 nums[r] = nums[l];
12 }
13 nums[l] = key;
14 return l;
15 }
16
17 public void qk(int nums[], int l, int r) {
18 if (l >= r)
19 return;
20 int pivot = partition(nums, l, r);
21 qk(nums, l, pivot - 1);
22 qk(nums, pivot + 1, r);
23 }
挖坑法
以上代码为“挖坑法”，由两个函数构成，qk 函数负责递归调用，partition函数负责排序并返回排序后基准元素位置。
在左右指针没有对撞的情况下：
- 先用右指针往左遍历，当找到比基准值小的数时，将该数填入左指针的位置。
- 左指针往右遍历，找到比基准值大的数时，填入右指针的位置。
- 若左右指针未对撞，重复以上步骤。
左右指针对撞，排序完成，得到基准数位置。然后对被基准数分开的两个子数组继续使用快速排序。
注意
右指针的数填入左指针前，左指针的数已经被取为基准，因此不会丢失。 左指针的数填入右指针时，右指针的数已经填入左指针遍历前的位置，因此也不会丢失。
堆排序
堆排序（Heapsort）是一种常用的排序算法，它使用了一棵树形数据结构，称为堆（heap），来实现排序。 heap 是一种完全二叉树，其中每个节点都满足某种特定性质（通常是父节点大于或等于左右子节点）。
1 import java.util.Arrays;
2
3 public class HeapSort {
4 public static void main(String[] args) {
5 int arr[] = {4, 6, 8, 5, 9};
6 System.out.println("排序前" + Arrays.toString(arr));
7 heapSort(arr);
8 System.out.println("排序后" + Arrays.toString(arr));
9 }
10
11 public static void heapSort(int arr[]) {
12 int temp = 0;
13
14 for (int i = arr.length / 2 - 1; i >= 0; i--) {
15 adjustHeap(arr, i, arr.length);
16 }
17 /**
18 * 将堆项元素与末尾元素交换，将最大元素"沉"到数组末端;
19 * 重新调整结构，使其满足堆定义，然后继续交换堆项元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。
20 */
21
22 for (int j = arr.length - 1; j > 0; j--) {
23 temp = arr[j];
24 arr[j] = arr[0];
25 arr[0] = temp;
26 adjustHeap(arr, 0, j);
27 }
28 }
29
30
31 /**
32 * 将一个数组（二叉树）调整成一个大根堆
33 * 功能：完成将以i对应的非叶子结点的树调整成大顶堆
34 * 举例int arr[]={4, 6,8,5,9};=>i=1=> adjustHeap=>得到{4,9,8,5, 6}
35 * 如果我们再次调用adjustHeap 传入的是i=0=>得到{4,9, 8,5,6}=> {9,6,8,5, 4}
36 *
37 * @param arr 待调整的数组
38 * @param i 表示非叶子结点在数组中索引
39 * @param length 表示对多少个元素继续调整，length 是在逐渐的减少
40 */
41 public static void adjustHeap(int arr[], int i, int length) {
42
43 int temp = arr[i];//先取出当前元素的值，保存在临时变量
44 //开始调整.
45 //说明:k=i*2+1k是i结点的左子结点
46 for (int k = i * 2 + 1; k < length; k = k * 2 + 1) {
47 if (k + 1 < length && arr[k] < arr[k + 1]) {
48 k++;
49 }
50 if (arr[k] > arr[i]) {
51 arr[i] = arr[k];
52 i = k;
53 } else {
54 break;
55 }
56 }
57 arr[i] = temp;
58 }
59 }
二分法插入排序
二分法没有排序，只有查找。所以当找到要插入的位置时。移动必须从最后一个记录开始，向后移动一位，再移动倒数第2位，直到要插入的位置的记录移后一位。
二分插入排序是稳定的与二分查找的复杂度相同； 最好的情况是当插入的位置刚好是二分位置 所用时间为O(log₂n)； 最坏的情况是当插入的位置不在二分位置 所需比较次数为O(n)，无限逼近线性查找的复杂度。
1 public static void advanceInsertSortWithBinarySearch(int[] arr) {
2 for (int i = 1; i < arr.length; i++) {
3 int temp = arr[i];
4 int low = 0, high = i - 1;
5 int mid = -1;
6 while (low <= high) {
7 mid = low + (high - low) / 2;
8 if (arr[mid] > temp) {
9 high = mid - 1;
10 } else { // 元素相同时，也插入在后面的位置
11 low = mid + 1;
12 }
13 }
14 for(int j = i - 1; j >= low; j--) {
15 arr[j + 1] = arr[j];
16 }
17 arr[low] = temp;
18 }
19 }