JAVA-快速排序

目次

一、快速排序基本思想
二、快速排序的实现
1.Hoare法找基准值  
2.挖坑法
3.前后指针法(了解)
三、快速排序的优化
1.三数取中法
2.递归到小的子区间时，可以考虑使用插入排序
四、非递归的写法
五、时间空间复杂度

---

一、快速排序基本思想

   快速排序是  Hoare  于  1962  年提出的一种二叉树布局的互换排序方法，其基本思想为：  任取待排序元素序列中的某元  素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中全部元素均小于基准值，右子序列中全部  元素均大于基准值，然后最左右子序列重复该过程，直到全部元素都排列在相应位置上为止  。        我们此次实现拿数组的第一个元素做为基准值      

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

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

  
二、快速排序的实现

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

复制代码

1.Hoare法找基准值  


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

1.     /**
2.      * Hoare法
3.      * @param array
4.      * @param left
5.      * @param right
6.      * @return
7.      */
8.     private static int partitionHoare(int[] array, int left,int right) {
9.         //用来保存基准值下标
10.         int i = left;
11.         //记录基准值的值
12.         int tmp = array[left];
13.         //没交汇就继续循环
14.         while (left < right) {
15.             //left < right 必须写前面，防止6 7 8 9这种情况
16.             //找到最右边小于基准值的值
17.             while (left < right && array[right] >= tmp){
18.                 right--;
19.             }
20.             //找到左边大于基准值的值
21.             while (left < right && array[left] <= tmp) {
22.                 left++;
23.             }
24.             //交换
25.             swap(array,left,right);
26.         }
27.         //此时 left 和 right 交汇
28.         swap(array,i,left);
29.         
30.         //返回新的基准值下标
31.         return left;
32.     }
34.     //交换函数
35.     private static void swap(int[] array, int i, int j) {
36.         int tmp = array[i];
37.         array[i] = array[j];
38.         array[j] = tmp;
39.     }

复制代码

测试代码：

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

复制代码

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

2.挖坑法

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

仔细的就会发现，这和Hoare法的数据顺序是不一样的。但也同样到达了效果
绘图的时候内里有一些空，其实是保存了原来数据的，但是为了更好的明白就没有保存。但是在代码上原有的数据一定会被覆盖。
代码：

1.     /**
2.      * 挖坑法
3.      * @param array
4.      * @param left
5.      * @param right
6.      * @return
7.      */
8.     private static int partitionK(int[] array, int left,int right) {
9.         //记录第一个坑，做为基准值
10.         int tmp = array[left];
11.         while (left < right) {
12.             //找到最左边比基准值小的
13.             while (left < right && array[right] >= tmp) {
14.                 right--;
15.             }
16.             //左边小的数据先放入，已经挖好了坑tmp
17.             array[left] = array[right];
19.             //找到最右边大于基准值的
20.             while (left < right && array[left] <= tmp) {
21.                 left++;
22.             }
23.             //放入右边的新坑
24.             array[right] = array[left];
25.         }
26.         //left 和 right 交汇，填空
27.         array[left] = tmp;
28.         return left;
29.     }

复制代码

  这是最紧张的一种方法，着重掌握
  
3.前后指针法(了解)

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

1. ​
2.     /**
3.      * 前后指针法 (做为了解)
4.      * @param array
5.      * @param left
6.      * @param right
7.      * @return
8.      */
9.     private static int partitionPre(int[] array, int left, int right) {
10.         int prev = left ;
11.         int cur = left+1;
12.         while (cur <= right) {
13.             if(array[cur] < array[left] && array[++prev] != array[cur]) {
14.                 swap(array,cur,prev);
15.             }
16.             cur++;
17.         }
18.         swap(array,prev,left);
19.         return prev;
20.     }
22. ​

复制代码

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

三、快速排序的优化

1.三数取中法

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

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

那么三树取中就是：
用left 和 right 与 mid(数组中间下标的值) ，内里选居中的一个。做为基准值，并将他和left换一下

此时3做为基准值

 那么最后基准值就在中间位置
写一个函数找到三个数之间中间的谁人数的下标:

1. //返回的是中间值小标
2.     private static int midTreeNum(int[] array,int left,int right) {
3.         int mid = left + right / 2;
5.         if(array[left] < array[right]) {
6.             if(array[mid] < array[left]) {
7.                 return left;
8.             }else if(array[right] < array[mid]) {
9.                 return right;
10.             }else {
11.                 return mid;
12.             }
13.         }else {
14.             if(array[mid] < array[right]) {
15.                 return right;
16.             }else if(array[left] < array[mid]) {
17.                 return left;
18.             }else {
19.                 return mid;
20.             }
21.         }
22.     }

复制代码

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

1.         public static void quickSort(int[] array) {
2.             quick(array,0,array.length-1);
3.         }
5.         private static void quick(int[] array,int start,int end) {
6.             if(start >= end) {
7.                 return;
8.             }
9.       
10.             //三数取中法
11.             int index = midTreeNum(array,start,end);
12.             swap(array,index,start);
14.             int par = partitionK(array,start,end);
16.             quick(array,start,par-1);
17.             quick(array,par+1,end);
19.         }

复制代码

结果：
 

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

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

1. public static void insertSortRange(int[] array,int left ,int right) {
2.         for (int i = left+1; i <= right; i++) {
3.             int tmp = array[i];
4.             int j = i-1;
5.             for (; j >= left; j--) {
6. //                if(array[j] > tmp) {   不稳定的写法
7.                 if(array[j] > tmp) {
8.                     array[j+1] = array[j];
9.                 }else {
10.                     //防止第一次array[j]>tmp，从而j--到-1，执行不到这条语句
11. //                    array[j+1] = tmp;
12.                     break;
13.                 }
14.             }
15.             array[j+1] = tmp;
16.         }
17. }

复制代码

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

复制代码

四、非递归的写法

1. public static void quickSortNot(int[] array) {
2.         Stack<Integer> stack = new Stack<>();
3.         int left = 0;
4.         int right = array.length-1;
5.         int par = partitionK(array,left,right);
7.         if(par > left+1) {
8.             stack.push(left);
9.             stack.push(par-1);
10.         }
11.         if(par < right-1) {
12.             stack.push(par+1);
13.             stack.push(right);
14.         }
15.         while (!stack.isEmpty()) {
16.             right = stack.pop();
17.             left = stack.pop();
18.             par = partitionK(array,left,right);
20.             //保证左边至少有两个元素
21.             if(par > left+1) {
22.                 stack.push(left);
23.                 stack.push(par-1);
24.             }
25.             //保证右边至少有两个元素
26.             if(par < right-1) {
27.                 stack.push(par+1);
28.                 stack.push(right);
29.             }
30.         }
31. }

复制代码

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

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

五、时间空间复杂度

优化后的
  

1. <u><strong>时间复杂度:O(n*log2n)
3. 空间复杂度:O(log2n)
5. 稳定性:不稳定</strong></u>

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。