排序(7) 快速排序

发表于 | 分类于 | 阅读次数:

快速排序的基本思想：通过一趟排序将待排数列分隔成独立的两部分，其中一部分数列的关键字均比另一部分的关键字小，则可分别对这两部分数列继续进行排序，以达到整个序列有序。 其中，最重要的partition主要有两种方法： 1)指针交换法。先把选定为pivot的元素放到最后，然后设定指针low和指针high，low指针右移，high指针左移，当两个指针相撞后停止移动。期间如果符合交换条件，两元素交换。最后把pivot元素放到中间。 2)挖坑法。类似冒泡排序的思路，把比pivot大的元素“往下沉”，把比pivot小的元素“往上浮”。

快速排序

思想

快速排序是从冒泡排序演变而来的算法，但是使用了 分治法，比冒泡排序要高效得多，所以叫快速排序。

同冒泡排序一样，快速排序也属于交换排序，通过元素之间的比较和交换位置来达到排序的目的。

不同的是，冒泡排序在每一轮只把一个元素冒泡到数列的一端，而快速排序 在每一轮挑选一个基准元素，并让其他比它大的元素移动到数列一边，比它小的元素移动到数列的另一边，从而把数列拆解成了两个部分。
这种思路就叫做分治法。

在分治法的思想下，原数列在每一轮被拆成两部分，每一部分在下一轮又分别被拆成两部分，直到不可再分为止。

基准元素的选择：最简单的方式是选择数列的第一个元素。
但是假如有一个原本逆序的数列，期望排序成顺序数列，这样数列每一轮仅仅确定了基准元素的位置。 第一个元素要么是最小值，要么是最大值，根本无法发挥分治法的优势。 在这种极端情况下，快速排序需要进行n轮，时间复杂度退化成了O(n^2)。

如何避免上述情况的发生，最简单的方法，不选择数列的第一个元素，而是随机选择一个元素作为基准元素。 这样一来，即使在数列完全逆序的情况下，也可以有效地将数列分成两部分。当然，即使是随机选择基准元素，每一次也有极小的几率选到数列的最大值或最小值，同样会影响到分治的效果。

快速排序是目前被认为最好的一种内部排序方法。快速排序算法处理的最好情况指每次都是将待排序数列划分为均匀的两部分，通常认为快速排序的平均时间复杂度是O(nlogn)。

但是，快速排序的最差情况就是基本逆序或者基本有序的情况，那么此时快速排序将蜕化成冒泡排序，其时间复杂度为O(n^2)

元素的移动

选定了基准元素，要做的就是把其他元素当中小于基准元素的都移动到基准元素一边，大于基准元素的都移动到基准元素另一边。
有两种方法：

  1. 挖坑法
  2. 指针交换法

快排（挖坑法）

快速排序挖坑法
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
public class QuickSort {
    public static void quickSort(int[] arr, int startIndex, int endIndex) {
        //递归结束条件
        if (startIndex >= endIndex) {
            return;
        }
        // 得到基准元素位置
        int pivotIndex = partition(arr, startIndex, endIndex);

        // 用分治法递归数列两部分
        quickSort(arr, startIndex, pivotIndex - 1);
        quickSort(arr, startIndex + 1, endIndex);
    }
    private static int partition(int[] arr, int startIndex, int endIndex) {
        // 取第一个位置的元素作为基准元素
        int pivot = arr[startIndex];
        int left = startIndex;
        int right = endIndex;

        // 坑的位置，初始等于pivot的位置
        int index = startIndex;

        // 大循环左右指针重合或者指针交换时结束
        while (right >= left) {
            // right指针从右向左进行比较
            while (right >= left) {
                if (arr[right] < pivot) {
                    arr[left] = arr[right];
                    index = right;
                    left++;
                    break;
                }
                right--;
            }
            //left指针从左向右进行比较
            while (right >= left) {
                if (arr[left] > pivot) {
                    arr[right] = arr[left];
                    index = left;
                    right--;
                    break;
                }
                left++;
            }
        }
        arr[index] = pivot;
        return index;
    }

    public static void main(String[] args) {
        int[] arr = { 4, 7, 6, 5, 3, 2, 8, 1 };
        quickSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }
}

指针交换法代码实现

和挖坑法相比，指针交换法在partition方法中进行的元素交换次数更少。

对于数列 {4, 7, 6, 5, 3, 2, 8, 1 }

由于left一开始指向的是基准元素，判断肯定相等，所以left右移一位。

进入第四次循环，right移动到元素3停止，这时候请注意，left和right指针已经重合在了一起。

当left和right指针重合之时，我们让pivot元素和left与right重合点的元素进行交换。此时数列左边的元素都小于4，数列右边的元素都大于4，这一轮交换终告结束。

快速排序指针交换法
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
public class QuickSort {
    public static quickSort(int[] arr, int startIndex, int endIndex) {
        if (startIndex >= endIndex) {
            return;
        }
        // 得到基准信息
        int pivotIndex = partition(arr, startIndex, endIndex);
        //根据基准元素，分成两部分进行递归
        quickSort(arr, startIndex, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, endIndex);
    }
    private static int partition(int[] arr, int startIndex, int endIndex) {
        // 取第一个元素作为基准元素
        int pivot = arr[startIndex];
        int left = startIndex;
        int right = endIndex;

        while (left != right) {
            // 控制right指针比较并左移
            while (left < right && arr[right] > pivot) {
                right--;
            }
            // 控制left指针比较并左移
            while (left < right && arr[left] <= pivot) {
                left++;
            }
            // 交换left和right指向的元素
            if (left < right) {
                int tmp = arr[left];
                arr[left] = arr[right];
                arr[right] = tmp;
            }
        }
        // pivot和指针重合交换
        int tmp = arr[left];
        arr[left] = arr[startIndex];
        arr[startIndex] = tmp;

        return left;
    }

    public static void main(String[] args) {
        int[] arr = { 4, 7, 6, 5, 3, 2, 8, 1 };
        quickSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }
}

partition函数的单边循环法

无论是挖坑法还是指针交换法，都是一层循环内嵌一层循环，从数组的两边交替遍历元素，代码不够简洁。
单边循环法只从数组的一边对元素进行遍历和交换。

单边循环法
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
public static void quickSort(int[] arr, int startIndex, int endIndex) {
    if (startIndex >= endIndex) {
        return;
    }
    int pivotIndex = partition(arr, startIndex, endIndex);
    quickSort(arr, startIndex, pivotIndex - 1);
    quickSort(arr, pivotIndex + 1, endIndex);
}

private static int partition(int[] arr, int startIndex, int endIndex) {
    int pivot = arr[startIndex];
    int mark = startIndex;

    for (int i = startIndex + 1; i <= endIndex; i++) {
        if (arr[i] < pivot) {
            mark++;
            int tmp = arr[mark];
            arr[mark] = arr[i];
            arr[i] = tmp;
        }
    }

    arr[startIndex] = arr[mark];
    arr[mark] = pivot;
    return mark;
}

非递归实现

上面的代码都是依靠递归来实现的，绝大多数用递归来实现的问题，都可以用栈的方式来代替。
因为我们代码中一层一层的方法调用，本身就是一个函数栈。每次进入一个新方法，就相当于入栈；每次有方法返回，就相当于出栈。
所以，我们可以把原本的递归实现转化成一个栈的实现，在栈当中存储每一次方法调用的参数：

使用非递归实现快速排序
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
public class QuickSort {
    public static void quickSort(int[] arr, int startIndex, int endIndex) {
        // 用一个集合栈来代替递归的函数栈
        Stack<Map<String, Integer>> quickSortStack = new Stack<>();
        // 整个数列的起止下标，以哈希的形式入栈
        Map<String, Integer> rootParam = new HashMap<>();
        rootParam.put("startIndex", startIndex);
        rootParam.put("endIndex", endIndex);
        quickSortStack.push(rootParam);
        // 循环结束条件，栈为空时结束
        while (!quickSortStack.isEmpty()) {
            // 栈顶元素出栈，得到起止下标
            Map<String, Integer> param = quickSortStack.pop();
            // 得到基准元素位置
            int pivotIndex = partition(arr, param.get("startIndex"), param.get("endIndex"));
            // 根据基准元素分成两部分，把每一部分的起止下标入栈

            if (param.get("startIndex") < pivotIndex - 1) {
                Map<String, Integer> leftParam = new HashMap<>();
                leftParam.put("startIndex", param.get("startIndex"));
                leftParam.put("endIndex", pivotIndex - 1);
                quickSortStack.push(leftParam);
            }
            if (param.get("endIndex") > pivotIndex + 1) {
                Map<String, Integer> rightParam = new HashMap<>();
                rightParam.put("startIndex", pivotIndex + 1);
                rightParam.put("endIndex", param.get("endIndex"));
                quickSortStack.push(rightParam);
            }
        }

    }

    private static int partition(int[] arr, int startIndex, int endIndex) {
        // 取第一个元素作为基准元素
        int pivot = arr[startIndex];
        int left = startIndex;
        int right = endIndex;

        while (left != right) {
            // 控制right指针比较并左移
            while (left < right && arr[right] > pivot) {
                right--;
            }
            // 控制left指针比较并右移
            while (left < right && arr[left] <= pivot) {
                left++;
            }
            // 交换left和right指向的元素
            if (left < right) {
                int tmp = arr[left];
                arr[left] = arr[right];
                arr[right] = tmp;
            }
        }
        // pivot和指针重合点交换
        int tmp = arr[left];
        arr[left] = arr[startIndex];
        arr[startIndex] = tmp;

        return left;
    }

    public static void main(String[] args) {
        int[] arr = new int[] { 4, 7, 6, 5, 3, 2, 8, 1 };
        quickSort(arr, 0, arr.length - 1);
        System.out.print(Arrays.toString(arr));
    }

}

和刚才的递归实现相比，代码的变动仅仅在quickSort方法当中。该方法中引入了一个存储Map类型元素的栈，用于存储每一次交换时的起始下标和结束下标。

每一次循环，都会让栈顶元素出栈，进行排序，并且按照基准元素的位置分成左右两部分，左右两部分再分别入栈。当栈为空时，说明排序已经完毕，退出循环。

改进主元选择的快排

在线性表中的第一个元素、中间元素和最后一个元素中选择一个 中位数作主元。

中位数选择的函数，如（1, 3, 5）选择3
1
2
3
4
public static int median(int first, int middle, int last) {
        return Math.max(Math.min(first, middle), 
            Math.min(Math.max(first, middle), last));
    }

复杂度及稳定性

算法复杂度：
时间复杂度（平均）： O(nlogn)
时间复杂度（最坏）： O(n^2)
时间复杂度（最好）： O(nlogn)

空间复杂度： O(nlogn)
快速排序是不稳定的排序算法。

快速排序有两个方向，左边的left指针一直往右走，当arr[left] <= pivot。而右边的right指针一直往左走，当arr[right] > pivot。如果left和right都走不动了，left <= right，交换arr[left]和arr[right]，重复上面的过程，直到left > right。 交换arr[left]和arr[startIndex]，完成一趟快速排序。
在中枢元素和a[left]交换的时候，很有可能把前面的元素的稳定性打乱，比如序列为5 3 3 4 3 8 9 10 11，现在中枢元素5和3（第5个元素，下标从1开始计）交换就会把元素3的稳定性打乱，所以快速排序是一个不稳定的排序算法，不稳定发生在中枢元素和arr[left] 交换的时刻。

快排和归并

归并排序和快速排序都使用了分而治之法。
对于归并排序，大量的工作是将两个子线性表进行归并，归并是在两个子线性表都 排好序后进行的。
对于快速排序，大量的工作是将线性表划分成两个子线性表，划分是在子线性表 排好序前进行的。
最差的情况下，归并排序的效率高于快速排序，但是，在平均情况下，两者效率相同。归并排序在归并两个数组是需要一个临时数组，而快速排序不需要额外的数组空间。因此，快速排序的空间效率高于归并排序。

快排和堆排序

相同点：堆排序和快速排序的平均时间复杂度都是O(nlogn)，并且都是 不稳定排序。

不同点：快速排序的最坏时间复杂度是O(n^2)，而堆排序最坏时间复杂度稳定在O(nlogn)。
此外，快速排序的递归和非递归的空间复杂度都是O(n)，而堆排序的空间复杂度是O(1)。

0%