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

2019-08-16 09:47:05来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

快排的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
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:javaweb各种框架组合案例(七):springboot+jdbcTemplete+通用dao

下一篇:你有对象吗?没有的话就new一个呗!