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

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

例如：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)   不具有稳定性

代码实现

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);
}

最后

以上就是负责棉花糖为你收集整理的排序算法之快速排序（五）的全部内容，希望文章能够帮你解决排序算法之快速排序（五）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。