除了上一次介绍的希尔排序，堆排序，快速排序，也是经常用到的排序方式，其中快速排序可以说是一种性能十分优秀的排序。
1 堆排序：
针对堆排序，对于其代码实现不作阐述，因为太过于复杂，主要是堆处理的复杂。
在此，对其算法的核心步骤作一定描述：
堆排序，本质上，分为两步：
1 建立堆：
1 广度优先初始化堆
2大数上浮，使满足堆属性
2 堆排序：
1 取走树根的值
2 将树根的值与 最下层 最右侧（注意这个描述所代表的位置）的叶子节点交换
3 去掉经过步骤2交换后的最下层，最右侧的叶子节点（也就是原根节点）
4 将最大数上浮至根
5 重复1、2、3、4
堆排序使用了堆这种数据结构，对数据进行排序，尽管上述过程看起来并不复杂，但在实际写程序的时候，也并不是一个简单的过程。
2 快速排序：
快速排序是一种十分优秀的排序方式，甚至说是一种最优的排序都不为过。
快速排序采用分治递归的思想完成了对数组的排序，快速排序的核心思想是：给基准数据（也就是边界）找其正确索引位置。
什么叫：给基准数据找其正确索引位置呢？ 举个例子：
对于原始数据： 8,2,6，我们知道其从小到大的顺序是：2,6,8；那么对于数据8而言，正确的位置是：3,；对于数据2而言，正确的位置是1。那么给基准数据找其正确索引的位置被理解成：假如现在选定基准数据6，我们要能把数据6 放到位置 2 ，就完成了 给基准数据（也就是边界）找其正确索引位置。那么如何做到这一点呢？也就是：我们怎么样才知道一个数据被放到了正确的位置呢？ 其实核心在于：这个数左边的数据都比这个数小，这个数右边的数据都比这个数大，那么这个数就被放到了一个正确位置。这是一种十分朴素但是又十分重要的思想。而快速排序证实基于这种思想完成了快速的排序。下面我们看看，快速排序如何做到这一点：
假如对于一组数据[a1,a2,....,an]假设数据的个数为n，大小顺序任意。我们先选择这组数据 (1+n)/2位置的数据作为基准数据，也就是中间位置的数据，将这个数左边作为一个子数组v1，这个数右边作为另外一个子数组v2。也就是整个大的待排序的数组被分成了2个小数组。这个时候，我们需要清楚：我们到底要干什么？
没错，我们需要将这个位置处于 (1+n)/2的数据放在正确的位置。这个时候，我们就要用到上面的思想了：这个数左边的数据都比这个数小，这个数右边的数据都比这个数大，那么这个数就被放到了一个正确位置。更具体而言：
这个数左边的子数组v1的每个数据都与基准数据进行比较，也就是与位置(1+n)/2的数据进行比较，如果比基准数据大，就把这个这个数据交换到右边数组对称的位置去。同样的，对于右侧数组，也采用相同的操作。最终，使得基准数据的左侧数据都比 基准数据（边界）小，使得基准数据的右侧侧数据都比 基准数据（边界）大。
但是这仅仅将一个数据放在了正确的位置，那么剩下的数据该怎么办呢？，同样的，对于左侧的子数组v1，右侧的子数组v2；再次选取各自的中间位置的数据作为边界，将v1分为v1-1,v1-2，将v2分解成v2-1,v2-2。这个时候对于从v1中选取的基准数据，从v2中选取的基准数据，将他们放在正确的位置.....一直这样做下去，最后整个大的数组被分解成n个小数组，即每个数组只有一个元素，排序结束，得到正确的排序结果。
这就是快速排序，怎么样，十分精彩吧，这种分治递归，为数据找正确位置的思想简直爆炸精彩好嘛23333.。
说了这么多，先上个代码吧：
1 //快速排序 2 void FastSort(vector<int> & sort_a) 3 { 4 int a_size; 5 a_size = sort_a.size();//得到数组大小 6 if (a_size < 2) 7 return; 8 int MaxIndex = 0; 9 for (int count = 1; count < a_size;count++) 10 { 11 if (sort_a[count]>sort_a[MaxIndex]) 12 { 13 MaxIndex = count; 14 } 15 } 16 swap(sort_a[a_size - 1], sort_a[MaxIndex]);//这里的swap用的是vector中的函数 17 FastSort(sort_a, 0, a_size-2); 18 } 19 ///快速排序 20 void FastSort(vector<int> & sort_array, int first, int last) 21 { 22 int lower = first + 1; 23 int upper = last; 24 swap(sort_array[first], sort_array[(first + last) / 2]); 25 int bound = sort_array[first];//将中间位置元素作为bound，并将其放在最开始的位置 26 while (lower <= upper) 27 { 28 while (sort_array[lower] < bound) 29 lower++; 30 while (sort_array[upper] > bound) 31 upper--; 32 if (lower < upper) 33 swap(sort_array[lower++], sort_array[upper--]); 34 else 35 lower++; 36 } 37 swap(sort_array[first], sort_array[upper]); 38 if (first < upper-1) 39 FastSort(sort_array, first, upper - 1); 40 if (last > lower) 41 FastSort(sort_array, lower, last); 42 /*if (last > upper+1) 43 FastSort(sort_array, upper + 1, last);*/ 44 }
上述过程完美的呈现了快速排序的优雅。在此对这个程序不再作阐述，有兴趣参考《c++数据结构与算法》这本书。只是这个程序中，有一个让我不安的地方：将待排序数组的最大数据放到了数据最右边，最大数据不参与排序。。。（暂时还没搞清楚为什么这么做，书上说和边界有关，暂时先不管）
我们再来关注一下：上文中有一句：我们先选择这组数据 (1+n)/2位置的数据作为基准数据。可能，每个人都会问，为什么选这个地方的数据，这样做一定好吗，什么样才是好的呢？
先说结论：快速排序最复杂的地方在于边界位置的选取，我们选取的这个地方的边界不一定是最好的。那么什么样的叫好的边界呢？
我们知道：快速排序的过程，数组一生二，二生四，四生八......如果我们选的边界，使得每次划分的子数组彼此间数据个数大致相等，那么这种边界选取就是一种优秀的方案。遗憾的是，并不存在一个理论的划分方式，这和数据的序列有关。这就导致了快速排序并不是一种稳定的算法（尽管如此，仍然很优秀）
那为何我们通常会选择中间位置的数据作为边界呢？那是因为：在实际上，数组的排序基本排序好了（注意是“基本”），这样选择中间的数据，其左右数据交换后，个数大致也是相等的）。
