快排

• 选主元
  • 经典快排：选数组最后一个元素
  • 将数组第一个，中间位置，最后1个位置三个数交换达到排序的目的，将中间位置的和最后一个位置的交换
  • 随机函数选择1个与最后一个位置的交换
• 划分子集
  • int i = left - 1, j = right
  • ++i,–j . 2个指针左指针和右指针，和主元比较，相向行驶。2个while循环
  • i < j 时 交换（交换时的arr[i] >= 主元，交换时的arr[j] <= 主元）,否则退出循环
  • i+1的位置即是本轮主元的最终位置

 private static int partition2(int[] array, int left,  private static int partition2(int[] array, int left, int right) {

       //选主元
        int privot = array[9];
       //划分子集
        int i = left - 1,j = right;
        for (;;){
            //大于等于的放右边
            while (array[++i] < privot){}//红色警报
            while (array[j--] > privot){}//红色警报
            //和主元相等的时候也交换
            if (i < j){
                swap(array,i,j);
            }else{
                break;
            }
        }
        swap(array,i,right);
        return i ;
    }
 public static void quickSort(int a[],int left,int right){
        if (left < right){
            int q = partition2(a,left,right);
            quickSort(a,left,q-1);
            quickSort(a,q +1 ,right);
        }
    }
void quick_sort(int[] arr,int length){
        quickSort(arr,0,length - 1);
    }

平均情况下时间复杂度： O(nlogn),空间复杂度O(logn)

最快情况下时间复杂度: O(n^2^) ,空间复杂度O(n)

注 :数组中元素全部相同时，不交换的情况下一轮就是O(n) ,整体就是O(n^2^)

归并排序

算法思想：采用分治的策略，选取中间位置，将数组划分为2，然后合并，递归的处理左边，递归的处理右边。

合并是合并2个有序子数组，要1个辅助数组。

public static void mergeSort(public static void mergeSort(int[] arr) {
	if (arr == null || arr.length < 2) {
		return;
	}
	mergeSort(arr, 0, arr.length - 1);
}

public static void mergeSort(int[] arr, int l, int r) {
	if (l == r) {
		return;
	}
	int mid = l + ((r - l) >> 1);
	mergeSort(arr, l, mid);
	mergeSort(arr, mid + 1, r);
	merge(arr, l, mid, r);
}

public static void merge(int[] arr, int l, int m, int r) {
	int[] help = new int[r - l + 1];
	int i = 0;
	int p1 = l;
	int p2 = m + 1;
	while (p1 <= m && p2 <= r) {
		help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
	}
	while (p1 <= m) {
		help[i++] = arr[p1++];
	}
	while (p2 <= r) {
		help[i++] = arr[p2++];
	}
	for (i = 0; i < help.length; i++) {
		arr[l + i] = help[i];
	}
}

快排和归并都是用分治的策略。

归并排序时间复杂度：O(nlogn),空间复杂度O(n)

3. 堆排序

   ①先理解堆结构，有一种O(n)的算法把一个数组调整成大根或者小根堆

   ②③

堆结构非常重要，建堆O(n)，被火车撞了都不能忘记。最大的亮点是形成堆后，进来1个，O(Logn)可以搞定

合并两个有序数组

https://leetcode-cn.com/problems/merge-sorted-array/

用归并的方法，从后往前扫描。