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;
}
