java|【算法】O(n2)时间复杂度和O(nlogn)排序算法的简要分析数据结构|算法

排序算法的概述 【java|【算法】O(n2)时间复杂度和O(nlogn)排序算法的简要分析】排序算法按时间复杂度分可以分为O(n2) 和 O(logn)
O(n2) 排序算法流程分析 1 2 3 4.n个数已有序 5.开始扫描第n+1个数 n个无序序列外层遍历遍历至第n个数内层遍历外层遍历的时间复杂度是n，内层遍历的时间复杂度也是n，由于嵌套关系，总的时间复杂度就是O(n2) 。O(n2) 排序算法都使用上述的流程，典型的代表有选择排序 、插入排序
选择排序
1 2 3 value和min交换 5.开始扫描第n+1个数 n个无序序列外层遍历设第n个数的value为最小值内层遍历找比vlaue还小的值min

/** * 选择排序，确认下标后交换，内层循环是寻找到最小下标 * */ private static int[] selectSort(int... arr) { // 可变参数列表，传参可以使用selectSort(1,2,3); int min; // 记录下标 for (int i = 0; i < arr.length; i++) { min = i; for (int j = i + 1; j < arr.length; j++) { if (arr[min] > arr[j]) { min = j; // 一轮中确认最小值的下标 } } swap(arr, i, min); } return arr; }

插入排序 1 2 3 将第n个数的value插入到有序区间继续从无序区间找待插入值 n个无序序列外层遍历设第n个数的value为待插入值 1..n-1的数已有序内层遍历找1..n-1的数

/** * 左边为有序区，右边为无序区，从无序区中选择元素插入到有序区中 * */ private static int[] insertionSort(int... arg) { for (int i = 1; i < arg.length; i++) { int candidate = arg[i]; int j; for (j = i; j > 0; j--) { if (arg[j - 1] > candidate) { arg[j] = arg[j - 1]; // 往后挪一个位置 } else { break; // 候选人比当前元素还要小，提前终止比较 } } arg[j] = candidate; } return arg; }

拓展：插入排序是希尔排序的基础
冒泡排序如果是从左往右冒泡
每一轮都选取一个最大值，并固定到右边，右边是有序区间。
跟选择排序 和 插入排序 不同，冒泡排序外层循环不会选待交换元素。
会从无序区间选举一个最大值往右推。
1 2 3 4.n个数已有序 5.下一轮确定倒数第n大的数 n个无序序列外层遍历遍历至第n轮内层遍历

/** * 冒泡排序法 * */ private static int[] bubbleSort(int ... arg){ // 向右冒泡，最大的放在左右边 for (int i = 0; i < arg.length - 1; i++) { for (int j = 0; j < arg.length - i - 1; j++) { if(arg[j] > arg[j + 1]) { swap(arg, j, j + 1); } } } return arg; }

拓展：优化

/** * 冒泡排序法优化1, 每趟减少一个遍历元素 * 从左往右冒泡 * */ private static int[] advanceBubbleSort(int ... arg){ int n = arg.length; boolean swapped; do { swapped = false; for (int i = 1; i < n; i++) { if (arg[i - 1] > arg[i]){ swap(arg,i - 1,i); swapped = true; } } n--; // 每一趟都会确认一个最大值，最右的元素下一轮不用考虑 } while (swapped); return arg; }

/** * 冒泡排序法优化2, 每趟减少N个遍历元素 * */ private static int[] advanceBubbleSort2(int ... arg){ int n = arg.length, newn; do { newn = 0; for (int i = 1; i < arg.length; i++) { if (arg[i - 1] > arg[i]){ swap(arg,i - 1,i); newn = i; } } } while (newn > 0); // 存在无序边界才继续冒泡return arg; }

O(nlogn) 排序算法流程分析 O(n2) 算法的理解都是较简单的
O(nlogn) 主要的思路就是大问题拆成结构相同的小问题。
时间复杂度能降到O(nlogn) ，得力于内层循环每次都比上一次少 1/2 的遍历个数。
常见的时间复杂度为 O(nlogn) 的算法有归并排序 快速排序。留个坑来写流程分析
参考github