검지 Offer - 정렬: 빠 른 정렬

제목:
쾌속 열 을 실현 하 다.
링크:
검지 제공 (제2판): P80
아이디어 태그:
알고리즘: 귀속
해답:
1. C++

빠 른 배열 은 재 귀 작업 을 바탕 으로 이 루어 진 것 이다.

먼저 배열 에서 무 작위 로 하나의 수 를 기준 으로 하고 끝의 요소 와 교환 하 며 마지막 요소 의 위치 에 놓 아 후기 비교 작업 을 편리 하 게 한다.

기준 보다 작고 기준 보다 큰 경 계 를 설정 하고 경 계 는 기준 보다 작은 마지막 수 이 며 초기 에 start - 1 로 설정 합 니 다.

배열 을 옮 겨 다 니 며 기준 보다 작은 수 는 경계 앞 에 교환 하고 기준 보다 큰 수 는 변 하지 않 을 수 있다.

기준 을 중간 위치 에 놓는다.

위의 절 차 는 한 번 의 실현 이 고 파 티 션 (partition) 작업 이 라 고 합 니 다.

왼쪽, 오른쪽 두 개의 배열 의 구역 구분 작업 을 재 귀적 으로 실현 하면 최종 적 으로 순 서 를 이룬다.

시간 복잡 도: 최 악의 상황 O (n ^ 2), 최 적의 상황 O (nlogn), 평균 상황 O (nlogn)

void swap(int* data, int i, int j){
    if(i == j) return;
    int temp = data[i];
    data[i] = data[j];
    data[j] = temp;
}

//     
int partition(int data[], int length, int start, int end){
    if(data == nullptr || length <= 0 || start < 0 || end >= length)
        throw new std::exception("Invalid Parameter");

    int index = rand() % (end - start + 1) + start; //       
    swap(data, index, end);
    int small = start - 1;
    for(index = start; index < end; ++index){
        if(data[index] < data[end]){
            ++small;
            if(small != index)
                swap(data, small, index);
        }
    }

    ++small;
    swap(data, small, end);

    return small;
}


void quickSort(int data[], int length, int start, int end){
    if(start == end) return;

    int index = partition(data, length, start, end);
    if(index > start)
        quickSort(data, length, start, index-1);
    if(index < end)
        quickSort(data, length, index+1, end);
}

2. python

def quick_sort(lists, left, right):
    #     
    if left >= right:
        return lists
    key = lists[left]
    low = left
    high = right
    while left < right:
        while left < right and lists[right] >= key:
            right -= 1
        lists[left] = lists[right]
        while left < right and lists[left] <= key:
            left += 1
        lists[right] = lists[left]
    lists[right] = key
    quick_sort(lists, low, left - 1)
    quick_sort(lists, left + 1, high)
    return lists

정렬 관련
python：

http://python.jobbole.com/82270/

동적 그림:

http://web.jobbole.com/87968/

기타 관련 문제
제목: 회사원 연령 서열
수만 명의 직원 이 정렬 알고리즘 을 실현 하고 시간 효율 O (n) 를 요구 하 며 상수 크기 의 보조 공간 을 사용 할 수 있 으 며 O (n) 를 초과 하지 않 습 니 다.연령 대 는 0 ~ 99 사이 다.
분석:

시간 효율 을 O (n) 로 요구 하기 때문에 추가 공간 을 사용 해 야 실현 할 수 있다 는 것 을 의미한다.

제목 에서 직원 의 연령 에 대해 순 위 를 매기 기만 하면 된다.

void sortAges(int ages[], int length){
    if(ages == nullptr || length <= 0) return;

    const int oldestAge = 99;
    int timesOfAge[oldestAge + 1];
    for(int i=0; i<=oldestAge; ++i)
        timesOfAge[i] = 0;

    for(int i=0; iint age = ages[i];
        if(age < 0 || age > oldestAge)
            throw new std::exception("Age of out range!");

        ++timesOfAge[age];
    }

    int index = 0;
    for(int i=0; i<=oldestAge; ++i){
        for(int j=0; j