#排序

7.1 快速排序的描述

最好情况/平均情况：

1. 分解：数组a[p..r]被划分为两个（可能为空）子数组a[p..q-1]和a[q+1..r]，是的a[p..q-1]中的每一个元素都小于a[q]，而a[q]也小于等于a[q+1..r]中的每个元素。其中计算下标q也是划分过程的一部分。
2. 解决：通过递归调用快速排序，对子数组a[p..q-1]和a[q+1..r]进行排序。
3. 合并：因为子数组都是原址排序的，所以不需要合并操作：数组a[p..r]已经有序

int *quicksort(int arr[], int p, int r){
    if(p < r){
        q = partition(arr, p, r);
        quicksort(arr, p, q-1);
        quicksort(arr, q+1, r);
    }
}

int partition(int arr[], int p, int r){
    int x = a[r];
    int i = p-1;
    for(int j=p; j<=r-1; j++){
        if(a[j] <= x){
            i++;
            swap(&a[i], &a[j]);
        }
    }
    swap(&a[i+1], &a[r]);
    return i+1;
}

void swap(int *x, int *y){
    int temp;
    temp = *x;//取内容交换
    *x = *y;
    *y = temp;
}

// way1
// 主算法
void quickSort(keytype k[],int n){
	quick(K, 0, n-1);
}
void quick(keytype k[ ],int left,int right){
    int i, j;
    keytype pivot;
    if(left < right){
        i = left;
        j = right+1;
        pivot = k[left];
        while(1){ 
            while(k[++i]<pivot && i!=right) { }
            while(k[--j]>pivot && j!=left) { }
            if(i < j)
            	swap(&k[i], &k[j]);  /*交换K[i]与K[j]的内容*/
            else
            	break;
        }
        swap(&k[left], &k[j]);      /*交换K[s]与K[j]的内容*/
        quick(k, left, j-1);       /* 对前一部分排序 */
        quick(k, j+1, right);       /* 对后一部分排序 */
    }
}
void swap(keytype *x, keytype *y){
    keytype temp;
    temp = *x;//取内容交换
    *x = *y;
    *y = temp;
}

// way2 BY K&R
// 主算法
void quickSort(keytype k[],int n){
       qsort(k, 0, n-1);
}
void qsort(keytype v[ ],int left, int right){
    int i, last;
    if(left >= right)
        return;
    swap(v, left, (left+right)/2);		//move partition elem to v[0]
    last = left;
    for(i=left+1; i<=right; i++)		//partition
        if(v[i] < v[left])
            swap(v, ++last, i);
    swap(v, left, last);		//restore partition elem
    qsort(v, left, last);  
    qsort(v, last+1, right);
}
void swap(keytype v[ ],int i, int j){
    keytype tmp;
    tmp = v[i];
    v[i] = v[j];
    v[j] = tmp;
}

7.2 快速排序的性能

7.3 快速排序的随机化版本

void randomized-quiksort(int arr[], int p, int r){
    if(p < r){
        q = randomized-partition(arr, p, r);
        randomized-quiksort(a, p, q-1);
        randomized-quiksort(a, q+1, r);
    }
}
int randomized-partition(int arr[], int p, int r){
    int i = random(p, r);
    swap(&a[r], &a[i]);
    return partition(arr, p, r);
}
int partition(int arr[], int p, int r){
    int x = a[r];
    int i = p-1;
    for(int j=p; j<=r-1; j++){
        if(a[j] <= x){
            i++;
            swap(&a[i], &a[j]);
        }
    }
    swap(&a[i+1], &a[r]);
    return i+1;
}

7.4 快速排序分析

1. 最坏情况：
2. 期望运行时间：