LintCode 464 Sort Integers II

思路

快排练习，不多说

复杂度

时间复杂度：平均O(nlogn)，最坏O(n^2)
空间复杂度：平均O(logn)，最坏O(n)

代码

public class Solution {
    /*** @param A: an integer array* @return: nothing*/public void sortIntegers2(int[] A) {
    // write your code hereif (A == null || A.length == 0) {
    return;}quickSort(A, 0, A.length - 1);}private void quickSort(int[] A, int start, int end) {
    if (start >= end) {
    return;}int left = start, right = end;int pivot = A[(start + end) / 2];while (left <= right) {
    while (left <= right && A[left] < pivot) {
    left++;}while (left <= right && A[right] > pivot) {
    right--;}if (left <= right) {
    int t = A[left];A[left] = A[right];A[right] = t;left++;right--;}}quickSort(A, start, right);quickSort(A, left, end);}
}