如何将O(n^2)复杂度的算法改写为长尾？

本文共计586个文字，预计阅读时间需要3分钟。

学算法时，自己实现的在O(n^2)时间复杂度上的算法与基础和经典算法相比，归并排序是我目前学到达到nlog(n)级的唯一算法。/ / * Created by yyairmarkyy on 2017/9/28. */ / / / public class SortUtil { / / / /* 选择排序 */ / / / }

学算法的时候自己实现的在O(n^2)这个时间复杂度上比较基础和经典的算法 其中归并排序是我目前学到nlog级别的唯一算法

/** * Created by yyairmarkyy on 2017/9/28. */ public class SortUtil { /** * 选择排序法 O(n^2) * @param a * @return */ public static int[] selectSort(int[] a){ int lenth = a.length; for (int i = 0; i a[j+1]){ swap(a,j,j+1); } } } return a; } /** * 希尔排序 * @return */ public static int[] shellSort(int[] a) { int n = a.length; while (true){ n = n/2; for (int i=1;i 0 && a[j-1] >= insertValue;j--){ a[j] = a[j-1]; } a[j] = insertValue; } if (n == 1) break; } return a; } /** * 归并排序（O(nlogn)） * @param a * @return */ public static int[] mergeSort(int[] a){ mergeSort(a,0,a.length-1); return a; } /** * 归并排序中用来分段 * @param a * @param l * @param r */ private static void mergeSort(int[] a,int l,int r){ if (l>=r) return; int n = (l+r)/2; mergeSort(a,l,n); mergeSort(a,n+1,r); merge(a,l,n,r); } /** * 把每段进行排序合并（最小段为2个元素） * @param a * @param l * @param mid * @param r */ private static void merge(int[] a,int l,int mid,int r){ int arr[] = new int[r-l+1]; for (int i = l;i mid){ a[k] = arr[j-l]; j++; }else if (j>r){ a[k] = arr[i-l]; i++; }else if (arr[i-l] > arr[j-l]){ a[k] = arr[j-l]; j++; }else { a[k] = arr[i-l]; i++; } } } /** * 生成相对有序的无序数组 * @param n 数组大小 * @param swapTimes 需要打乱顺序的次数 * @return */ public static int[] generateNearlyRandomArray(int n,int swapTimes){ int[] arr = new int[n]; for (int i = 0 ; i