快排的java实现方式，用java代码来实现快排

 1. 快排的思想

　　通过一趟排序将要排序的数据分割成独立的两部分，前一部分的所有数据都要小于后一部分的所有数据，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据的有序性。

 

2. 快排实现的核心步骤 

　　①找基准点：一般是数组的第一个元素来充当； 

　　②right：从数组的最后一个元素开始，从右往左，直到找到小于基准点的元素；每次都要right比left先走； 

　　③left：从数组的第一个元素开始，从左往右，直到找到大于基准点的元素；

　　④交换 left 和 right 所在位置的两个元素；

　　⑥right 继续往左走，找到小于基准点的元素；left 继续往右走，找到大于基准点的元素；然后 left 和 right 再做交换；循环往复，直到两人相遇；

　　⑦将相遇点所在位置的元素和基准点所在位置的元素做交换，基准点到了中间位置（此时基准点左边的元素全都小于基准点右边的元素）；

　　⑧【递归】将基准点左边的所有元素当成一个数组，重复①~⑦步骤；基准点右边的所有元素也是如此；

 

3. 快排的java代码实现

 1 public class A01QuickSort {
 2 　　public static void main(String[] args) {
 3 　　　　A01QuickSort quickSort = new A01QuickSort();
 5 
 6 　　　　// 测试快排的效率：
 7 　　　　//    int number = 1000000;
 8 　　　　//    int[] array = new int[number];
 9 　　　　//    for (int i = 0; i < array.length; i++) {
10 　　　　//    array[i] = new Random().nextInt(number);
11 　　　　//    }
12 
13 　　　　//配合后面的元素输出，测试快排是否排序准确：
14 　　　　int[] array = new int[] {181,181,187,181};
15 　　　　System.out.println("数组准备完毕~");
16 
17 　　　　long start = System.currentTimeMillis();
18 　　　　quickSort.quickSort(array, 0, array.length - 1);
19 　　　　long end = System.currentTimeMillis();
20 　　　　System.out.println("quickSort 用时：" + (end - start));// 测试结果： 元素为5万个时：11毫秒。50万：66毫秒。100万：136毫秒
21 
22 　　　　//遍历输出数组元素：
23 　　　　quickSort.traverseArray(array);
24 　　}
25 
26 　　/**
27 　　* 快排的实现
28 　　* @param target
29 　　* @param left
30 　　* @param right
31 　　*/
32 　　public void quickSort(int[] target, int left, int right) {
33 　　　　if (left >= right) {
34 　　　　　　return;
35 　　　　}
36 　　　　int pivot = target[left];// 基准点
37 　　　　int temp;
38 　　　　int i = left;
39 　　　　int j = right;//为什么要声明i和j，因为后面做迭代的时候还需要用到最初的left和right
40 　　　　while (i < j) {//验证array数组至少有2个元素，才要做排序
41 　　　　　　/**
42 　　　　　　* 提问：
43 　　　　　　* 为什么是 while里的判断，为什么是 “target[j] >= pivot”，而不是“target[j] > pivot”？？？
44 　　　　　　* 答: 数组[181,181,187,181]，分别用上面两种while去测试：
45 　　　　　　*    如果是">="时，因为 181 >= 181 成立，所以right就会从右往左移；
46 　　　　　　*    如果是">"时，因为 181 > 181 成立，所以right就不会左移。
47 　　　　　　* 重点！！！right或left，必须有一方得是移动的！！！否则程序就会进入死循环！！！
48 　　　　　　*/
49 　　　　　　// 如果right一直都大于或等于pivot，则继续走，直到找到比pivot小的：
50 　　　　　　while (target[j] >= pivot && i < j) {
51 　　　　　　　　j--;
52 　　　　　　}
53 　　　　　　// 如果left一直都小于等于pivot，则继续走，直到找到比pivot大的：
54 　　　　　　while (target[i] <= pivot && i < j) {
55 　　　　　　　　i++;
56 　　　　　　}
57 　　　　　　// 此时right < pivot, left > pivot，将i和j做交换：
58 　　　　　　if (i < j) {//这里做判断是为了right到了left位置时，不用再将执行下面这三行代码了：
59 　　　　　　　　temp = target[i];
60 　　　　　　　　target[i] = target[j];
61 　　　　　　　　target[j] = temp;
62 　　　　　　}
63 　　　　}
64 　　　　// left和right相遇了：
65 　　　　// ①将相遇点的元素和pivot做交换：
66 　　　　target[left] = target[j];
67 　　　　target[j] = pivot;
68 　　　　// ②基准点两边的元素的分别再做排序：
69 　　　　quickSort(target, left, j - 1);
70 　　　　quickSort(target, j + 1, right);
71 　　}
72 
73 　　//遍历数组
74 　　public void traverseArray(int[] array) {
75 　　　　for(int element : array) {
76 　　　　　　System.out.println(element);
77 　　　　}
78 　　}
79 }

 

4. 快排的时间复杂度：O（n * log（n)) 

　　快排的时间复杂度分析：快排的时间复杂度分析（含图解）

 

原文链接:https://www.cnblogs.com/laipimei/p/11134210.html
如有疑问请与原作者联系

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有