其中 冒泡,选择,归并,快速,希尔,堆排序属于比较排序
稳定性理解
如果相等的两个元素,在排序前后的相对位置保持不变,那么这是稳定的排序算法。
排序前:5,1,3(a),4,7,3(b)
稳定的排序:1,3(a),3(b),4,5,7
不稳定的排序:1,3(b),3(a),4,5,7
原地算法(In-place Algorithm)理解
定义:不依赖额外的资源或依赖少数的额外资源(空间复杂度较低),仅依靠输出覆盖输入(例如直接对输入的数组进行操作)
用于提供测试数据与测试代码正确性
public class Asserts { public static void test(boolean value) { try { if (!value) throw new Exception("测试未通过"); } catch (Exception e) { e.printStackTrace(); } } }
public class Integers { /** 生成随机数 */ public static Integer[] random(int count, int min, int max) { if (count <= 0 || min > max) return null; Integer[] array = new Integer[count]; int delta = max - min + 1; for (int i = 0; i < count; i++) { array[i] = min + (int)(Math.random() * delta); } return array; } /** 合并两个数组 */ public static Integer[] combine(Integer[] array1, Integer[] array2) { if (array1 == null || array2 == null) return null; Integer[] array = new Integer[array1.length + array2.length]; for (int i = 0; i < array1.length; i++) { array[i] = array1[i]; } for (int i = 0; i < array2.length; i++) { array[i + array1.length] = array2[i]; } return array; } public static Integer[] same(int count, int unsameCount) { if (count <= 0 || unsameCount > count) return null; Integer[] array = new Integer[count]; for (int i = 0; i < unsameCount; i++) { array[i] = unsameCount - i; } for (int i = unsameCount; i < count; i++) { array[i] = unsameCount + 1; } return array; } /** * 生成头部和尾部是升序的数组 * disorderCount:希望多少个数据是无序的 */ public static Integer[] headTailAscOrder(int min, int max, int disorderCount) { Integer[] array = ascOrder(min, max); if (disorderCount > array.length) return array; int begin = (array.length - disorderCount) >> 1; reverse(array, begin, begin + disorderCount); return array; } /** * 生成中间是升序的数组 * disorderCount:希望多少个数据是无序的 */ public static Integer[] centerAscOrder(int min, int max, int disorderCount) { Integer[] array = ascOrder(min, max); if (disorderCount > array.length) return array; int left = disorderCount >> 1; reverse(array, 0, left); int right = disorderCount - left; reverse(array, array.length - right, array.length); return array; } /** * 生成头部是升序的数组 * disorderCount:希望多少个数据是无序的 */ public static Integer[] headAscOrder(int min, int max, int disorderCount) { Integer[] array = ascOrder(min, max); if (disorderCount > array.length) return array; reverse(array, array.length - disorderCount, array.length); return array; } /** * 生成尾部是升序的数组 * disorderCount:希望多少个数据是无序的 */ public static Integer[] tailAscOrder(int min, int max, int disorderCount) { Integer[] array = ascOrder(min, max); if (disorderCount > array.length) return array; reverse(array, 0, disorderCount); return array; } /** 升序生成数组 */ public static Integer[] ascOrder(int min, int max) { if (min > max) return null; Integer[] array = new Integer[max - min + 1]; for (int i = 0; i < array.length; i++) { array[i] = min++; } return array; } /** 降序生成数组 */ public static Integer[] descOrder(int min, int max) { if (min > max) return null; Integer[] array = new Integer[max - min + 1]; for (int i = 0; i < array.length; i++) { array[i] = max--; } return array; } /** 反转数组 */ private static void reverse(Integer[] array, int begin, int end) { int count = (end - begin) >> 1; int sum = begin + end - 1; for (int i = begin; i < begin + count; i++) { int j = sum - i; int tmp = array[i]; array[i] = array[j]; array[j] = tmp; } } /** 复制数组 */ public static Integer[] copy(Integer[] array) { return Arrays.copyOf(array, array.length); } /** 判断数组是否升序 */ public static boolean isAscOrder(Integer[] array) { if (array == null || array.length == 0) return false; for (int i = 1; i < array.length; i++) { if (array[i - 1] > array[i]) return false; } return true; } /** 打印数组 */ public static void println(Integer[] array) { if (array == null) return; StringBuilder string = new StringBuilder(); for (int i = 0; i < array.length; i++) { if (i != 0) string.append("_"); string.append(array[i]); } System.out.println(string); } }
public class Times { private static final SimpleDateFormat fmt = new SimpleDateFormat("HH:mm:ss.SSS"); public interface Task { void execute(); } public static void test(String title, Task task) { if (task == null) return; title = (title == null) ? "" : ("【" + title + "】"); System.out.println(title); System.out.println("开始:" + fmt.format(new Date())); long begin = System.currentTimeMillis(); task.execute(); long end = System.currentTimeMillis(); System.out.println("结束:" + fmt.format(new Date())); double delta = (end - begin) / 1000.0; System.out.println("耗时:" + delta + "秒"); System.out.println("-------------------------------------"); } }
public abstract class Sort<T extends Comparable<T>> implements Comparable<Sort<T>> { /** 目标数组 */ protected T[] array; /** 比较次数 */ private int cmpCount; /** 交换次数 */ private int swapCount; /** 执行时间 */ private long time; /** 小数格式化 */ private DecimalFormat fmt = new DecimalFormat("#.00"); /** 预处理 */ public void sort(T[] array) { if (array == null || array.length < 2) return; this.array = array; long begin = System.currentTimeMillis(); sort(); time = System.currentTimeMillis() - begin; } /** 目标方法 */ protected abstract void sort(); /** * 比较数组下标对应的值 * * 返回值等于0,代表 array[index1] == array[index2] * 返回值小于0,代表 array[index1] < array[index2] * 返回值大于0,代表 array[index1] > array[index2] */ protected int cmp(int index1, int index2) { cmpCount++; return array[index1].compareTo(array[index2]); } /** 比较值 */ protected int cmp(T value1, T value2) { cmpCount++; return value1.compareTo(value2); } /** 交换值 */ protected void swap(int index1, int index2) { swapCount++; T tmp = array[index1]; array[index1] = array[index2]; array[index2] = tmp; } /** 稳定性测试 */ @SuppressWarnings("unchecked") private boolean isStable() { Student[] students = new Sort.Student[20]; for (int i = 0; i < students.length; i++) { //(0,10) (10,10) (20,10) (30,10) students[i] = new Student(i * 10, 10); } sort((T[]) students);//只会对年龄进行排序 for (int i = 1; i < students.length; i++) { int score = students[i].score; int prevScore = students[i - 1].score; if (score != prevScore + 10) return false; } return true; } private static class Student implements Comparable<Student>{ Integer score; Integer age; public Student(Integer score, Integer age) { this.score = score; this.age = age; } @Override public int compareTo(Student o) { return age - o.age; } } /** 排序方式 */ @Override public int compareTo(Sort o) { int result = (int)(time - o.time); if(result != 0) return result; result = cmpCount - o.cmpCount; if(result != 0) return result; return swapCount - o.swapCount; } @Override public String toString() { return "【" + getClass().getSimpleName() + "】\n" + "交换次数 ==> " + numberString(swapCount) + "\n" + "比较次数 ==> " + numberString(cmpCount) + "\n" + "执行时间 ==> " + time * 0.001 + "s" + "\n" + "稳定性 ==> " + isStable() + "\n" + "================================="; } /** 数字格式化 */ private String numberString(int number) { if (number < 10000) return "" + number; if (number < 100000000) { return fmt.format(number / 10000.0) + "万"; } return fmt.format(number / 100000000.0) + "亿"; } }
public void sort() { for (int eIndex = array.length - 1; eIndex > 0; eIndex--) { for (int i = 1; i <= eIndex; i++) { if (cmp(i, i - 1) < 0) { swap(i, i - 1); } } } }
优化方案:如果序列已经完全有序,可以提前终止冒泡排序
缺点:只有当完全有序时才会提前终止冒泡排序,概率很低
public void sort() { for (int eIndex = array.length - 1; eIndex > 0; eIndex--) { boolean sorted = true; for (int i = 1; i <= eIndex; i++) { if (cmp(i,i - 1) < 0) { swap(i, i - 1); sorted = false; } } if (sorted) break; } }
优化方案:如果序列尾部已经局部有序,可以记录最后一次交换的位置,减少比较次数
public class BubbleSort<T extends Comparable<T>> extends Sort<T> { /** * 优化方式二:如果序列尾部已经局部有序,可以记录最后依次交换的位置,减少比较次数 * 为什么这里sortedIndex为1(只要保证 eIndex-- > 0 即可)? * => 如果sortedIndex为eIndex,当数组第一次就完全有序时,就退回到最初的版本了 * => 如果sortedIndex为1,当数组第一次就完全有序时,一轮扫描就结束了! * */ @Override public void sort() { for (int eIndex = array.length - 1; eIndex > 0; eIndex--) { int sortedIndex = 1; //记录最后一次交换的下标位置 for (int i = 1; i <= eIndex; i++) { if (cmp(i, i - 1) < 0) { swap(i, i - 1); sortedIndex = i; } } eIndex = sortedIndex; } } }
最坏,平均时间复杂度:O(n^2),最好时间复杂度:O(n)
空间复杂度:O(1)
属于稳定排序
注意:稍有不慎,稳定的排序算法也能被写成不稳定的排序算法,如下冒泡排序是不稳定的
public void sort() { for (int eIndex = array.length - 1; eIndex > 0; eIndex--) { for (int i = 1; i <= eIndex; i++) { if (cmp(i, i - 1) <= 0) { swap(i, i - 1); } } } }
这里以选最小元素为例
public class SelectionSort<T extends Comparable<T>> extends Sort<T> { @Override public void sort() { for (int eIndex = array.length - 1; eIndex > 0; eIndex--) { int maxIndex = 0; for (int i = 1; i <= eIndex; i++) { //注意:为了稳定性,这里要写 <= if (cmp(maxIndex, i) <= 0) { maxIndex = i; } } if(maxIndex != eIndex) swap(maxIndex, eIndex); } } }
选择排序是否还有优化的空间? => 使用堆来选择最大值
堆排序可以认为是对选择排序的一种优化
public class HeapSort<T extends Comparable<T>> extends Sort<T> { /** 记录堆数据 */ private int heapSize; @Override protected void sort() { // 原地建堆(直接使用数组建堆) heapSize = array.length; for (int i = (heapSize >> 1) - 1; i >= 0; i--) { siftDown(i); } while (heapSize > 1) { // 交换堆顶元素和尾部元素 swap(0, --heapSize); // 对0位置进行siftDown(恢复堆的性质) siftDown(0); } } /** 堆化 */ private void siftDown(int index) { T element = array[index]; int half = heapSize >> 1; while (index < half) { // index必须是非叶子节点 // 默认是左边跟父节点比 int childIndex = (index << 1) + 1; T child = array[childIndex]; int rightIndex = childIndex + 1; // 右子节点比左子节点大 if (rightIndex < heapSize && cmp(array[rightIndex], child) > 0) { child = array[childIndex = rightIndex]; } // 大于等于子节点 if (cmp(element, child) >= 0) break; array[index] = child; index = childIndex; } array[index] = element; } }
最好,最坏,平均时间复杂度:O(nlog^n)
空间复杂度:O(1)
属于不稳定排序
@SuppressWarnings({"rawtypes","unchecked"}) public class SortTest { public static void main(String[] args) { Integer[] arr1 = Integers.random(10000, 1, 20000); testSort(arr1, new SelectionSort(), new HeapSort(), new BubbleSort()); } static void testSort(Integer[] arr,Sort... sorts) { for (Sort sort: sorts) { Integer[] newArr = Integers.copy(arr); sort.sort(newArr); //检查排序正确性 Asserts.test(Integers.isAscOrder(newArr)); } Arrays.sort(sorts); for (Sort sort: sorts) { System.out.println(sort); } } }
在执行过程中,插入排序会将序列分为两部分(头部是已经排好序的,尾部是待排序的)
从头开始扫描每一个元素,每当扫描到一个元素,就将它插入到头部适合的位置,使得头部数据依然保持有序
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; while(cur > 0 && cmp(cur,cur - 1) < 0) { swap(cur,cur - 1); cur--; } } } }
什么是逆序对? => 数组 [2,3,8,6,1] 的逆序对为:<2,1> < 3,1> <8,1> <8,6> <6,1>
插入排序的时间复杂度与逆序对的数量成正比关系
时间复杂度最高如下:O(n^2)
优化思路 => 将交换改为挪动
先将待插入元素备份
头部有序数据中比待插入元素大的,都朝尾部方向挪动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; } } }
优化思路 => 将交换改为二分搜索(较少比较次数)
二分搜索理解
如何确定一个元素在数组中的位置?(假设数组里全是整数)
如果是无序数组,从第 0 个位置开始遍历搜索,平均时间复杂度:O(n)
如果是有序数组,可以使用二分搜索,最坏时间复杂度:O(log^n)
思路
实例
/** 二分搜索-基本实现 * 查找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在有序数组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; } }
merge
大致想法
细节
@SuppressWarnings("unchecked")public class MergeSort<T extends Comparable<T>> extends Sort<T> { private T[] leftArr; @Override protected void sort() { leftArr = (T[]) new Comparable[array.length >> 1]; sort(0, array.length); } /** 对 [begin,end) 位置的元素进行归并排序 */ private void sort(int begin, int end) { if (end - begin < 2) return; int mid = (begin + end) >> 1; sort(begin, mid); sort(mid, end); merge(begin, mid, end); } /** 将 [begin,mid) 和 [mid,end) 范围的序列合并成一个有序序列 */ private void merge(int begin, int mid, int end) { int li = 0, le = mid - begin; int ri = mid, re = end; int ai = begin; //备份左边数组 for (int i = 0; i < le; i++) { leftArr[i] = array[begin + i]; } //如果左边还没有结束(情况一) while (li < le) { //当 ri < re 不成立,就会一直leftArr挪动(情况二) if (ri < re && cmp(array[ri],leftArr[li]) < 0) { array[ai++] = array[ri++]; } else { //注意稳定性 array[ai++] = leftArr[li++]; } } }}
复杂度分析
T(n) = sort() + sort() + merge()=> T(n) = T(n/2) + T(n/2) + O(n)=> T(n) = 2T(n/2) + O(n) //由于sort()是递归调用,用T表示,由于T(n/2)不好估算,现在要理清T(n)与O(n)之间的关系T(1) = O(1)T(n)/n = T(n/2) / (n/2) + O(1) //令S(n) = T(n)/n S(1) = O(1) S(n) = S(n/2) + O(1) = S(n/4) + O(2) = S(n/8) + O(3) = S( n/(2^k) ) + O(k) = S(1) + O(log^n) = O(lon^n)T(n) = n*S(n) = O(nlog^n) => 归并排序时间复杂度:O(nlog^n)
常见递推式
总结
由于归并排序总是平均分割子序列,所以最好,最坏,平均时间复杂度都是:O(nlog^n)
空间复杂度:O(n/2 + log^n) = O(n),n/2用于临时存放左侧数组,log^n用于递归调用
属于稳定排序