JAVA-快速排序

目录

一、快速排序基本思想

二、快速排序的实现

1.Hoare法找基准值  

2.挖坑法

3.前后指针法(了解)

三、快速排序的优化

1.三数取中法

2.递归到小的子区间时，可以考虑使用插入排序

四、非递归的写法

五、时间空间复杂度

---

一、快速排序基本思想

快速排序是 Hoare 于 1962 年提出的一种二叉树结构的交换排序方法，其基本思想为： 任取待排序元素序列中的某元 素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有 元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止 。

我们此次实现拿数组的第一个元素做为基准值

right找到比tmp小的，left再找到比tmp大的就交换。如果交汇了就放入第一个元素，再把tmp放进来。 right必须先找left后找

把交汇处的下标给par，再分别从par两边重复之前的操作。而且这不就是二叉树吗。那么就适合用递归来处理了

二、快速排序的实现

    public static void quickSort(int[] array) {quick(array,0,array.length-1);}private static void quick(int[] array,int start,int end) {//当start >= end了证明只有一个元素，或者没有左右树了也就不需要排序了if(start >= end) {return;}//按照基准值对array数组的 [start,end]区间中的元素进行划分//并返回当前基准值下标int par = partitionHoare(array,start,end);//遍历左边quick(array,start,par-1);//遍历右边quick(array,par+1,end);}

1.Hoare法找基准值  

从逻辑上已经构造好了，就差具体的操作了：

    /*** Hoare法* @param array* @param left* @param right* @return*/private static int partitionHoare(int[] array, int left,int right) {//用来保存基准值下标int i = left;//记录基准值的值int tmp = array[left];//没交汇就继续循环while (left < right) {//left < right 必须写前面，防止6 7 8 9这种情况//找到最右边小于基准值的值while (left < right && array[right] >= tmp){right--;}//找到左边大于基准值的值while (left < right && array[left] <= tmp) {left++;}//交换swap(array,left,right);}//此时 left 和 right 交汇swap(array,i,left);//返回新的基准值下标return left;}//交换函数private static void swap(int[] array, int i, int j) {int tmp = array[i];array[i] = array[j];array[j] = tmp;}

测试代码：

public static void main(String[] args) {int[] array = {10,9,7,2,3,8,1};Sort.bubbleSort(array);System.out.println(Arrays.toString(array));}

出了刚才的Hoare法可以找基准值下面还有两种方法

2.挖坑法

先把基准值记录一下，再由right找到小于基准值的，然后left找到大于基准值的。两边来回填补。

最后tmp放入交汇处

细心的就会发现，这和Hoare法的数据顺序是不一样的。但也同样达到了效果

画图的时候里面有一些空，其实是保留了原来数据的，但是为了更好的理解就没有保留。但是在代码上原有的数据一定会被覆盖。

代码：

    /*** 挖坑法* @param array* @param left* @param right* @return*/private static int partitionK(int[] array, int left,int right) {//记录第一个坑，做为基准值int tmp = array[left];while (left < right) {//找到最左边比基准值小的while (left < right && array[right] >= tmp) {right--;}//左边小的数据先放入，已经挖好了坑tmparray[left] = array[right];//找到最右边大于基准值的while (left < right && array[left] <= tmp) {left++;}//放入右边的新坑array[right] = array[left];}//left 和 right 交汇，填空array[left] = tmp;return left;}

这是最重要的一种方法，着重掌握

3.前后指针法(了解)

做选择题的时候可能会有。做题顺序： 挖坑法 > Hoare法 > 前后指针法

​/*** 前后指针法 (做为了解)* @param array* @param left* @param right* @return*/private static int partitionPre(int[] array, int left, int right) {int prev = left ;int cur = left+1;while (cur <= right) {if(array[cur] < array[left] && array[++prev] != array[cur]) {swap(array,cur,prev);}cur++;}swap(array,prev,left);return prev;}​

快速排序如果不做优化，数据量大了以后他是很有可能会栈溢出的。

但是计算做了优化也有可能会栈溢出，虽然快速排序是最快的，但耗费内存大也是他的缺点

三、快速排序的优化

1.三数取中法

快排在能取到中间值时，最快。

如果数组是一个有序的，那么就会开辟很多没必要的空间。浪费时间空间

那么三树取中就是：

用left 和 right 与 mid(数组中间下标的值) ，里面选居中的一个。做为基准值，并将他和left换一下

此时3做为基准值

 那么最后基准值就在中间位置

写一个函数找到三个数之间中间的那个数的下标:

//返回的是中间值小标private static int midTreeNum(int[] array,int left,int right) {int mid = (left + right) / 2;if(array[left] < array[right]) {if(array[mid] < array[left]) {return left;}else if(array[right] < array[mid]) {return right;}else {return mid;}}else {if(array[mid] < array[right]) {return right;}else if(array[left] < array[mid]) {return left;}else {return mid;}}}

边看图边看代码，假设array[left] < array[right]   假设array[left] >= array[right]

        public static void quickSort(int[] array) {quick(array,0,array.length-1);}private static void quick(int[] array,int start,int end) {if(start >= end) {return;}//三数取中法int index = midTreeNum(array,start,end);swap(array,index,start);int par = partitionK(array,start,end);quick(array,start,par-1);quick(array,par+1,end);}

结果：

 

2.递归到小的子区间时，可以考虑使用插入排序

我们知道在趋于有序的时候插入排序最快，可以达到O(n)

public static void insertSortRange(int[] array,int left ,int right) {for (int i = left+1; i <= right; i++) {int tmp = array[i];int j = i-1;for (; j >= left; j--) {
//                if(array[j] > tmp) {   不稳定的写法if(array[j] > tmp) {array[j+1] = array[j];}else {//防止第一次array[j]>tmp，从而j--到-1，执行不到这条语句
//                    array[j+1] = tmp;break;}}array[j+1] = tmp;}
}

        public static void quickSort(int[] array) {quick(array,0,array.length-1);}private static void quick(int[] array,int start,int end) {if(start >= end) {return;}//当分出来的,数组越小。递归的次数就越多了，但是趋于有序了就可以用插入排序if(end - start + 1 <= 10) {insertSortRange(array,start,end);return;}//三数取中法int index = midTreeNum(array,start,end);swap(array,index,start);int par = partitionK(array,start,end);quick(array,start,par-1);quick(array,par+1,end);}

四、非递归的写法

public static void quickSortNot(int[] array) {Stack<Integer> stack = new Stack<>();int left = 0;int right = array.length-1;int par = partitionK(array,left,right);if(par > left+1) {stack.push(left);stack.push(par-1);}if(par < right-1) {stack.push(par+1);stack.push(right);}while (!stack.isEmpty()) {right = stack.pop();left = stack.pop();par = partitionK(array,left,right);//保证左边至少有两个元素if(par > left+1) {stack.push(left);stack.push(par-1);}//保证右边至少有两个元素if(par < right-1) {stack.push(par+1);stack.push(right);}}
}

用栈来模拟，用栈后进先出的原理来模拟实现。

快速排序最好还是用递归来实现

五、时间空间复杂度

优化后的

时间复杂度:O(n*log2n)空间复杂度:O(log2n)稳定性:不稳定