0%

快速排序

发表于 分类于

文章字数：916,阅读全文大约需要3分钟

快速排序的思想就是把第一个数作为基数，比基数小的放到前面，比基数大或等于的放到基数后面。然后再对基数以前和基数以后的部分分别进行前面的操作，直到基数前面和基数后面都只有一个数时（左侧游标和右侧游标相遇）

时间复杂度O(N*logN)

具体方案

调用：

  1. 写一个用于整理区域的方法
  2. 递归调用，整理所有的部分（整理当前，的到基数位置，递归整理基数之前的区域，递归整理基数之后的区域）

整理方法：

  1. 选第一位为基数
  2. 右游标从前找比基数小的数，放到左游标处(左右游标的位置上都没有值，因为一旦选中某个元素，就意味着这个元素不符合要求，需要放到另一边)
  3. 左游标向后找比基数大的数，放到右游标的位置。
  4. 循环2，3操作，知道左右游标相遇，这个位置就是基数应该放在的地方
  5. 返回基数的位置，方便上面的递归调用时判断基数前后区域

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
/**
 * @author colin.cheng
 * @version V1.0
 */
public class midTest {
    public int arrayTheList(int[] arr,int l,int r){
        //选中第一位作为基数
        int x = arr[l];
        //左和右的游标遇到时结束
        while (l<r){
            //右游标移动到小于基数的值上
            while(l<r&&arr[r]>=x){
                r--;
            }
            //放到左边游标的位置上（相当于从右边找不符合要求的数，全部放到左边）
            if(l<r){
                arr[l]=arr[r];
            }

            //左边找不符合要求的数，放到右边
            while(l<r&&arr[l]<=x){
                l++;
            }
            if(l<r){
                arr[r]=arr[l];
            }
        }
        //当左边游标和右边游标相同时这个位置填充基数
        arr[l]=x;
        //返回基数位置
        return l;
    }

    void quick_sort(int[]arr,int l,int r){
        //递归的结束条件
        if(l<r){
            //1.整理当前区域，返回基数位置
            int i = arrayTheList(arr,l,r);
            //2.整理基数左边的区域
            quick_sort(arr,l,i-1);
            //3.整理基数右边的区域
            quick_sort(arr,i+1,r);
        }
    }

        public static void main(String[] args) {
        int[] arr={21,35,2,6,4,8,2,4,98,4,95,1,60,5,7,2,2,0,2,14,0,123,3,654,484,34,5235,68,455,834,568,3458,56,31,69,55,349,582,1,97,35,95,84,8492,2,546,475,354};
        midTest t = new midTest();
        //调用排序
        t.quick_sort(arr,0,arr.length-1);
        System.out.println("--------------");
        //输出结果
        int index=0;
        for(int i:arr){
            System.out.print(i);
            index++;
            if(index!=arr.length){
                System.out.print(",");
            }
        }
    }
}

#输出结果

1
0,0,1,1,2,2,2,2,2,2,3,4,4,4,5,6,7,8,14,21,31,34,35,35,55,56,60,68,69,84,95,95,97,98,123,349,354,455,475,484,546,568,582,654,834,3458,5235,8492

基于栈的快速排序

上面的使用的是递归，递归如果深度过深可能会造成jvm栈空间不足。所以修改了一下调用的方法，改为使用先进后出的数据结构stack,和递归效果一样，但是每次的函数执行完就退出，不会像递归那样不关闭

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
import java.util.Stack;

/**
 * @author colin.cheng
 * @date
 */
public class demo {

    public static Stack<Node> stack = new Stack();

    public static void main(String[] args) {

        int[] values = {1, 23, 51, 24, 124, 15, 124, 15123, 114, 4, 564, 42, 5, 434, 3434, 344, 444, 2, 5, 90, 7, 7, 8,
            54, 3, 4, 65, 43, 34, 5, 743, 24, 514, 5, 2};
        sortArray(values, 0, values.length - 1);
        for (int v : values) {
            System.out.print(v + ",");
        }
    }

    /**
     * 调用区域排序，并把基准点左右区域的排序任务入栈
     * 
     * @param args
     * @param l
     * @param r
     */
    static void dealArrayAndAddToStack(int[] args, int l, int r) {
        int baseIndex = sort(args, l, r);

        if (l < baseIndex - 1) {
            Node leftNode = new Node(l, baseIndex - 1);
            stack.push(leftNode);
        }

        if (baseIndex + 1 < r) {
            Node rightNode = new Node(baseIndex + 1, r);
            stack.push(rightNode);
        }
    }

    /**
     * 排序调度
     * 
     * @param args
     * @param l
     * @param r
     */
    public static void sortArray(int[] args, int l, int r) {
        dealArrayAndAddToStack(args, l, r);
        // 任务出栈
        while (!stack.empty()) {
            Node currentNode = stack.pop();
            dealArrayAndAddToStack(args, currentNode.left, currentNode.right);
        }
    }

    /**
     * 区域排序
     * 
     * @param args
     * @param l
     * @param r
     * @return
     */
    public static int sort(int[] args, int l, int r) {
        int base = args[l];

        while (l < r) {

            while (l < r && args[r] >= base) {
                r--;
            }

            if (l < r) {
                args[l] = args[r];
            }

            while (l < r && args[l] <= base) {
                l++;
            }

            if (l < r) {
                args[r] = args[l];
            }

        }
        args[l] = base;
        return l;
    }

    static class Node {
        public int left;
        public int right;

        public Node(int left, int right) {
            this.left = left;
            this.right = right;
        }
    }
}

简易版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public void sort(int[] nums, int lIndex, int rIndex) {
    if (lIndex < rIndex) {
        int l = lIndex, r = rIndex, x = nums[lIndex];
        while (l < r) {
            while (l < r && nums[r] > x) {
                r--;
            }
            if (l < r) {
                nums[l] = nums[r];
                l++;
            }
            while (l < r && nums[l] < x) {
                l++;
            }
            if (l < r) {
                nums[r] = nums[l];
                r--;
            }
        }
        nums[l] = x;
        sort(nums, lIndex, l - 1);
        sort(nums, l + 1, rIndex);
    }
}