/*
* 归并排序。迭代版
* @param: {int []} arr
* @param: {int} len
* @return null;
*/
void MergeSort_1 (int arr[], int len) {
int* a = arr;
int* b = (int*) malloc(len * sizeof(int));
int seg, start;
for (seg = 1; seg < len; seg += seg) {
for (start = 0; start < len; start += seg + seg) {
int low = start, mid = Min (start + seg, len), high = Min(start + seg + seg, len);
int k = low;
int start1 = low, end1 = mid;
int start2 = mid, end2 = high;
while (start1 < end1 && start2 < end2)
b[k++] = a[start1] < a[start2] ? a[start1++] : a[start2++];
while (start1 < end1)
b[k++] = a[start1++];
while (start2 < end2)
b[k++] = a[start2++];
}
int* temp = a;
a = b;
b = temp;
}
if (a != arr) {
int i;
for (i = 0; i < len; i++)
b[i] = a[i];
b = a;
}
free(b);
}
int Min(int x, int y) {
return x < y ? x : y;
}
/*
* 归并排序。递归版
* @param: {int []} arr
* @param: {const int} len
* @return null;
*/
void MergeSort_2 (int arr[], const int len) {
int reg[len];
merge_sort_recursive(arr, reg, 0, len - 1);
}
void merge_sort_recursive (int arr[], int reg[], int start, int end) {
if (start >= end)
return;
int len = end - start, mid = (len >> 1) + start;
int start1 = start, end1 = mid;
int start2 = mid + 1, end2 = end;
merge_sort_recursive(arr, reg, start1, end1);
merge_sort_recursive(arr, reg, start2, end2);
int k = start;
while (start1 <= end1 && start2 <= end2)
reg[k++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];
while (start1 <= end1)
reg[k++] = arr[start1++];
while (start2 <= end2)
reg[k++] = arr[start2++];
for (k = start; k <= end; k++)
arr[k] = reg[k];
}
总结【上】
这篇文章“十大经典排序算法及其 C 语言实现【上】”引出了十大经典算法的前五个并用 C 语言实践：冒泡排序、选择排序、插入排序、希尔排序和归并排序，并作出了充足的图文解释。即将推出的“十大经典排序算法及其 C 语言实现【下】”将对剩下五个经典算法快速排序、堆排序、计数排序、桶排序、基数排序作出完善，尽请期待~。
期中已到，期末将至。《算法设计与分析》的“预习”阶段藉此开始~。在众多的算法思想中，如果你没有扎实的数据结构的功底，不知道栈与队列，哈希表与二叉树，不妨可以从排序算法开始练手。纵观各类排序算法，常见的、经典的排序算法将由此篇引出。
排序算法的输出必须遵守的下列两个原则：
十大经典的排序算法及其时间复杂度和稳定性如上表所示。判断一个排序算法是否稳定是看在相等的两个数据排序算法执行完成后是否会前后关系颠倒，如若颠倒，则称该排序算法为不稳定，例如选择排序和快速排序。
00.交换两个整数的值
接下来十个经典排序算法的详细探讨缺少不了交换两个整数值的掌握，这里回顾一下其中三种方交换法：用临时变量交换两个整数的值(SwapTwo_1)、不用第三方变量交换两个整数的值(SwapTwo_2)、使用位运算交换两个整数的值(SwapTwo_3)。其中用临时变量交换两个整数的值效率最高，后俩者只适用于内置整型数据类型的交换，并不高效。
01. 冒泡排序(BubbleSort)
先不说公司面试笔试，大学实验室的纳新题里最常有的就是冒泡排序。冒泡排序重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。由于它的简洁，冒泡排序通常被用来对于程序设计入门的学生介绍算法的概念。
上图可见，冒泡排序算法的运作如下：
通俗来讲，整个冒泡排序就是通过两次循环，外层循环将此轮最大(小)值固定到此轮尾部，内层循环“冒泡”比较相邻的两个元素并决定是否交换位置。
从上图也可理解冒泡排序如何将每一轮最大（小）值固定到此轮尾部：尾部总为有序状态，前面无序状态区根据大小规则冒泡向后方传递最值。
02. 选择排序(SelectionSort)
选择排序首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
选择排序的主要优点与数据移动有关。如果某个元素位于正确的最终位置上，则它不会被移动。选择排序每次交换一对元素，它们当中至少有一个将被移到其最终位置上，因此对n个元素的表进行排序总共进行至多n-1次交换。在所有的完全依靠交换去移动元素的排序方法中，选择排序属于非常好的一种。
上图左下角和右上角可以分别看做排序序列起始位置(已排序区)和排序序列末尾(未排序区)，左下角一直稳定更新，但选择排序不稳定，即排序后曾经相同的两个元素的前后位置关系可能会发生颠倒。
03. 插入排序(InsertionSort)
插入排序的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用 in-place 排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
一般来说，插入排序都采用 in-place 在数组上实现。具体算法描述如下：
如果比较操作的代价比交换操作大的话，可以采用二分查找法来减少比较操作的数目。该算法可以认为是插入排序的一个变种，称为二分查找插入排序。这里先不做涉及。
04. 希尔排序(ShellSort)
希尔排序按其设计者希尔（Donald Shell）的名字命名，该算法由1959年公布。希尔排序也称递减增量排序算法，是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。希尔排序是基于插入排序的以下两点性质而提出改进方法的：
希尔排序通过将比较的全部元素分为几个区域来提升插入排序的性能。这样可以让一个元素可以一次性地朝最终位置前进一大步。然后算法再取越来越小的步长进行排序，算法的最后一步就是普通的插入排序，但是到了这步，需排序的数据几乎是已排好的了（此时插入排序较快）。
步长的选择是希尔排序的重要部分。只要最终步长为1任何步长序列都可以工作。算法最开始以一定的步长进行排序。然后会继续以一定步长进行排序，最终算法以步长为1进行排序。当步长为1时，算法变为插入排序，这就保证了数据一定会被排序。
已知的最好步长序列是由 Sedgewick 提出的(1, 5, 19, 41, 109,...)，这项研究也表明“比较在希尔排序中是最主要的操作，而不是交换。”用这样步长序列的希尔排序比插入排序要快，甚至在小数组中比快速排序和堆排序还快，但是在涉及大量数据时希尔排序还是比快速排序慢。
05. 归并排序(MergeSort)
归并排序是创建在归并操作上的一种有效的排序算法，效率为 O(n log n)。1945年由约翰·冯·诺伊曼首次提出。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。
归并操作（merge），也叫归并算法，指的是将两个已经排序的序列合并成一个序列的操作。归并排序算法依赖归并操作。
归并排序用迭代法和递归法都可以实现，迭代法的算法步骤为：
递归法的算法步骤为：
总结【上】
这篇文章“十大经典排序算法及其 C 语言实现【上】”引出了十大经典算法的前五个并用 C 语言实践：冒泡排序、选择排序、插入排序、希尔排序和归并排序，并作出了充足的图文解释。即将推出的“十大经典排序算法及其 C 语言实现【下】”将对剩下五个经典算法快速排序、堆排序、计数排序、桶排序、基数排序作出完善，尽请期待~。