目录
选择排序
基本思想
选择排序的实现
图片实现
代码实现
快速排序
基本思想
快速排序的实现
图片实现
代码实现
选择排序
基本思想
每一次从待排序的数据元素中选出最小（最大）的元素，存放在序列的起始位置，直到全部待排序的数据元素排完。
选择排序的实现
图片实现
如图，是一组数据。让4为起始位置，从2开始遍历到8，找到最小的那个数字 1（必须要小于4），然后交换 4和 1。然后再从2开始，直到全部遍历完。
代码实现
void SelectSort(int* a, int n)
{
int begin = 0;
int end = n - 1;
int min = begin;
while (begin < end)
{
for (int i = begin + 1;i <= end;++i)
{
if (a[i] < a[min])
{
min = i;
}
}
Swap(&a[begin], &a[min]);
++begin;
min = begin;
}
}如果同时把最小的放在起始位置，最大的放到末尾位置，我们就能得到这个代码
代码如下：
void SelectSort(int* a, int n)
{
int begin = 0, end = n - 1;
while (begin < end)
{
int mini = begin, maxi = begin;
for (int i = begin + 1; i <= end; ++i)
{
if (a[i] < a[mini])
{
mini = i;
}
if (a[i] > a[maxi])
{
maxi = i;
}
}
Swap(&a[begin], &a[mini]);
if (maxi == begin)
{
maxi = mini;
}
Swap(&a[end], &a[maxi]);
++begin;
--end;
}
}理解一下这个代码，会比较能理解下面所讲的快速排序了。
快速排序
基本思想
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，基本思想是：任取待排序元素序列中的某元素作为基准值，按照该排序码将排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排序完成。
快速排序的实现
图片实现
代码实现
代码如下：
void QuickSort(int* a, int begin,int end)
{
if (begin >= end)
return;
//注意一下
int left = begin, right = end;
int keyi = begin;
while (left < right)
{
//右边，找到比a[keyi]小的,然后放到左边
//注意条件是<=
while (left < right && a[keyi] <= a[right])
{
--right;
}
//左边，找到比a[keyi]大的，然后放到右边
//注意条件是>=
while (left < right && a[keyi] >= a[left])
{
++left;
}
Swap(&a[left], &a[right]);
}
Swap(&a[keyi], &a[left]);
keyi = left;
QuickSort(a, begin, keyi - 1);
QuicktSort(a, keyi+1, end);
}这个快速排序是Hoare版本的快速排序，要注意的事情非常多，一不小心就会弄错。
比如while循环的条件，还有交换，以及keyi。
下一篇文章会介绍改进版本的快速排序。
