public static void quickSort(int[] array){quick(array,0,array.length-1);}public static void quick(int[] array,int start,int end){//大于号 是预防1 2 3 4 5 6,直接没有左树或没有右树if (start >= end){return;}int pivot = partition(array,start,end);quick(array,start,pivot-1);quick(array,pivot+1,end);}//找基准//Hoare版本private static int partition(int[] array,int left,int right){int i = left;int pivot = array[left];while (left < right){while (left < right && array[right] >= pivot){right--;}//right下标的值小于pivotwhile (left < right && array[left] <= pivot){left++;}//left下标的值大于pivotswap(array,left,right);}//循环走完,left和right相遇//交换 和原来的leftswap(array,left,i);//返回基准return left;}

时间复杂度:O(n*logn)

此时间复杂度不是最坏情况下的时间复杂度,最坏情况下是有序的情况下,此时树的高度是n,时间复杂度是O(n^2),空间复杂度也变成了O(n).

空间复杂度:O(logn)

稳定性:不稳定

挖坑法找基准

private static int partition(int[] array,int left,int right){int pivot = array[left];while (left < right){while (left < right && array[right] >= pivot){right--;}array[left] = array[right];while (left < right && array[left] <= pivot){left++;}array[right] = array[left];}array[left] = pivot;//返回基准return left;}

挖坑法是找到合适的值直接交换.

需要注意的是挖坑法和hoare找基准的结果是不一样的但是最终都是有序的.

快速排序优化

当数据有序的时候,快速排序的时间复杂度达到最大,而且空间复杂度也会随之改变.

三数取中法

为了使二叉树的划分尽可能的均匀,我们在left,mid,right三个数中,取出中间大的值,来作为key(left).

比如1 2 3 4 5,如果不采用三数取中法,那么1作为key走下来,left和right在1相遇,基准就是1,此时划分的就是单分支的树;如果采用三数取中,将数组顺序调整为 3 2 1 4 5,3作为key,走下来,left和right在中间位置相遇,将3和1交换,变为 1 2 3 4 5,虽然又变回去了,但是此时的基准在中间位置3的地方,此时二叉树划分的将更加均匀.

public static void quick(int[] array,int start,int end){//大于号 是预防1 2 3 4 5 6,直接没有左树或没有右树if (start >= end){return;}//在找基准之前,进行三数取中的优化,尽量去解决划分不均匀的问题.//在left,mid,right三个数中找到中间大的数字做keyint index = findMidValueOfIndex(array, start, end);swap(array,start,index);int pivot = partitionHoare(array,start,end);quick(array,start,pivot-1);quick(array,pivot+1,end);}//3个数中取中位数private static int findMidValueOfIndex(int[] array,int start,int end){int minIndex = (start+end)/2;if (array[start] > array[end]){if (array[minIndex] > array[start]){return start;}else if (array[minIndex] < array[end]){return end;}else {return minIndex;}}else {if (array[minIndex] > array[end]){return end;}else if (array[minIndex] < array[start]){return start;}else {return minIndex;}}}

我们除了采取这种优化之外,还可以在快速排序递归到小区间的时候,采用插入排序.

因为插入排序在数据趋于有序并且数据量小的时候,排序的速度非常快.

非递归实现快速排序

 public static void quickSort2(int[] array) {Stack<Integer> stack = new Stack<>();int start = 0;int end = array.length-1;int pivot = partition(array,start,end);//1.判断左边是不是有2个元素if(pivot > start+1) {stack.push(start);stack.push(pivot-1);}//2.判断右边是不是有2个元素if(pivot < end-1) {stack.push(pivot+1);stack.push(end);}while (!stack.isEmpty()) {end = stack.pop();start = stack.pop();pivot = partition(array,start,end);//3.判断左边是不是有2个元素if(pivot > start+1) {stack.push(start);stack.push(pivot-1);}//4.判断右边是不是有2个元素if(pivot < end-1) {stack.push(pivot+1);stack.push(end);}}

归并排序

先分解,后合并.

public static void mergeSort1(int[] array) {mergeSortChild(array,0,array.length-1);}private static void mergeSortChild(int[] array,int left,int right) {if(left == right) {return;}int mid = (left+right) / 2;mergeSortChild(array,left,mid);mergeSortChild(array,mid+1,right);//合并merge(array,left,mid,right);}private static void merge(int[] array,int left,int mid,int right) {int s1 = left;int e1 = mid;int s2 = mid+1;int e2 = right;int[] tmpArr = new int[right-left+1];int k = 0;//表示tmpArr 的下标while (s1 <= e1  && s2 <= e2) {if(array[s1] <= array[s2]) {tmpArr[k++] = array[s1++];}else{tmpArr[k++] = array[s2++];}}while (s1 <= e1) {tmpArr[k++] = array[s1++];}while (s2 <= e2) {tmpArr[k++] = array[s2++];}//tmpArr当中 的数据 是right  left 之间有序的数据for (int i = 0; i < k; i++) {array[i+left] = tmpArr[i];}}

时间复杂度:O(n*logn).

空间复杂度:O(n)

稳定性:稳定

非递归的归并排序

 public static void mergeSort(int[] array) {int gap = 1;while (gap < array.length) {for (int i = 0; i < array.length; i += gap*2) {int left = i;int mid = left + gap -1;int right = mid+gap;if(mid >= array.length) {mid = array.length-1;}if(right >= array.length) {right = array.length-1;}merge(array,left,mid,right);}gap *= 2;}}