交换排序(Exchange sorts)专题
这类算法通过在序列内元素之间的进行比较并交换元素对序列进行排序。
下面介绍的算法实现中，排序输出的结果均是由小到大排列，只要稍微修改下代码（主要是判断语句）都可以使得输出序列的结果由大到小排列。
1.冒泡排序 Bubble sort / sinking sort
算法(参考维基百科：http://en.wikipedia.org/wiki/Bubble_sort)：
Repeatedly steps through the list to be sorted, compares each pair of adjacent items and swaps them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list
is sorted. The algorithm, which is a comparison sort, is named for the way smaller elements "bubble" to the top of the list.
http://zh.wikipedia.org/wiki/冒泡排序)：
1.比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。
2.對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最後一對。這步做完後，最後的元素會是最大的數。
3.針對所有的元素重複以上的步驟，除了最後一個。
4.持續每次對越來越少的元素重複上面的步驟，直到沒有任何一對數字需要比較。
特点：
1.稳定的(Stability)：相等的两个元素，在执行算法后他们的前后顺序保持不变。
2.属于比较排序算法。
3.原址的(in place)，辅助空间复杂度O(1)，至多需要O(1)空间或内存存储辅助的数据。
4.时间复杂度：最优：O(n)，此时原始序列已顺序排列；最差：O(n^2)，此时原始序列逆序排列；平均：O(n^2)。
5.数据规模n较大或数据逆序排列时不适用，有更好的其他算法可以代替。冒泡排序适用n较小且数据大部分已经顺序排列好的情况，此时运行时间接近O(n)。
6.序列中有两种类型元素排序时移动的效率不一致(冒泡排序的一个特点：兔子和乌龟问题)：原始序列中开头且值较大的元素（兔子）经过少数步骤后（快）就可以被交换到序列尾部，但末尾且数值较小的元素（乌龟）要经过较多的步骤（慢）才能被交换到序列头部。(参考维基百科Bubble sort 中：Rabbits and turtles:Large elements at the beginning of
the list do not pose a problem, as they are quickly swapped. Small elements towards the end, however, move to the beginning extremely slowly.)
上述也说明了针对存在兔子情况的序列冒牌排序表现会好些，例如输入序列：5，1，2，3，4；而针对存在乌龟情况的序列冒泡排序表现会差些，例如输入序列：2，3，4，5，1。
算法C实现（有些实现（例如维基百科中）是比较当前元素和前一个元素来决定是否进行交换，这里是比较当前元素和下一个元素来决定是否进行交换，两个实现效果一致，注意好循环的边界条件即可）：
void bubble_sort(TYPE* array, TYPE count)
{
TYPE i,temp;
TYPE flag_repeat = 1;
/// repeated until no swaps
while (flag_repeat) {
flag_repeat = 0;
for (i = 0; i < count - 1; i++) {
/// compares adjacent items and swaps them if in wrong order.
if (array[i] > array[i + 1]) {
temp = array[i];
array[i] = array[i + 1];
array[i + 1] = temp;
flag_repeat = 1;
}
}
}
}
算法C优化：
由于每次循环过程中，被交换且距离数组起始位置最远的元素，总是当前数组起始位置到该元素位置之间所有元素中的最大值，并且比该元素位置更远的元素都已经被排好序，因此可以优化算法减少多余的判断次数。下面为优化代码:
void bubble_sort(TYPE* array, TYPE count)
{
TYPE i, temp;
TYPE flag_repeat = 1;
TYPE current_count = count - 1;
/// repeated until no swaps
while (flag_repeat) {
flag_repeat = 0;
for (i = 0; i < current_count; i++) {
/// compares adjacent items and swaps them if in wrong order.
if (array[i] > array[i + 1]) {
temp = array[i];
array[i] = array[i + 1];
array[i + 1] = temp;
flag_repeat = i;
}
}
/// new count for comparison
current_count = flag_repeat;
}
}
拓展：冒泡排序可以和插入排序做下比较（主要是交换次数及元素移动方面），因为较好的情况下插入排序算法可能也优于冒泡排序。另外，如果原始序列开头已是排好的序列，末尾有少数未进行排序的元素，那么从右向左进行冒牌排序将是一个不错的选择（维基百科中指出了这一点：In some cases, the sort works from right to left (the opposite direction), which is
more appropriate for partially sorted lists, or lists with unsorted items added to the end.）。
2.鸡尾酒排序 Cocktail sort
算法(参考维基百科：http://en.wikipedia.org/wiki/Cocktail_sort)：
The algorithm differs from a bubble sort in that it sorts in both directions on each pass through the list. This sorting algorithm is only marginally more difficult to implement than a bubble sort, and solves the problem of
turtles in bubble sorts.
是冒泡排序法的一种变形，该算法双向进行冒泡排序，目的是解决冒泡排序中兔子乌龟问题，序列开头值大的元素和序列尾部值小的元素都能够迅速移动大正确的序列头尾。
特点：
1.各方面特点与冒泡排序特点(上文1，2，3，4，5点)一致。
2.鸡尾酒排序速度通常是冒泡排序速度的两倍(小于两倍)。典型的例子是：2，3，4，5，1，这时鸡尾酒排序比冒泡排序表现的更好。
算法C实现(已采用冒泡排序同一优化思路进行优化):
void cocktail_sort(TYPE* array, TYPE count)
{
TYPE i, temp;
TYPE flag_repeat = 1;
TYPE begin = 0;
TYPE end = count - 1;
/// repeated until no swaps
while (flag_repeat) {
/// from begin to end
flag_repeat = 0;
for (i = begin; i < end; i++) {
/// compares adjacent items and swaps them if in wrong order.
if (array[i] > array[i + 1]) {
temp = array[i];
array[i] = array[i + 1];
array[i + 1] = temp;
flag_repeat = i;
}
}
/// out of loop if no swap
if (flag_repeat == 0)
break;
/// new end for comparison
end = flag_repeat;
/// from end to begin
flag_repeat = 0;
for (i = end; i > begin; i--) {
/// compares adjacent items and swaps them if in wrong order.
if (array[i] < array[i - 1]) {
temp = array[i];
array[i] = array[i - 1];
array[i - 1] = temp;
flag_repeat = i;
}
}
/// new begin for comparison
begin = flag_repeat;
}
}
3.奇偶排序 Odd-even sort
算法(参考维基百科：http://en.wikipedia.org/wiki/Odd%E2%80%93even_sort)：
It functions by comparing all (odd, even)-indexed pairs of adjacent elements in the list and, if a pair is in the wrong order (the first is larger than the second) the elements are switched. The next step repeats this for
(even, odd)-indexed pairs (of adjacent elements). Then it alternates between (odd, even) and (even, odd) steps until the list is sorted.
http://zh.wikipedia.org/wiki/奇偶排序)：
該演算法中，透過比較陣列中相鄰的（奇-偶）位置數位對，如果該奇偶對是錯誤的順序（第一個大於第二個），則交換。下一步重複該操作，但針對所有的（偶-奇）位置數位對。如此交替進行下去。
奇偶排序也是冒泡排序的一个变种，该算法主要用于并行处理器(parallel processors)进行高效排序。
特点：
各方面特点与冒泡排序特点一致。
算法C实现(若算法在单处理器下运行，或未针对处理器进行并行计算优化，并不见得会比冒泡排序高效)：
void odd_even_sort(TYPE* array, TYPE count)
{
TYPE i, temp;
TYPE flag_repeat = 1;
/// repeated until no swaps
while (flag_repeat) {
flag_repeat = 0;
/// pass by odd
for (i = 1; i < count - 1; i += 2) {
/// compares adjacent items and swaps them if in wrong order.
if (array[i] > array[i + 1]) {
temp = array[i];
array[i] = array[i + 1];
array[i + 1] = temp;
flag_repeat = 1;
}
}
/// pass by even
for (i = 0; i < count - 1; i += 2) {
/// compares adjacent items and swaps them if in wrong order.
if (array[i] > array[i + 1]) {
temp = array[i];
array[i] = array[i + 1];
array[i + 1] = temp;
flag_repeat = 1;
}
}
}
}
4.梳排序 Comb sort
算法(参考维基百科：http://en.wikipedia.org/wiki/Comb_sort)：
算法主要针对冒泡排序中兔子乌龟问题(和鸡尾酒排序想解决的问题一致)进行优化，消灭序列中的乌龟，因为乌龟是导致冒泡排序算法效率降低的主要原因。冒牌排序，以及鸡尾酒排序，奇偶排序中，进行比较和交换的两个元素之间的距离(gap)都是1，即只在相邻位置进行交换。梳排序的关键思想就是改变这个进行比较和交换的元素之间的距离，这个距离在每次循环过程中通过一个收缩率因子(shrink factor)进行改变使距离逐渐降低到1。
特点：
1.算法作者指出收缩率因子为1.3时效果是最好的(兼顾比较的次数多少和能否有效的消除序列中的乌龟现象)。(另一个收缩率因子1.24733...可参考维基百科：http://zh.wikipedia.org/wiki/梳排序)
2.梳排序的效率在开始时最佳，接近结束时效率最差。一种可优化的方式是当进行比较和交换的两个元素之间的距离(gap)小于某个阈值时，改用其他排序算法(如插入排序和鸡尾酒排序)以提高性能。对于规模n比较大和序列本身比较乱序的数据，梳排序算法要比冒泡排序高效得多。
3.属于不稳定型算法，相等的两个元素，执行算法时可能在不同gap值循环时使他们的前后顺序发生改变。
4.属于比较排序算法。
5.原址的(in place)，辅助空间复杂度O(1)。
6.时间复杂度：最优：O(n)，此时原始序列已顺序排列；最差：O(n^2)，此时原始序列逆序排列；平均：。
算法C实现(代码要注意gap相关的边界条件):
void comb_sort(TYPE* array, TYPE count)
{
TYPE i, temp;
TYPE flag_repeat = 1;
/// initialize gap size
TYPE gap = count;
/// set gap shrink factor
double shrink = 1.3;
/// repeated until no swaps
while (gap != 1 || flag_repeat) {
/// update gap from shrink
if (gap > 1) ///< minimum gap = 1
gap /= shrink;
flag_repeat = 0;
for (i = 0; i < count - gap; i++) {
/// compares 'comb' items and swaps them if in wrong order.
if (array[i] > array[i + gap]) {
temp = array[i];
array[i] = array[i + gap];
array[i + gap] = temp;
flag_repeat = 1;
}
}
}
}
拓展：梳排序修改gap值的思想与希尔排序的思想一致，可以相互比较进行学习。
5.侏儒排序/地精排序 gnome sort
算法(参考： http://www.dickgrune.com/Programs/gnomesort.html 及维基百科：http://en.wikipedia.org/wiki/Gnome_sort)：
It is a sorting algorithm which is similar to insertion sort, except that moving an element to its proper place is accomplished by a series of swaps, as in bubble sort. It is conceptually simple, requiring no nested loops.
Gnome Sort is based on the technique used by the standard Dutch Garden Gnome. Here is how a garden gnome sorts a line of flower pots. Basically, he looks at the flower pot next to him and the previous one; if they are in the
right order he steps one pot forward, otherwise he swaps them and steps one pot backwards. Boundary conditions: if there is no previous pot, he steps forwards; if there is no pot next to him, he is done.
实现：
这个算法在交换元素时和冒泡排序方法一致，也是比较和交换相邻元素，与冒泡排序区别在于：地精排序从序列起始位置到序列末尾位置的前进过程中，不断进行比较，只要发生元素交换现象就退回一步（往序列起始位置方向），直到没有发生交换现象再冒泡前进，到达序列末尾时结束。
特点：
1.各方面特点与冒泡排序特点(上文1，2，3，4，5点)一致。
2.地精排序不需要像冒泡排序那样通过判断有无发生数据交换来结束算法，而是通过判断是否到达序列尾部来结束算法。
3.与前面算法相比，地精排序和鸡尾酒排序一样，解决了冒泡排序的乌龟问题，但是也把兔子给一并消除了。
算法C实现(注意防止i下界溢出；优化：如果前进过程中在某位置交换元素并退回了，从停止进行交换开始，再次前进到该位置前是不需要再进行比较的，因为由于先前的交换已经能够得到它们的大小关系信息了，基于这个想法可对上面的算法进行优化。(The gnome sort may be optimized by introducing a variable to store the position
before traversing back toward the beginning of the list. This would allow the "gnome" to teleport back to his previous position after moving a flower pot. With this optimization, the gnome sort would become a variant of the insertion sort. )
void gnome_sort(TYPE* array, TYPE count)
{
TYPE i = 0, temp;
TYPE pos_last = 0;
/// repeated until move to end
while (i < count - 1) {
if (array[i] <= array[i + 1]) {
/// if have saved position before, set to it.
if (pos_last != 0) {
DEBUG_PRINT_STRING("last pos get.\n");
DEBUG_PRINT_VALUE("%d", pos_last);
i = pos_last;
pos_last = 0;
}
/// move forward
i++;
} else {
/// swap and move backward
temp = array[i];
array[i] = array[i + 1];
array[i + 1] = temp;
/// i can not smaller than 0
if (i > 0) {
/// save position at first time
if (pos_last == 0) {
DEBUG_PRINT_STRING("last pos set.\n");
DEBUG_PRINT_VALUE("%d", pos_last);
pos_last = i;
}
/// move backward
i--;
} else {
i++;
}
}
}
}
6.快速排序 quicksort
算法及实现(详细可参考《算法导论》中第七章快速排序及维基百科： http://en.wikipedia.org/wiki/Quicksort)：
快速排序采用了分治策略(分治法 divide and conquer)，关键的思想是通过partition把一个数组成功处理并划分为左中右三部分：小于或等于主元(pivot)的子数组;主元(单个)，大于主元的子数组，子数组由主元隔离，并返回主元的位置。
1.Pick an element, called a pivot, from the array.
2.Reorder the array so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position.
This is called the partition operation.
3.Recursively apply the above steps to the sub-array of elements with smaller values and separately to the sub-array of elements with greater values.
特点：
1.属于不稳定型算法，相等的两个元素，执行算法时递归中的partition操作可能使他们的顺序发生改变。
2.属于比较排序算法。
3.可以实现为原址的(in place)，辅助空间复杂度为O(logn)，这里考虑了递归过程中使用的堆栈。这里值得一提的是归并排序也使用了分治的思想，但是辅助空间复杂度为O(n)。
4.时间复杂度：最优：O(nlgn)，此时递归过程中partition都把数组均分为两个相等长度（或差1）的子数组；最差：O(n^2)，此时原序列已顺序或逆序排列，出现可能性很小；平均：O(nlgn)，因为partition对数组进行常数比例的划分，根据递归方程，都会使运行时间趋近于O(nlgn)。
5.快速排序的平均运行时间更接近于最好情况，而非最坏情况。
6.Quicksort is often faster in practice than other O(n log n) algorithms.（维基百科提出）
算法C实现(代码的一个分析：比较元素大小时若使用小于等于号若用小于号代替，那么partition划分后的右边子数组存的值为大于等于（而不是大于）主元的元素，左边子数组存的值为小于（而不是小于等于）主元的元素，partition操作选用的主元为待处理数组中末尾的元素，这也是可以的。在《算法导论》中使用的是小于等于号，而维基百科代码实现中使用的是小于，个人更倾向于小于号，毕竟较少了一个等于的判断，从而一定程度减少了相同元素之间的交换):
/**
* @brief select the last element as a pivoit.
* Reorder the array so that all elements with values less than the pivot
* come before the pivot, while all elements with values greater than the pivot
* come after it (equal values can go either way). After this partitioning, the
* pivot is in its final position.
*
* @param[in,out] array input and output array
* @param[in] index_begin the begin index of the array(included)
* @param[in] index_end the end index of the array(included)
*
* @return the position of the pivot(index from the array)
*/
TYPE partition(TYPE* array, TYPE index_begin, TYPE index_end)
{
/// pick last element of the array as the pivot
TYPE pivot = array[index_end];
/// index of the elments that not greater than pivot
TYPE i = index_begin - 1;
TYPE j, temp;
/// check array's elment one by one
for (j = index_begin; j < index_end; j++) {
if (array[j] <= pivot) {
/// save the elements not greater than pivot to left index of i.
i++;
temp = array[j];
array[j] = array[i];
array[i] = temp;
}
}
/// set the pivot to the right position
array[index_end] = array[++i];
array[i] = pivot;
/// return the position of the pivot
return i;
}
void quick_sort(TYPE* array, TYPE index_begin, TYPE index_end)
{
/// sort only under the index_begin < index_end condition
if ( index_begin < index_end) {
/// exchange elements to the pivot position by partition function
TYPE index_pivot = partition(array, index_begin, index_end);
/// sort the array before the pivot position
quick_sort(array, index_begin, index_pivot - 1);
/// sort the array after the pivot position
quick_sort(array, index_pivot + 1, index_end);
}
}
算法拓展：
随机化的快速排序算法（partition操作选用的主元通过随机抽样(randomize)来获得（实现中调用C标准库中rand()函数），而不是待处理数组中末尾的元素，使得算法对于所有的输入都能够获得较好的期望性能（随机抽样效果好的话可以使原始序列为顺序和逆序的数组也能获得O(nlgn)的运行时间性能）
拓展（总结自维基百科）：
C标准库中的qsort函数采用的排序方法就是快速排序（q取自Quicksort首字母）。
关于主元pivot的选择：除了可以选择序列中最后一个元素或随机元素作为主元之外，也可以选择序列的中间元素，或者选择序列的首元素，中间元素，尾元素三个数的中位数（这个非常适用于未知原始序列信息的情况）。
序列中存在过多重复元素时（维基百科抽象了问题，可学习： Dutch national flag problem）：此时快速排序性能变差。解决这个问题的方法是使partition输出两个位置(left, right)，把序列分成三部分：小于主元的子数组和截止位置left，等于主元的子数组（可能单个），大于主元的子数组和起始位置。最典型的例子是原始序列所有元素均相等，这个方法将有很好的性能。
优化一：一次递归中顺序执行的两个子数组递归，可以让他们开辟的辅助空间共用来严格保证辅助空间复杂度为O(lgn)(To make sure at most O(log n) space is used, recurse first into the smaller side of the partition, then use a tail call to recurse into the other.)。
优化二：递归到一定程度时不使用partition而使用插入排序算法(Use insertion sort, which has a smaller constant factor and is thus faster on small arrays, for invocations on small arrays.)。
优化三：采用并行处理技术。
7.交换排序的其他算法：
BogoSort: Bogo排序，可参考维基百科。
StoogeSort: 臭皮匠排序，可参考维基百科。
8.交换算法之间比较：
排序算法之间进行比较时参考：
输入数据特点：顺序，逆序，随机乱序，局部乱序；
输入规模n：时间复杂度，空间复杂度；
排序性质：稳定性，思想方法；