基础闯关记-快速排序

# 快速排序
## 快速排序基本思想
快速排序的基本思想就是分治法，就是将一个大的数组按照某一中间值分成两个子集，一组是每个元素都大于中间值，另一组是每个元素都小于中间值，然后递归调用该过程，最后可完成排序。步骤：
```
1、先从数列中取出一个数作为基准数，可以是第一个元素或最后一个元素。

2、分两个子集，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。

3、再对左右子集间重复第二步，直到各子集只有一个数，排序结束
```

整个过程可以用下图的竹竿按从低到高的顺序排序，首先我们找出第一根杆子为标准，剩下的高杆移到右边，低杆移到左边（不用管两遍的顺序，只要符合低左高右即可）。然后针对左边再次进行同样的动作，最后就可以保证左边是从低到高排列的，再针对右边也进行同样的动作（图中没有画），最终所有的竹竿都是有序的。

![image](http://note.youdao.com/yws/api/personal/file/WEB7c9a009e4df41edecbdb58f20cb23aea?method=download&shareKey=a851b2b6d2cbbe5f0fa4940c11e930e4)

这个图可以看出，只要不断递归左右两个子集，最终递归结果就是整个数组有序。所以**快速排序的核心是找到一个快速的左右子集划分方法，以及找到一个合适的基准元素**，这两个因素影响了你写的快速排序到底快不快。

## 实现快速排序
前面说到，找到划分方法和基准元素，快速排序基本上就实现了。

如果要实现以某一个元素为基准，将数组划分成左右两个子集。方法其实有很多种，有的可能时间复杂度高，有的可能耗费空间多。
### 左右子集划分思路
《啊哈，算法》里介绍的一种方法，这种方法的效率比较高。这种方法就是假设有两个探针，分别是左探针和右探针。一开始分别指向数组的首地址和末地址。然后右探针开始向中间靠拢，直到发现一个小于基准值的元素，然后左探针也向中间靠拢，直到发现一个大于基准值的元素，这是交换两个探针的数组，直到两个探针相遇结束。整个过程可以用下图表示，仔细观察下基准元素4是如何插入到中间的

![image](http://note.youdao.com/yws/api/personal/file/WEBe80746a2e077fa73ec170783d6a56a77?method=download&shareKey=d493e7749ddb08770b20b9d3b7b32d2d)

### 左右子集划分代码
对照上图，很容易就可以写出相应的算法，实现上面过程的函数是partition函数，需要注意的是，看上面的图，最终和基准元素交换的是i和j相遇的地方。
```
#include<stdio.h>
void partition(int arr[], int left, int right);
void swap(int *a, int *b);

void main(){
    int arr[] = {4, 3, 6, 7, 1, 5, 2};
    partition(arr, 0, 6);
    int i = 0;
    while( i <= 7 ){
        printf("%d ", arr[i]);
        i++;
    }
}

/**
 * 以数组第一个元素为基准数，重排数组使得基准数左边都比它小，基准数右边都比它大
 * @param arr 数组地址
 * @param left 数组第一个元素地址 
 * @param right 数组最后一个元素地址
 */
void partition(int arr[], int left, int right){
    if(left >= right){
        return;
    }
    int mid = arr[left];
    int i = left;
    int j = right;
    while( i < j ){
        while(arr[j] >= mid && i < j){
            j--;
        }

while(arr[i] <= mid && i < j){
            i++;
        }
        if(i<j){
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i], &arr[left]);
}

//工具函数，交换两个数组元素
void swap(int *a, int *b){
    int tmp = *a;
    *a = *b;
    *b = tmp;
}
```

之所以把左右子集划分的算法单独提取出来，因为这个算法是可替代的，你可以写出自己的更高效的划分算法。

## 快速排序实现
有了上面的左右子集划分算法的实现，我们很快就能编写出一个快速排序算法，只需要递归调用左右自己划分算法就可以了，然后在这个基础上，再封装一个快速排序的方法
```
void quickSort(int arr[], int length){
    partition(arr, 0, length-1);
}
```
最后，附上快速排序的整个源代码
```
#include<stdio.h>
void partition(int arr[], int left, int right);
void swap(int *a, int *b);
void quickSort(int arr[], int length);

void main(){
    int arr[] = {4, 3, 6, 7, 1, 5, 2};
    quickSort(arr, 7);
    int i;
    for(i=0; i<7; i++){
        printf("%d ", arr[i]);
    }
}

void quickSort(int arr[], int length){
    partition(arr, 0, length-1);
}

while(arr[i] <= mid && i < j){
            i++;
        }
        if(i<j){
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[j], &arr[left]);
    partition(arr, left, j-1);
    partition(arr, j+1, right);
}

//工具函数，交换两个数组元素
void swap(int *a, int *b){
    int tmp = *a;
    *a = *b;
    *b = tmp;
}
```
## 基准元素
我们前面随便选第一个元素为基准元素太草率了。选基准元素很重要，要不然快速排序一点也不快。前面我们直接使用了数组的第一个元素为基准。但是这种情况往往并不理想，因为快速排序的思想是分治法，如果分的不均匀，那快速排序的时间复杂度一样为O(n^2)，试想一下最糟糕的情况，输入的数组已经有序了，在这个有序的基础上再次排序会怎么样。

![image](http://note.youdao.com/yws/api/personal/file/WEB5a40cf5226d77bfd7bd20a6662f4d29a?method=download&shareKey=e12a018037a8798b5b75fd50ae335c53)

计算一下这种情况的复杂度
```
T(n) = O(n) + T(n-1)
     = O(n) + O(n-1) + T(n-2)
     = O(n) + O(n-1) + ... + O(1)
     = O(n^2)
```

**快速排序最理想的情况找到一个基准元素将数组对半分开**

这也是分治法最理想的情况，因为每次对半开的话，子集的个数将按指数规模减少。所以针对快速排序，需要处理好基准元素的选取。

这里介绍一种取数组头，中，尾的中位数作为基准元素，有三种情况
```
1. 第一个元素已经是中位数，不用处理
2. 中间元素为中位数，交换第一个元素和中间元素
3. 最后一个元素为中位数，交换第一个元素和最后一个元素
```
代码实现
```
int getMid(int arr[], int left, int right){
    int leftVal = arr[left];
    int rightVal = arr[right];
    int mid = (left + right) / 2;
    int midVal = arr[mid];

if(leftVal < midVal && leftVal < rightVal){
        return leftVal;
    }else if(midVal < leftVal && midVal < rightVal){
        swap(&arr[left], &arr[mid]);
        return midVal;
    }else{
        swap(&arr[left], &arr[right]);
        return rightVal;
    }
}
```

Navigation

Recent Posts

Friend Links