冒泡排序、归并排序、快速排序，一个个名词耳熟能详，听吴军老师娓娓道来，仍有不少额外的收获，记录分享如下。
对于冒泡排序，原理很简单，就是每次找到无序数据中的最大值，直到排序完成，步骤如下：
1.比较相邻的元素。如果第一个比第二个大，就交换他们两个；
2.对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数；
3.针对所有的元素重复以上的步骤，除了最后一个；
4.持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
算法复杂度为O(n2)，用C语言实现如下：
void bubble_sort(int a[], int n)
{
int i, j, temp;
for (j = 0; j < n - 1; j++)
for (i = 0; i < n - 1 - j; i++)
{
if(a[i] > a[i + 1])
{
temp = a[i];
a[i] = a[i + 1];
a[i + 1] = temp;
}
}
}
归并排序的原理是将无序数据分堆，找出每一堆的序列，然后合并得到一个完整的有序序列，步骤如下：
1.申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
2.设定两个指针，最初位置分别为两个已经排序序列的起始位置；
3.比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
4.重复步骤3直到某一指针超出序列尾；
5.将另一序列剩下的所有元素直接复制到合并序列尾。
算法复杂度为nlog(n)，C语言实现如下：
void Merge(int sourceArr[],int tempArr[], int startIndex, int midIndex, int endIndex)
{
int i = startIndex, j=midIndex+1, k = startIndex;
while(i!=midIndex+1 && j!=endIndex+1)
{
if(sourceArr[i] > sourceArr[j])
tempArr[k++] = sourceArr[j++];
else
tempArr[k++] = sourceArr[i++];
}
while(i != midIndex+1)
tempArr[k++] = sourceArr[i++];
while(j != endIndex+1)
tempArr[k++] = sourceArr[j++];
for(i=startIndex; i<=endIndex; i++)
sourceArr[i] = tempArr[i];
}
//内部使用递归
void MergeSort(int sourceArr[], int tempArr[], int startIndex, int endIndex)
{
int midIndex;
if(startIndex < endIndex)
{
midIndex = (startIndex + endIndex) / 2;
MergeSort(sourceArr, tempArr, startIndex, midIndex);
MergeSort(sourceArr, tempArr, midIndex+1, endIndex);
Merge(sourceArr, tempArr, startIndex, midIndex, endIndex);
}
}
快速排序的原理是通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。步骤如下：
1.设置两个变量i、j，排序开始的时候：i=0，j=N-1；
2.以第一个数组元素作为关键数据，赋值给key，即key=A[0]；
3.从j开始向前搜索，即由后开始向前搜索(j--)，找到第一个小于key的值A[j]，将A[j]和A[i]互换；
4.从i开始向后搜索，即由前开始向后搜索(i++)，找到第一个大于key的A[i]，将A[i]和A[j]互换；
5.重复第3、4步，直到i=j； (3,4步中，没找到符合条件的值，即3中A[j]不小于key,4中A[i]不大于key的时候改变j、i的值，使得j=j-1，i=i+1，直至找到为止。找到符合条件的值，进行交换的时候i， j指针位置不变。另外，i==j这一过程一定正好是i+或j-完成的时候，此时令循环结束）。
这个算法的复杂度一般也是nlog(n)，C语言实现如下：
void sort(int *a, int left, int right)
{
int i = left;
int j = right;
int key = a[left];
if(left >= right)/*如果左边索引大于或者等于右边的索引就代表已经整理完成一个组了*/
{
return ;
}
while(i < j) /*控制在当组内寻找一遍*/
{
while(i < j && key <= a[j])
/*而寻找结束的条件就是，1，找到一个小于或者大于key的数（大于或小于取决于你想升
序还是降序）2，没有符合条件1的，并且i与j的大小没有反转*/
{
j--;/*向前寻找*/
}
a[i] = a[j];
/*找到一个这样的数后就把它赋给前面的被拿走的i的值（如果第一次循环且key是
a[left]，那么就是给key）*/
while(i < j && key >= a[i])
/*这是i在当组内向前寻找，同上，不过注意与key的大小关系停止循环和上面相反，
因为排序思想是把数往两边扔，所以左右两边的数大小与key的关系相反*/
{
i++;
}
a[j] = a[i];
}
a[i] = key;/*当在当组内找完一遍以后就把中间数key回归*/
sort(a, left, i - 1);/*最后用同样的方式对分出来的左边的小组进行同上的做法*/
sort(a, i + 1, right);/*用同样的方式对分出来的右边的小组进行同上的做法*/
/*当然最后可能会出现很多分左右，直到每一组的i = j 为止*/
}
作为一个码农，排序的事情经常做，却对其本质知之甚少。
排序算法的效率提高，在于它少做了很多并不需要做的比较。效率＝产出／所做的事情。人的产出是很难提高的，但是所做的事情是可以减少的。强调工程师水平差一级，贡献可能就差出10倍。在农耕文明时代，没有力气的人最不济也能产生壮劳力1/3的生产力。在工业时代，靠手工一件件生产商品，可能效率能有机器的1%。但是到了智能时代，本事差一点，效果可能差几百万倍，几亿倍，专业和不专业就差得更远了。
罗胖跨年演讲说，人生即算法。人的总时间和注意力都相差不多，关键在于如何取舍，并且在核心方面最好最后的1%。
