1、排序与查找的关系

排序是查找的前提。

排序时，要考虑时间、空间、稳定性。

2、插入排序

3、选择排序

4、归并排序

5、快速排序

先找到某一个元素（假定是第一个元素）的最终位置，然后把数据分为两半。然后在两半分别再找到某一个元素的最终位置……——递归

经过一次排序，只能确定一个元素的最终位置，其他元素仍然是无序的。

例：

9 0 8 10 -5 2 13 7

9：
l：比它大的赋值，比它小的移动；
h：比它小的赋值，比它大的移动。

5 2 6 8 4 3 7
第一次：
3 2 4 5 8 6 7

程序：

#include <stdio.h>

void QuickSort(int *, int, int);
int FindPos(int *, int, int);

int main(void)
{
    int a[6] = {2, 1, 0, 5, 4, 3};
    int i = 0;

    QuickSort(a, 0, 5); 
    // 第2个参数：第1个元素的下标 
    // 第3个参数：最后一个元素的下标 

    for(i=0; i<6; ++i)
    {
        printf("%d ", a[i]);
    }
    printf("\n");

    return 0;
}

void QuickSort(int * a, int low, int high)
{
    int pos = 0;

    if(low < high)
    {
        pos = FindPos(a, low, high); // 找到该元素的最终位置 
        QuickSort(a, low, pos-1);
        QuickSort(a, pos+1, high);
    }
}

int FindPos(int * a, int low, int high)
{
    int val = a[low];

    while(low < high)
    {
        while(low < high && a[high] >= val)
        {
            --high;
        }
        a[low] = a[high];
    
        while(low < high && a[low] <= val)
        {
            ++low;
        }
        a[high] = a[low];
    } 
    // while结束之后，low和high一定是相等的
    // 这个值就是val的最终位置 

    a[low] = val;

    return low; 
}