数据结构（二）
这是卡尼慕的第n篇文章
上篇复习了一下数据结构的基本概念和常识，那么今天来复习一下几种常见的排序算法。
首先了解一下排序的一个特性：稳定性。
稳定性是指相同元素在排序后相对位置保持不变。
稳定性的意义
如果只是简单的进行数字的排序，那么稳定性将毫无意义。
如果排序的内容仅仅是一个复杂对象的某一个数字属性，那么稳定性依旧将毫无意义。
如果要排序的内容是一个复杂对象的多个数字属性，但是其原本的初始顺序毫无意义，那么稳定性依旧将毫无意义。
冒泡bubububu~
冒泡算法是最最最最基础的排序算法。小的往左移动，大的往右，整个过程就像是水中气泡上浮。在相邻两个元素的比较中，如果相等，则没有必要交换。
这一点，保证了冒泡排序的稳定性。它的思路也非常简单，使用了两层for循环。第一层循环是遍历整个数组，第二层是比较两两相邻的数。
void BubbleSorting(int a[] , int n)
{
for(int i = 0; i < n-1; i++)
{
for(int j = 0; j < n-1-i; j++)
{
if(a[j] > a[j+1])
{
int tmp = a[j];
a[j] = a[j+1];
a[j+1] = tmp;
}
}
}
}快速排序
这里引荐一篇大牛的文章，看了简直是醍醐灌顶，哈哈，坐在马桶上看算法：快速排序。
方法其实很简单：分别从初始序列“6 1 2 7 9 3 4 5 10 8”两端开始“探测”。先从右往左找一个小于6的数，再从左往右找一个大于6的数，然后交换他们。这里可以用两个变量i和j，分别指向序列最左边和最右边。我们为这两个变量起个好听的名字“哨兵i”和“哨兵j”。刚开始的时候让哨兵i指向序列的最左边（即i=1），指向数字6。让哨兵j指向序列的最右边（即=10），指向数字。
首先哨兵j开始出动。因为此处设置的基准数是最左边的数，所以需要让哨兵j先出动，这一点非常重要（请自己想一想为什么）。哨兵j一步一步地向左挪动（即j--），直到找到一个小于6的数停下来。接下来哨兵i再一步一步向右挪动（即i++），直到找到一个数大于6的数停下来。最后哨兵j停在了数字5面前，哨兵i停在了数字7面前。
现在交换哨兵i和哨兵j所指向的元素的值。交换之后的序列如下：
6 1 2 5 9 3 4 7 10 8
到此，第一次交换结束。接下来开始哨兵j继续向左挪动（再友情提醒，每次必须是哨兵j先出发）。他发现了4（比基准数6要小，满足要求）之后停了下来。哨兵i也继续向右挪动的，他发现了9（比基准数6要大，满足要求）之后停了下来。此时再次进行交换，交换之后的序列如下：
6 1 2 5 4 3 9 7 10 8
第二次交换结束，“探测”继续。哨兵j继续向左挪动，他发现了3（比基准数6要小，满足要求）之后又停了下来。哨兵i继续向右移动，糟啦！此时哨兵i和哨兵j相遇了，哨兵i和哨兵j都走到3面前。说明此时“探测”结束。我们将基准数6和3进行交换。交换之后的序列如下：
3 1 2 5 4 6 9 7 10 8
void QuickSort(int a[] , int left ,int right)
{
if(left > right)
{
return;
}
int i , j ,tmp;
i = left;
j = right;
tmp = a[left]; //哨兵
6
while(i != j) //哨兵不能碰面
{
while(a[j] <= tmp && i < j) //先移动右边的哨兵
{
j--;
}
while(a[i] >= tmp && i < j)
{
i++;
}
if(i < j)
{
int k = a[i];
a[i] = a[j];
a[j] = k;
}
}
a[left] = a[j];
a[j] = tmp;
QuickSort(a ,left,i-1);
QuickSort(a ,i+1,right);
}选择排序
选择排序的思路也特别容易好想，就是先遍历整个数组，找到最小值，把最小值丢到最前面，然后选取第二个数作为首项，再找最小值，逐步排号顺序。
void ChoiceSort(int a[] , int N)
{
for (int i = 0; i < N; i++)
{
int k = i;
for (int j = k + 1; j < N; j++)
{
if (a[j] < a[k])
{
k = j;
}
}
//找到了最小的值再交换
int temp = a[i];
a[i] = a[k];
a[k] = temp;
}
}插入排序
插入排序的思路也不难，就可以简单的类比于我们整理扑克牌一样，现在左手上那一张牌，然后从牌堆中随便选取一张牌，按照大小插入左手已经有序的牌中，逐一类推。
从代码方面考虑，为了使代码更方便可行，一般直接按照顺序选取下一个未排序的元素作为待插入的牌。
void InsertSort(int a[] ,int N)
{
//从第二个元素开始，加入第一个元素是已排序数组
for (int i = 1; i < N; i++){
//待插入元素 array[i]
if (a[i] < a[i - 1]){
int wait = a[i];
int j = i;
while (j > 0 && a[j - 1] > wait){
//从后往前遍历已排序数组，若待插入元素小于遍历的元素，则遍历元素向后挪位置
a[j] = a[j - 1];
j--;
}
a[j] = wait;
}
}
}归并排序
归并排序是把序列递归地分成短序列，递归出口是短序列只有1个元素（认为直接有序）或者2个序列（1次比较和交换），然后把各个有序的段序列合并成一个有序的长序列，不断合并直到原序列全部排好序。可以发现，在1个或2个元素时，1个元素不会交换，2个元素如果大小相等也没有人故意交换，这不会破坏稳定性。那么，在短的有序序列合并的过程中，稳定是是否受到破坏？没有，合并过程中我们可以保证如果两个当前元素相等时，我们把处在前面的序列的元素保存在结果序列的前面，这样就保证了稳定性。
void Merge(int *arr, int n)
{
int temp[n]; // 辅助数组
int b = 0; // 辅助数组的起始位置
int mid = n / 2; // mid将数组从中间划分，前一半有序，后一半有序
int first = 0, second = mid; // 两个有序序列的起始位置
while (first < mid && second < n)
{
if (arr[first] <= arr[second]) // 比较两个序列
temp[b++] = arr[first++];
else
temp[b++] = arr[second++];
}
while(first < mid) // 将剩余子序列复制到辅助序列中
temp[b++] = arr[first++];
while(second < n)
temp[b++] = arr[second++];
for (int i = 0; i < n; ++i) // 辅助序列复制到原序列
arr[i] = temp[i];
}
void MergeSort(int* s, int Num)
{
if(n <= 1) //递归法的出口
return;
if(n > 1)
{
MergeSort(a ,n/2);
MergeSort(a + n/2 ,n - n/2);
Merge(a , n); //归并两部分
}
}