关于java:JAVA快速排序代码

疾速排序三个步骤：

1. 抉择基准值：在待排序列中，依照某种形式挑出一个元素，作为基准值。
2. 宰割操作：以该基准值在序列中的理论地位，把序列分成两个子序列，一边是比它大的值，另外一边是比它小的值。
3. 递归：对两个子序列进行快排，直到序列为空或者只有一个元素。

代码实现

package sort;

import java.util.Arrays;

public class QuickSort {public static void quickSort(int[] arr, int left, int right){
        // 递归的进口：只剩下一个元素的时候
        if (left >= right){return;}
        int pivot = arr[left];
        int i = left, j = right;
        while (i < j) {
            // 这里如果 pivot 选在左侧，就要先从右侧开始遍历，反之则先从左侧开始
            // 小于等于来解决反复的元素
            while (arr[j] >= pivot && i < j){j--;}
            // 找到比基准小的数换到左侧
            arr[i] = arr[j];
            while (arr[i] <= pivot && i < j) {i++;}
            // 找到比基准大的数换到右侧去
            arr[j] = arr[i];
        }
        // 最初将基准放到两头地位
        arr[i] = pivot;
        //  递归快排左侧数列
        quickSort(arr, left, i - 1);
        // 递归遍历右侧数列
        quickSort(arr, i + 1, right);
    }

    public static void main(String[] args) {int[] arr = {7,3,2,1,6,4,5,6};
        int left = 0;
        int right = arr.length - 1;

        quickSort(arr, left, right);

        System.out.println(Arrays.toString(arr));
    }
}

工夫复杂度

对 n 个元素进行疾速排序的过程形成一棵递归树，在这样的递归树中，每一层最多对 n 个元素进行划分，所花的工夫为 O(n)。当初始排序数据随机散布，使每次分成的两个子区间中的元素个数大抵相等时，递归树高度为 log2n，疾速排序出现最好状况，即最好状况下的工夫复杂度为 O(nlog2n)。疾速排序算法的均匀工夫复杂度也是 O(nlog2n)。所以疾速排序是一种高效的算法。

最坏状况为，每一轮分不成两组，每一轮都只能把基准值索引放到第一个或者最初一个，因而一共须要 n 轮。
因而，最坏工夫复杂度为 O(n^2)。