直接插入没有利用到要插入的序列已有序的特点，插入第 i 个元素时可以通过二分查找找到插入位置 insertIndex，再把 i~insertIndex 之间的所有元素后移一位，把第 i 个元素放在插入位置上。
123456789101112131415161718192021222324 public void binaryInsertionSort(``int``[] nums) {`` ``for (``int i = ``1``; i < nums.length; i++) {`` ``int insertNum = nums[i];`` ``int insertIndex = -``1``;`` ``int start = ``0``;`` ``int end = i - ``1``;`` ``while (start <= end) {`` ``int mid = start + (end - start) / ``2``;`` ``if (insertNum > nums[mid])`` ``start = mid + ``1``;`` ``else if (insertNum < nums[mid])`` ``end = mid - ``1``;`` ``else {`` ``insertIndex = mid + ``1``;`` ``break``;`` ``}`` ``}`` ``if (insertIndex == -``1``)`` ``insertIndex = start;`` ``if (i - insertIndex >= ``0``)`` ``System.arraycopy(nums, insertIndex, nums, insertIndex + ``1``, i - insertIndex);`` ``nums[insertIndex] = insertNum;`` ``}``}Q3：希尔排序的原理？
又称缩小增量排序，是对直接插入排序的改进，不稳定，平均时间复杂度 O(n1.3)，最差时间复杂度 O(n²)，最好时间复杂度 O(n)，空间复杂度 O(1)。
把记录按下标的一定增量分组，对每组进行直接插入排序，每次排序后减小增量，当增量减至 1 时排序完毕。
123456789101112 public void shellSort(``int``[] nums) {`` ``for (``int d = nums.length / ``2``; d > ``0 ; d /= ``2``) {`` ``for (``int i = d; i < nums.length; i++) {`` ``int insertNum = nums[i];`` ``int insertIndex;`` ``for (insertIndex = i - d; insertIndex >= ``0 && nums[insertIndex] > insertNum; insertIndex -= d) {`` ``nums[insertIndex + d] = nums[insertIndex];`` ``}`` ``nums[insertIndex + d] = insertNum;`` ``}`` ``}``}Q4：直接选择排序的原理？
不稳定，时间复杂度 O(n²)，空间复杂度 O(1)。
每次在未排序序列中找到最小元素，和未排序序列的第一个元素交换位置，再在剩余未排序序列中重复该操作直到所有元素排序完毕。
12345678910111213 public void selectSort(``int``[] nums) {`` ``int minIndex;`` ``for (``int index = ``0``; index < nums.length - ``1``; index++){`` ``minIndex = index;`` ``for (``int i = index + ``1``;i < nums.length; i++){`` ``if``(nums[i] < nums[minIndex]) `` ``minIndex = i;`` ``}`` ``if (index != minIndex){`` ``swap(nums, index, minIndex);`` ``}`` ``}``}Q5：堆排序的原理？
是对直接选择排序的改进，不稳定，时间复杂度 O(nlogn)，空间复杂度 O(1)。
将待排序记录看作完全二叉树，可以建立大根堆或小根堆，大根堆中每个节点的值都不小于它的子节点值，小根堆中每个节点的值都不大于它的子节点值。
以大根堆为例，在建堆时首先将最后一个节点作为当前节点，如果当前节点存在父节点且值大于父节点，就将当前节点和父节点交换。在移除时首先暂存根节点的值，然后用最后一个节点代替根节点并作为当前节点，如果当前节点存在子节点且值小于子节点，就将其与值较大的子节点进行交换，调整完堆后返回暂存的值。
123456789101112131415161718192021222324252627282930 public void add(``int``[] nums, ``int i, ``int num){`` ``nums[i] = num;`` ``int curIndex = i;`` ``while (curIndex > ``0``) {`` ``int parentIndex = (curIndex - ``1``) / ``2``;`` ``if (nums[parentIndex] < nums[curIndex]) `` ``swap(nums, parentIndex, curIndex);`` ``else break``;`` ``curIndex = parentIndex;`` ``}``} public int remove(``int``[] nums, ``int size){`` ``int result = nums[``0``];`` ``nums[``0``] = nums[size - ``1``];`` ``int curIndex = ``0``;`` ``while (``true``) {`` ``int leftIndex = curIndex * ``2 + ``1``;`` ``int rightIndex = curIndex * ``2 + ``2``;`` ``if (leftIndex >= size) ``break``;`` ``int maxIndex = leftIndex;`` ``if (rightIndex < size && nums[maxIndex] < nums[rightIndex])`` ``maxIndex = rightIndex;`` ``if (nums[curIndex] < nums[maxIndex])`` ``swap(nums, curIndex, maxIndex);`` ``else break``;`` ``curIndex = maxIndex;`` ``}`` ``return result;``}Q6：冒泡排序的原理？
稳定，平均/最坏时间复杂度 O(n²)，元素基本有序时最好时间复杂度 O(n)，空间复杂度 O(1)。