快速排序的相关算法题（java）

版权声明：本文为博主原创文章，未经博主允许不得转载。 https://cloud.tencent.com/developer/article/1341937

快速排序的相关算法题（java）

关于二分查找的，可以参考我的这篇博客二分查找的相关算法题

关于归并排序的的，可以参考我的这篇博客归并排序 递归版和非递归版的实现（java）

关于快速排序的，可以参考我的这篇博客 快速排序的相关算法题（java）

转载请注明原博客地址：

源码下载地址：

最近在做各个大公司的笔试题 ，比如阿里，腾讯，cvte等等，经常会遇到关于快速排序的各种算法题，包括时间复杂度，空间复杂度的分析与计算等等，于是本人查阅了相关的资料，先总结如下

本篇博客主要讲解一下三点

1. 快排是怎样实现的？
2. 怎样用最快的速度找出数组中出现次数超过一半的数字
3. 要求找出数组中最小的第k个数，时间复杂度最低

快排是怎样实现的？

举例说明一下吧，这个可能不是太好理解。假设要排序的序列为 

2 2 4 9 3 6 7 1 5

1. 首先用2当作基准，使用i，j两个指针分别从两边进行扫描，把比2小的元素和比2大的元素分开。
2. 首先比较2和5，5比2大，j左移 2 2 4 9 3 6 7 1 5 比较2和1，1小于2，所以把1放在2的位置，即 2 1 4 9 3 6 7 1 5 ；
3. 接着比较2和4，4大于2，因此将4移动到后面。即2 1 4 9 3 6 7 4 5 比较2和7，2和6，2和3，2和9，全部大于2，满足条件，因此不变
4. 4.经过第一轮的快速排序，元素变为下面的样子

1 2 4 9 3 6 7 5

之后，在把2左边的元素进行快排，由于只有一个元素，因此快排结束。右边进行快排，递归进行，最终生成最后的结果。

下面我们来看一下源码是怎样实现的

1. 简单来说就是先找出一个索引，左边的数都比他小，右边的数都比他大 ，接着利用递归排列左边和右边的数，知道low>=high

private static void qSort(int[] data, int low, int high) {
    int pivot;
    if (low < high) {
        pivot = partition(data, low, high);
        qSort(data, 0, pivot - 1);
        qSort(data, pivot + 1, high);
    }
}

1. 下面我们来看一下partition函数式怎样实现的

1. private static int partition(int[] data, int low, int high) {
2. int pivotKey;
3. `pivotKey = data[low];`
4. // 将大于基准点的值得数放到后面
5. while (low < high) {
6. while (low < high && data[high] >= pivotKey) {//
7. `high--;`
8. }
9. ArrayUtils.exchangeElements(data, low, high);
10. // 将小于基准点的值得数放到前面
11. while (low < high && data[low] <= pivotKey) {
12. `low++;`
13. }
14. ArrayUtils.exchangeElements(data, low, high);
15. }
16. // 返回基准点的索引
17. return low;
18. }

到此快速排序的分析为止

2）数组中第K个 最小的数字

一、问题描述

给定一个数组，数组中的数据无序，在一个数组中找出其第k个最小的数，例如对于数组x，x = {3，2，1，4，5，6}，则其第2个最小的数为2。

二、解题思路

本算法跟快排的思想相似，首先在数组中选取一个数centre作为枢纽，将比centre小的数，放到centre的前面将比centre大的数，放到centre的后面。如果此时centre的位置刚好为k，则centre为第k个最小的数；如果此时centre的位置比k前，则第k个最小数一定在centre后面，递归地在其右边寻找；如果此时centre的位置比k后，则第k个最小数一定在centre后面，递归地在其左边寻找。

三、代码

1. package com.xujun.quicksort;
2. ​
3. import java.util.Collections;
4. ​
5. public class MinIndex {
6. ​
7. static int[] a = new int[] { 20, 9, 3, 5, 26, 100, 8, -1, 7, 50, -5, 20, -1 };
8. ​
9. public static void main(String[] args) {
10. ​
11. System.out.println("before sort");
12. ArrayUtils.printArray(a);
13. int k=8;
14. int pivot = findMinIndexInArray(a, k);
15. System.out.println("after sort");
16. ArrayUtils.printArray(a);
17. System.out.println("数组中最小的第"+k+"个数是 " + a[pivot]);
18. }
19. ​
20. private static int findMinIndexInArray(int[] data, int k) {
21. if (data == null || data.length < k) {
22. return -1;
23. }
24. int start = 0;
25. int end = data.length - 1;
26. int pivot = partition(data, start, end);
27. while (pivot != k - 1) {
28. ​
29. if (pivot < k - 1) {
30. `start = pivot +` `1;`
31. `pivot = partition(data, start, end);`
32. } else {
33. `end = pivot -` `1;`
34. `pivot = partition(data, start, end);`
35. }
36. }
37. ​
38. ​
39. return pivot;
40. ​
41. }
42. ​
43. private static int partition(int[] data, int low, int high) {
44. int pivotKey;
45. /*
46. `* pivotKey = data[low];// 选取low作为基准点，pivotKey为基准点的值`
47. `*/`
48. ​
49. int middle = low + (high - low) / 2;
50. if (data[low] > data[high]) {// 较大的数存在high中
51. ArrayUtils.exchangeElements(data, low, high);
52. }
53. if (data[middle] > data[high]) {
54. ArrayUtils.exchangeElements(data, middle, high);
55. }
56. if (data[middle] > data[low]) {
57. ArrayUtils.exchangeElements(data, middle, low);
58. }
59. `pivotKey = data[low];// 选取low作为基准点，pivotKey为基准点的值`
60. // 将大于基准点的值得数放到后面
61. while (low < high) {
62. while (low < high && data[high] >= pivotKey) {//
63. `high--;`
64. }
65. `data[low]` `= data[high];`
66. // 将小于基准点的值得数放到前面
67. while (low < high && data[low] <= pivotKey) {
68. `low++;`
69. }
70. `data[high]` `= data[low];`
71. }
72. `data[low]` `= pivotKey;`
73. // 返回基准点的索引
74. return low;
75. }
76. ​
77. }

3）数组中出现次数超过一半的数字

一、问题描述

给定一个数组，找出数组中元素出现次数超过数组长度一半的元素 

如数组： 

4, 3, 2, 1, 1, 1, 1, 1, 1, 0  

其中超过一半的元素就是 1

二、解题思路

1）本题同样可以医用快速排序的思想来做，如果一个数字出现次数超过一般，那么排好序的数组的中间数肯定就是出现次数超过一半的数字 

2）考虑异常情况下，出现次数没有超过一半 

遍历数组，检查一下

三、代码

1. package com.xujun.quicksort;
2. ​
3. import java.util.Collections;
4. ​
5. public class MoreThanHalf {
6. ​
7. static int[] a = new int[] { 20, 9, 3, 5, 10,10,10,10,10 };
8. ​
9. public static void main(String[] args) {
10. ​
11. System.out.println("before sort");
12. ArrayUtils.printArray(a);
13. int k = 8;
14. int pivot = findMoreHalfInArray(a);
15. int target = a[pivot];
16. boolean checkIsMoreThanHalf = checkIsMoreThanHalf(a, target);
17. if(checkIsMoreThanHalf){
18. System.out.println("after sort");
19. ArrayUtils.printArray(a);
20. ​
21. System.out.println("超过一般的数是="+target);
22. }else{
23. System.out.println("没有超过一般的数字");
24. }
25. ​
26. }
27. ​
28. private static boolean checkIsMoreThanHalf(int[] data, int target) {
29. int half=data.length/2;
30. int count=0;
31. for(int i=0;i<data.length;i++){
32. if(data[i]==target){
33. `count++;`
34. }
35. }
36. return count>=half?true:false;
37. ​
38. }
39. ​
40. private static int findMoreHalfInArray(int[] data) {
41. if (data == null || data.length <= 0) {
42. return -1;
43. }
44. int start = 0;
45. int end = data.length - 1;
46. int half = data.length / 2;
47. int pivot = partition(data, start, end);
48. while (pivot != half - 1) {
49. ​
50. if (pivot < half - 1) {// 枢轴在一半的 左边
51. `start = pivot +` `1;`
52. `pivot = partition(data, start, end);`
53. } else {// 枢轴在一半（中间点）的右边
54. `end = half -` `1;`
55. `pivot = partition(data, start, end);`
56. }
57. }
58. ​
59. return pivot;
60. ​
61. }
62. ​
63. private static int partition(int[] data, int low, int high) {
64. int pivotKey;
65. /*
66. `* pivotKey = data[low];// 选取low作为基准点，pivotKey为基准点的值`
67. `*/`
68. ​
69. int middle = low + (high - low) / 2;
70. if (data[low] > data[high]) {// 较大的数存在high中
71. ArrayUtils.exchangeElements(data, low, high);
72. }
73. if (data[middle] > data[high]) {
74. ArrayUtils.exchangeElements(data, middle, high);
75. }
76. if (data[middle] > data[low]) {
77. ArrayUtils.exchangeElements(data, middle, low);
78. }
79. `pivotKey = data[low];// 选取low作为基准点，pivotKey为基准点的值`
80. // 将大于基准点的值得数放到后面
81. while (low < high) {
82. while (low < high && data[high] >= pivotKey) {//
83. `high--;`
84. }
85. `data[low]` `= data[high];`
86. // 将小于基准点的值得数放到前面
87. while (low < high && data[low] <= pivotKey) {
88. `low++;`
89. }
90. `data[high]` `= data[low];`
91. }
92. `data[low]` `= pivotKey;`
93. // 返回基准点的索引
94. return low;
95. }
96. ​
97. }

关于二分查找的，可以参考我的这篇博客二分查找的相关算法题

关于归并排序的的，可以参考我的这篇博客归并排序 递归版和非递归版的实现（java）

关于快速排序的，可以参考我的这篇博客 快速排序的相关算法题（java）

转载请注明原博客地址：

源码下载地址：