快速排序：
画图画的丑，拿百度百科的勉强用着。
快速排序思想：
- 在初始数组中选出一个基数，将数组分为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]; } } }
