算法导论笔记 -- Step 7 [快速排序]

**转载请注明**

快速排序，又一个divide-and-conquer的实例。
虽然最坏情况是O(n^2)，但是平均期望效率是O(nlgn)，所以在应用中还是比较广泛的。



原理：

1. 在原数组里取一个点（假如是末尾的），小于它的往前‘放’；大于的往后排；排完了把它放中间。
2. 然后把大小两子数组再排序。
    * ‘放’：每次标杆 j 向后移，遇到小于标杆的就跟 i+1 交换，交换时 i 也往后移。

#include <iostream>

using namespace std;

void Switch ( int*, int, int );
void Print_array ( int*, int, int );

void Quick_sort ( int*, int, int );
int Partition ( int*, int, int ); // Find the final pivot position

int main(){
    int array[] = { 2,8,7,1,3,5,6,4 };
    Quick_sort(array, 0, sizeof(array)/sizeof(int)-1);

    Print_array(array, 0, sizeof(array)/sizeof(int)-1);
    return 0;
}

void Quick_sort ( int* array, int start, int end){
    if ( start < end ){
        int p = Partition(array, start, end);
        Quick_sort ( array, start, p-1 );
        Quick_sort ( array, p+1, end );
    }
}

int Partition ( int* array, int start, int end ){
    int i = start-1;
    for( int j = start; j <= end-1; j++ ){
        if ( array[j] < array[end] ){
            i++;
            Switch(array, i, j);
        }
    }
    i++;
    Switch(array, i, end);
    return i;
}

void Switch ( int* array, int index1, int index2 ){
    int mid = array[index1];
    array[index1] = array[index2];
    array[index2] = mid;
}

void Print_array ( int* array, int start, int end ){
    while( start <= end ){
        cout << array[start] << endl;
        start++;
    }
}

运行结果：


空间复杂度： 
    O（1）

时间复杂度：
    O（n^2)