快速排序
时间复杂度
O(nlogn) 空间复杂度O（logn） 不稳定
时间复杂度：
最坏O（n^2） 当划分不均匀时候 逆序and排好序都是最坏情况最好O（n） 当划分均匀partition的时间复杂度: O（n）一共需要logn次partition代码
public class quickSort { public static void sort(int[] array, int start, int end) { if (start < end) { int p = partition(array, start, end); sort(array, start, p - 1); sort(array, p + 1, end); } } public static int partition(int[] A, int start, int end) { int left = start; int right = end; int pivot = A[start]; while (left < right) { while (left < right && A[right]> pivot) { right--; } while (left < right && A[left] <= pivot) { left++; } swap(A, left, right); } swap(A, start, left); return left; } public static void swap(int[] A, int i, int j) { int tem = A[i]; A[i] = A[j]; A[j] = tem; } public static void main(String[] args) { int array[] = {8,7,1,6,5,4,3,2}; quickSort s = new quickSort(); s.sort(array, 0, 7); for(int i=0;i 归并排序
时间复杂度
时间复杂度 O(nlogn), 空间复杂度O(n) +O(logn)
排序时间与输入无关，最佳情况，最坏情况都是如此, 稳定。代码
public class MergeSort {
public static void sort(int[] A, int start, int end) { if (start >= end) { return; } int mid = (start + end) / 2; sort(A, start, mid); sort(A, mid + 1, end); merge(A, start, mid, end);}public static void merge(int[] A, int start, int mid, int end) { int[] helper = new int[A.length]; for (int i = start; i <= end; i++) { helper[i] = A[i]; } int i = start, j = mid + 1; for (int k = start; k <= end; k++) { if (i > mid) { A[k]= helper[j++]; } else if (j > end) { A[k]= helper[i++]; } else if (helper[i]> helper[j]) { A[k]= helper[j++]; } else { A[k]= helper[i++]; } }}public static void main(String[] args) { int array[] = {8,7,1,6,5,4,3,2}; MergeSort s = new MergeSort(); s.sort(array, 0, 7); for(int i=0;i }