快速排序：
画图画的丑，拿百度百科的勉强用着。
快速排序思想：
- 在初始数组中选出一个基数，将数组分为3个区间。[小于基数的一个区间]，[等于基数的一个区间]，[大于基数的一个区间]。当大于区或小于区数量大于1时，在区间内重新选基数，重新进行分区（重选基数，重新分区），它的平均时间复杂度为O(NlogN)。最坏的情况下它的时间复杂度会跟冒泡排序一样O(N^)
快速排序实现：
/**
* fileName:FastSort
* description:
* author:hcq
* createTime:2019-04-12 10:01
*/
public class FastSort {
public static void main(String[] args) {
int[] arr={5,3,5,6,2,7,8,9,17,0,1,-2,-8};
Arrays.stream(arr).forEach(v -> {
System.out.println(v);
});
System.out.println("排序后--------");
sort(arr,0,arr.length-1);
Arrays.stream(arr).forEach(v -> {
System.out.println(v);
});
}
/**
* 将arr数组中[begin,end]之间的元素进行排序
* @param arr
* 需要排序的数组
* @param begin
* 需要排序开始位置
* @param end
* 需要排序的结束位置
*/
static void sort(int[] arr,int begin,int end){
//定义基准
int sta=arr[begin]; //535627
//定义小于区边界
int min=-1;
//定义大于区边界
int max=end+1;
//定义指针位置
int point=0;
//定义最小区数据量
int mincount=0;
int maxcount=0;
while(point<max){
if(arr[point]>sta){
//当前前指针位置与大于区左边第一个交换
int tmp=arr[point];
arr[point]=arr[max-1];
arr[max-1]=tmp;
//指针位置不变
max--;//大于区扩大
maxcount++;//大于区数据量+1
}else if(arr[point]<sta){
//当前指针位置与小于区右第一个位置交换数据
int tmp=arr[point];
arr[point]=arr[min+1];
arr[min+1]=tmp;
min++;//小于区向右扩大一位
point++;//指针右移
mincount++;//小于区数量+1
}else{
point++;
}
}
if(mincount>1){//最小区数据量大于等于2
sort(arr,0,min);
}
if(maxcount>1){//最大去数据量大于等于2
sort(arr,max,end);
}
}
}
归并排序：
感谢百度百科。。。。。
归并排序思想： 归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
归并排序的实现：
public class mergeSort {
public static void main(String[] args) {
int[] arr={0,1,2,8,7,9,4,5,6,7,11,12,13,14,15,0,2};
mergeSort(arr,0,arr.length-1);
for (int i : arr) {
System.out.println(i);
}
}
/**
* 将数组的[left,right]之间的元素进行排序
* @param arr
* 待排序数组
* @param left
* 从left处开始排序
* @param right
* 到right处排序结束
*/
static void mergeSort(int[] arr,int left,int right){
if(left<right){
int mid=(left+right)/2;
//归并排序左边数组
mergeSort(arr,left,mid);
//归并排序右边数组
mergeSort(arr,mid+1,right);
merge(arr,left,mid,right);
}
}
/**
* 将两个有序的子数组归并为一个整体有序的数组
* @param arr
* 原数组
* @param left
* 左边子数组开始位置
* @param center
* 左边子数组结束位置[右边子数组开始位置]
* @param right
* 右边子数组结束位置
*/
static void merge(int[] arr,int left,int center,int right){
//定义临时数组
int[] newArr=new int[right-left+1];
//定义两个指针
int leftPoint=left;
int rightPoint=center+1;
//定义复制位置
int tmp=0;
//比较两个子数组，将排序的结果放入临时数组
while(leftPoint<=center && rightPoint<=right){
if(arr[leftPoint]<=arr[rightPoint]){
newArr[tmp]=arr[leftPoint];//将值复制到新数组中
leftPoint++;//指针向右移动
}else{
newArr[tmp]=arr[rightPoint];//将值复制到新数组中
rightPoint++;//指针向右移动
}
tmp++;//移动新的复制位置
}
//将剩余数据复制到新数组中。
while(leftPoint<=center){//左边数据未复制完毕
newArr[tmp]=arr[leftPoint];//将值复制到新数组中
leftPoint++;//指针向右移动
tmp++;
}
while(rightPoint<=right){//右边数据未复制完毕
newArr[tmp]=arr[rightPoint];//将值复制到新数组中
rightPoint++;//指针向右移动
tmp++;
}
//更新原数组
for(int i=0;i<newArr.length;i++){
arr[left++]=newArr[i];
}
}
}
