빠른 정렬 시간 복잡도와 공간 복잡도

최근에 빠른 정렬 알고리즘을 쓰지 않고 이 코드의 빠른 정렬 알고리즘을 돌려 수조에서 주원(pivot)이라는 요소를 선택하여 수조를 두 부분으로 나누어 첫 번째 부분의 모든 요소가 주원보다 작거나 같게 하고 두 번째 부분의 모든 요소가 주원보다 크다.첫 번째 부분에 대해 빠른 정렬 알고리즘을 적용하고 두 번째 부분에 대해 빠른 정렬 알고리즘을 적용한다.최악의 경우 n개의 원소로 구성된 수조를 구분하려면 n차 비교와 n차 이동이 필요하다.따라서 구분에 필요한 시간은 O(n)입니다.최악의 경우, 매번 주원은 수조를 하나의 큰 자수조와 하나의 공수조로 구분한다.이 큰 자수조의 규모는 지난번에 구분된 자수조의 규모를 1로 줄인 것이다.이 알고리즘은 (n-1)+(n-2)+...+2+1=O(n^2) 시간이 필요합니다.최적 상황에서 매번 주원은 수조를 규모가 대체적으로 같은 두 부분으로 구분한다.설정 T(n)는 빠른 정렬 알고리즘을 사용하여 n개의 요소를 포함하는 그룹을 정렬하는 데 걸리는 시간을 표시하기 때문에 병합 정렬의 분석과 비슷하고 빠른 정렬의 T(n) = O(nlogn)이다.

import java.awt.List;
/**
 * Created by shuxing on 2017/7/12.
 */
public class QuickSort {
    public static int[] quickSort(int[] list) {
        quickSort(list, 0, list.length - 1);
        return list;
    }

    public static int[] quickSort(int[] list, int first, int last) {
        if (first < last) {// （pivot） 
            int pivotIndex = partition(list, first, last);
            quickSort(list, first, pivotIndex - 1);
            quickSort(list, pivotIndex + 1, last);
        }
        return list;
    }
    public static int partition(int[] list, int first, int last) {// 
        int pivot = list[first], low = first + 1, high = last;
        // 
        while (high > low) {
            while (pivot >= list[low] && low <= high)
                low++;
            while (pivot < list[high] && low <= high)
                high--;
            // 
            if (low < high) {
                int tmp = list[low];
                list[low] = list[high];
                list[high] = tmp;
            }
        }
        // 
        while (list[high] >= pivot && high > first)
            high--;
        if (list[high] < pivot) {
            list[first] = list[high];
            list[high] = pivot;
            return high;
        }
        else {
            return first;
        }
    }
    public static void main(String[] args) {
        int[] list = {2,6,3,5,4,1,8,45,2};
        list = quickSort(list);
        for (int i = 0; i < list.length; i++) {
            System.out.println(list[i]);
        }
    }
}

더욱 알기 쉬운 빠른 정렬 알고리즘을 볼 수 있습니다.http://blog.csdn.net/morewindows/article/details/6684558