排序算法之快速排序（五）

125 阅读 0 评论 83 点赞

我是靠谱客的博主负责棉花糖，这篇文章主要介绍排序算法之快速排序（五），现在分享给大家，希望可以做个参考。

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

例如：4，3，1，2，6，5，

1.刚开始定义两个变量i和j指向数组的首尾，首先将i号下标元素值拿出来当作标记位。从j开始由后向前找到第一个比标记位4小的值放到i好下标位置即图2，然后i向后移动找到第一个比标记位4大的数放到j号下标，如图三，重复以上步骤，直到i=j，将标记位4放入i=j号下标，至此完成一趟排序，一趟排序之后所有比4小的都在4的左边，比4大的都在4的右边。

2.一趟排序之后结果 1，3，2，4，6，5，将1，3，2分为一组，6，5分为一组，继续进行快排。

完整的过程：

原数组：4，3，1，2，6，5

一趟后 1，3，2，4，6，5

二趟后 1，2，3，4，5，6

时间复杂度 O(nlogn) 空间复杂度O(1) 不具有稳定性

代码实现

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
private static <T extends Comparable<T>>void quickSort(T[] arr, int left, int right) {
        if (left >= right){
            return;
        }
        T temp = arr[left];
        int i = left;
        int j = right;
        while (i<j){
            while (arr[j].compareTo(temp)>0 && i<j){
                j--;
            }
            arr[i] = arr[j];
            while (arr[i].compareTo(temp)<=0 && i<j){
                i++;
            }
            arr[j] = arr[i];
        }
        arr[i] = temp;
        quickSort(arr,left,i-1);
        quickSort(arr,i+1,right);
}