十大排序算法详解 (4)

时间复杂度最高如下：O(n^2)

6.4 优化一

优化思路 => 将交换改为挪动

先将待插入元素备份

头部有序数据中比待插入元素大的，都朝尾部方向挪动1个位置

将待插入元素放到最终合适位置

注意：逆序对越多，该优化越明显

public class InsertionSort<T extends Comparable<T>> extends Sort<T> { @Override protected void sort() { for (int i = 1; i < array.length; i++) { int cur = i; T val = array[cur]; while(cur > 0 && cmp(val,array[cur - 1]) < 0) { array[cur] = array[cur - 1];//优化重点在这里 cur--; } array[cur] = val; } } } 6.5 优化二

优化思路 => 将交换改为二分搜索（较少比较次数）

二分搜索理解

如何确定一个元素在数组中的位置？（假设数组里全是整数）

如果是无序数组，从第 0 个位置开始遍历搜索，平均时间复杂度：O(n)

如果是有序数组，可以使用二分搜索，最坏时间复杂度：O(log^n)

思路

如下，假设在 [begin, end) 范围内搜索某个元素 v，mid == (begin + end) / 2

如果 v < mid，去 [begin,mid) 范围内二分搜索

如果 v > mid，去 [mid + 1,end) 范围内二分搜索

如果 v == mid，直接返回 mid

实例

/** 二分搜索-基本实现 * 查找val在有序数组arr中的位置，找不到就返回-1 */ private static int indexOf(Integer[] arr,int val) { if(arr == null || arr.length == 0) return -1; int begin = 0; //注意这里end设计为arr.length便于求数量（end - begin） int end = arr.length; while (begin < end) { int mid = (begin + end) >> 1; if(val < arr[mid]) { end = mid; } else if(val > arr[mid]) { begin = mid + 1; } else { return mid; } } return -1; }

二分搜索(Binary Search)优化实现

之前的插入排序代码，在元素 val 的插入过程中，可以先二分搜索出合适的插入位置，然后将元素 val 插入

适合于插入排序的二分搜索必须满足：要求二分搜索返回的插入位置是第1个大于 val 的元素位置

如果 val 是 5 ，返回 2

如果 val 是 1，返回 0

如果 val 是15，返回 7

如果 val 是 8，返回 5

实现思路

假设在 [begin,end) 范围内搜索某个元素 val，mid == (begin + end) / 2

如果val < mid，去 [begin,mid) 范围内二分搜索

如果val >= mid，去 [mid + 1,end) 范围内二分搜索

当 begin == end == x，x 就是待插入位置

实例

/** * 二分搜索-适用于插入排序 * 查找val在有序数组arr中可以插入的位置 * 规定：要求二分搜索返回的插入位置是第1个大于 val 的元素位置 */ private static int search(Integer[] arr,int val) { if(arr == null || arr.length == 0) return -1; int begin = 0; int end = arr.length; while (begin < end) { int mid = (begin + end) >> 1; if(val < arr[mid]) { end = mid; } else { begin = mid + 1; } } return begin; }

插入排序最终实现

注意：使用了二分搜索后，只是减少了比较次数，但插入排序的平均时间复杂度依然是O(n^2)

public class InsertionSort<T extends Comparable<T>> extends Sort<T> { /** 优化 => 二分搜索 */ @Override protected void sort() { for (int begin = 1; begin < array.length; begin++) { //这里为什么传索引而不是传值？ // => 传索引还可以知道前面已经排好序的数组区间：[0,i) insert(begin,search(begin)); } } /** 将source位置的元素插入到dest位置 */ private void insert(int source,int dest) { //将[dest,source)范围内的元素往右边挪动一位 T val = array[source]; for (int i = source; i > dest; i--) { array[i] = array[i - 1]; } //插入 array[dest] = val; } private int search(int index) { T val = array[index]; int begin = 0; int end = index; while (begin < end) { int mid = (begin + end) >> 1; if(cmp(val,array[mid]) < 0) { end = mid; } else { begin = mid + 1; } } return begin; } } 6.6 算法优劣

最坏，平均时间复杂度为 O(n^2)，最好时间复杂度为 O(n)

空间复杂度为 O(1)

属于稳定排序

7. 归并排序（Merge Sort） 7.1 执行流程

不断的将当前序列平均分割成 2 个子序列，直到不能再分割（序列中只剩一个元素）

不断的将 2 个子序列合并成一个有序序列，直到最终只剩下 1 个有序序列