（一）快速排序
第一步：选择轴值，选择策略
第二步：将待排序序列划分为两个子序列l和r，使得l中的所有记录都小于等于轴值，而r中的所有记录都大于轴值，也就是关键的划分算法。
第三步：对子序列l和r递归快速排序。
class solution {
//快速排序
public int[] sortarray(int[] nums) {
if(nums==null ||nums.length<2)
return nums;
quicksort(nums,0,nums.length-1);
return nums;
}
public void quicksort(int[] nums,int low,int high){
if(low>=high)
return;
int index=partition(nums,low,high);
quicksort(nums,low,index-1);
quicksort(nums,index 1,high);
}
public int partition(int[] nums,int low,int high){
int i=low,j=high;
int temp=nums[low]; //轴值选择最左边的一个
while(i=temp)
j--;
if(i
（二）归并排序
二路归并：
class solution {
//归并排序
public int[] sortarray(int[] nums) {
if(nums==null && nums.length<2)
return nums;
mergesort(nums,0,nums.length-1);
return nums;
}
public void mergesort(int[] nums,int low,int high){
if(low>=high)
return ;
int mid=low (high-low)/2;
mergesort(nums,low,mid);
mergesort(nums,mid 1,high);
merge(nums,low,mid,high);
}
public void merge(int[] nums, int low,int mid,int high){
int[] temp=new int[high-low 1];
int i=low,j=mid 1,k=0;
while(i<=mid && j<=high){
if(nums[i]<=nums[j])
temp[k ]=nums[i ];
else
temp[k ]=nums[j ];
}
while(i<=mid)
temp[k ]=nums[i ];
while(j<=high)
temp[k ]=nums[j ];
for(int t=0;t
（三）堆排序
堆：
一个关键字序列｛k0，k1，…，kn-1｝，当满足条件（1）或（2）时就称为堆。
(1) ki ≤k2i 1 或 (2) ki ≥k2i 1
ki ≤k2i 2 ki ≥k2i 2
满足（1）的序列为最小堆（小顶堆）。
满足（2）的序列为最大堆（大顶堆）。
筛选法：
堆排序：
class solution {
//堆排序，o(nlogn)
public int[] sortarray(int[] nums) {
buildheap(nums); //建立初始堆
for(int i=nums.length-1;i>=0;i--){
//交换
int temp=nums[0];
nums[0]=nums[i];
nums[i]=temp;
//重新构建大顶堆，0下筛
heapadjustdown(nums,i,0);
}
return nums;
}
public void buildheap(int[] nums){ //建堆
for(int i=nums.length/2-1;i>=0;i--)
heapadjustdown(nums,nums.length,i);
}
//下筛算法，时间复杂度o(nlogn)
public void heapadjustdown(int[] nums, int n, int h){ //筛选算法，下筛,将nums[h]拉下来
int i=h,temp=nums[h]; //标记父结点
int j=2*i 1; //左孩子
while(jnums[j])
j=j 1; //j为孩子中的较大者
if(temp>nums[j]) //满足大顶堆
break;
else{
nums[i]=nums[j];
i=j;
j=2*i 1;
}
}
nums[i]=temp;
}
}