1、排序與查找的關(guān)系

排序是查找的前提。

排序時，要考慮時間、空間、穩(wěn)定性。

2、插入排序

3、選擇排序

4、歸并排序

5、快速排序

先找到某一個元素（假定是第一個元素）的最終位置，然后把數(shù)據(jù)分為兩半。然后在兩半分別再找到某一個元素的最終位置……——遞歸

經(jīng)過一次排序，只能確定一個元素的最終位置，其他元素仍然是無序的。

例：

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個參數(shù)：第1個元素的下標(biāo) 
    // 第3個參數(shù)：最后一個元素的下標(biāo) 

    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結(jié)束之后，low和high一定是相等的
    // 這個值就是val的最終位置 

    a[low] = val;

    return low; 
}