分治思想：快速排序、归并排序
分治法：将原问题划分为若干个规模较小而结构与原问题一致的子问题，递归解决这些子问题然后在合并结果。容器确定运行时间是分治法优点之一
分治在每一层递归上都有三个步骤：1、分解：将原问题分解为一系列子问题；2、解决：递归解决各个子问题；3、合并：将子问题的结果合并
快排重点在于划分，将原数组A根据某一下标q划分为俩个子数组，其中右边数组中的任意一个元素都大于等于A[q]，左边数组的任意一个元素都小于等于A[q]，这样就不需要合并了。
归并重点在合并，将原数组划分为俩个子数组，俩个数组各自的排序简单，但合并在一起有难度。
快排：
快排法如何划分：有单向扫描和双向扫描
单向扫描法：定主元素作为中间值 用俩个指针把数组分为3个区间。扫描指针：该指针左面元素是确认小于主元素的；扫描指针到第二个指针之间的区域为未知，第二个指针为末指针，末指针右边元素确认大于主元素。当扫描指针逐右扫到比主元素大的元素就跟末指针指的元素交换位置。然后扫描指针扫描交换过来的元素，末指针左移一项。
双向扫描法：头指针往后扫，找到第一个比主元素大的元素，末指针从末尾往前扫，找到第一个比主元素小的元素，然后交换位置
public class Test1 {
public static void main(String[] args) {
int[] arr = new int[]{4,5,7,2,1,6,7,9,3,23,16,54,8};
f1(arr,0,arr.length-1);
for (int i : arr) {
System.out.println(i);
}
}
//快排
static void f1(int[] arr,int p,int r){ //p为排序范围的左端点，r为右端点
//int q=partition1(arr,p,r);
int q=partition2(arr,p,r);
f1(arr,p,q-1);
f1(arr,q+1,r);
}
}
//一遍扫描法
static int partition1(int[] arr,int p,int r){
int pivot=arr[p];
int sp=p+1;//扫描指针
int bigger =r;//末指针
while(sp<=bigger){
if(arr[sp]<=pivot){
sp++;
}else{
swap(arr,sp,bigger);
bigger--;
}
}
//此时bigger指向小于等于pivot的最后一个元素，sp指向大于pivot的第一个元素
swap(arr,p,bigger);
return bigger;
}
//双向扫描
static int partition2(int[] arr,int p,int r){
int pivot=arr[p];
int left=p+1;
int right=r;
while(left<=right){
while(left<=right && arr[left]<=pivot) left++;
while(left<=right && arr[right]>pivot)right--;
if(left<right)
swap(arr,left,right);
}
swap(arr,p,right);
return right;
}
//交换数组内元素位置
static void swap(int[] arr,int sp,int bigger){
int t=arr[sp];
arr[sp]=arr[bigger];
arr[bigger]=t;
}
}缺陷：当每次定的主元素都为当前子序列中的最大值，这时时间复杂度就会退化为O(n^2);
归并排序
将原数组简单的划分为俩部分，对俩部分进行排序，然后用俩个指针分别指向俩个子序列的最小值处，比较后，放小的元素放入一个新的数组中，然后小的指针右移。
需要用一个辅助数组helper，复制arr的数据到helper中，在helper中进行比较，然后将结果赋值到arr中。
public class Test1 {
public static void main(String[] args) {
int[] arr = new int[]{4,5,7,2,1,6,7,9,3,23,16,54,8};
//归并排序
helper=new int[arr.length];
sort1(arr,0,arr.length-1);
for (int i : arr) {
System.out.println(i);
}
}
static int[] helper;
static void sort1(int[] arr,int low,int high){
if(low<high){
int mid = low+((high-low)>>1);
sort1(arr,low,mid);
sort1(arr,mid+1,high);
merge1(arr,low,mid,high);
}
}
//合并
static void merge1(int[] arr,int low,int mid,int high){
//把arr中数据拷贝到helper中
for(int i=low;i<=high;i++){
helper[i]=arr[i];
}
int left =low; //左侧队伍的头指针，指向待比较的元素
int right =mid+1; //右侧队伍的头指针，指向待比较的元素
int current=low; //原数组指针，指向待填入元素的位置
while(left<=mid && right<=high){ //俩个队伍都没走完
if(helper[left]<=helper[right]){
arr[current]=helper[left];
left++;
}else{
arr[current]=helper[right];
right++;
}
current++;
}
while(left<=mid){ //左侧未走完，右侧走完
arr[current]=helper[left];
left++;
current++;
}
while(right<=mid){ //右侧未走完，左侧走完
arr[current]=helper[right];
right++;
current++;
}
}
}