学算法的时候自己实现的在O(n^2)这个时间复杂度上比较基础和经典的算法 其中归并排序是我目前学到nlog级别的唯一算法 /** * Created by yyairmarkyy on 2017/9/28. */public class SortUtil { /** * 选择排
/**
* 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