选择排序和快速排序（1）

目录

选择排序

基本思想

选择排序的实现

图片实现

代码实现

快速排序

基本思想

快速排序的实现

图片实现

 代码实现

---

选择排序

基本思想

每一次从待排序的数据元素中选出最小（最大）的元素，存放在序列的起始位置，直到全部待排序的数据元素排完。

选择排序的实现

图片实现

如图，是一组数据。让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。

下一篇文章会介绍改进版本的快速排序。