李肖遥来源
技术让梦想更伟大冒泡排序简介冒泡排序是因为越小的元素会经由交换以升序或降序的方式慢慢浮到数列的顶端，就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名冒泡排序。复杂度与稳定性思路原理以顺序为例从第一个元素开始一个一个的比较相邻的元素，如果第一个比第二个大即a[1]a[2]，就彼此交换。从第一对到最后一对，对每一对相邻元素做一样的操作。此时在最后的元素应该会是最大的数，我们也称呼一遍这样的操作为一趟冒泡排序。针对所有的元素重复以上的步骤，每一趟得到的最大值已放在最后，下一次操作则不需要将此最大值纳入计算。持续对每次对越来越少的元素，重复上面的步骤。直到所有的数字都比较完成符合aa[i+1]，即完成冒泡排序。图示过程以数组数据{70,50,30,20,10,70,40,60}为例：如图，每一次排序把一个最大的数被放在了最后，然后按照这个趋势逐渐往前，直到按从小到大的顺序依次排序。到了第4轮的时候，整个数据已经排序结束了，但此时程序仍然在进行。直到第5，6，7轮程序才算真正的结束，这其实是一种浪费算力的表现。主要代码实现voidbubble_sort(inta[],intn){for(inti=0;in;i++){for(intj=0;jn-i;j++){if(a[j]a[j+1]){swap(a[j],a[j+1]);//交换数据}}}}注意，由于C++的namespacestd命名空间的使用，std自带了交换函数swap(a,b)，可以直接使用，其功能是交换a与b的两个值，当然你可以自定义swap函数，其模板代码为：templateclassT//模板类，可以让参数为任意类型voidswap(Ta,Tb){Tc(a);a=b;b=c;}或者指定类型修改为整形，如：voidswap(inta,intb){//指定类型inttemp=a;a=b;b=temp;}选择排序简介选择排序是一种简单直观的排序算法，它从待排序的数据元素中选出最小或最大的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小或最大元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。复杂度与稳定性过程介绍（以顺序为例）首先设置两个记录i和j，i从数组第一个元素开始，j从(i+1)个元素开始。接着j遍历整个数组，选出整个数组最小的值，并让这个最小的值和i的位置交换。i选中下一个元素(i++)，重复进行每一趟选择排序。持续上述步骤，使得i到达(n-1)处，即完成排序。图示过程：以数据{2,10,9,4,8,1,6,5}为例如图所示，每次交换的数据使用红颜色标记出，已经排好序的数据使用蓝底标注，每一趟从待排序的数据元素中选出最小的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。我们只需要进行n-1趟排序即可，因为最后剩下的一个数据一定是整体数据中最大的数据。代码实现voidselect_sort(inta[],intn){inttemp;for(inti=0;in-1;i++){temp=i;//利用一个中间变量temp来记录需要交换元素的位置for(intj=i+1;jn;j++){if(a[temp]a[j]){//选出待排数据中的最小值temp=j;}}swap(a,a[temp]);//交换函数}}相比冒泡排序的不断交换，简单选择排序是等到合适的关键字出现后再进行交换，并且交换一次就可以达到一次冒泡的效果。插入排序简介插入排序是一种最简单的排序方法，对于少量元素的排序，它是一个有效的算法。复杂度与稳定性过程介绍首先将一个记录插入到已经排好序的有序表中，从而一个新的、记录数增1的有序表。每一步将一个待排序的元素，按其排序码的大小，插入到前面已经排好序的一组元素的适当位置上去，直到元素全部插入为止。可以选择不同的方法在已经排好序数据表中寻找插入位置。根据查找方法不同，有多种插入排序方法，下面要介绍的是直接插入排序。每次从无序表中取出第一个元素，把它插入到有序表的合适位置，使有序表仍然有序。第一趟比较前两个数，然后把第二个数按大小插入到有序表中；第二趟把第三个数据与前两个数从后向前扫描，把第三个数按大小插入到有序表中；依次进行下去，进行了(n-1)趟扫描以后就完成了整个排序过程。图示过程以数组数据{70,50,30,20,10,70,40,60}为例：将红色的数据依次插入组成一个逐渐有序的数组代码实现voidinsert_sort(inta[],intn){inti,j;//外层循环标识并决定待比较的数值for(i=1;in;i++){//循环从第2个元素开始if(aa[i-1]){inttemp=a;//待比较数值确定其最终位置for(j=i-1;j=0a[j]temp;j--){a[j+1]=a[j];}a[j+1]=temp;//此处就是a[j+1]=temp;}}}希尔排序简介希尔排序又称缩小增量排序，是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法，在对几乎已经排好序的数据操作时，效率极高，即可以达到线性排序的效率。复杂度与稳定性过程介绍先将整个待排序的记录序列分组，对若干子序列分别进行直接插入排序，随着增量逐渐减少即整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。过程如下：选择一个增量序列t1，t2，……，tk，其中titj,tk=1；按增量序列个数k，对序列进行k趟排序；每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m的子序列，分别对各子表进行直接插入排序。仅增量因子为1时，整个序列作为一个表来处理，表长度即为整个序列的长度。图示过程可以看见，相比直接插入排序由于可以每趟进行分段操作，故整体效率体现较高。主要代码实现voidshellSort(intarr[],intn){inti,j,gap;for(gap=n/2;gap0;gap/=2){for(i=0;igap;i++){for(j=i+gap;jn;j+=gap){for(intk=j;kiarr[k]arr[k-gap];k-=gap){swap(arr[k-gap],arr[k]);}}}}}堆排序简介堆排序是指利用堆这种数据结构所设计的一种排序算法，它是一个近似完全二叉树的结构。同时堆满足堆积的性质：即子结点的键值或索引总是小于或大于它的父节点。复杂度与稳定性什么是堆？由于堆排序比较特殊，我们先了解一下堆是什么。堆是一种非线性的数据结构，其实就是利用完全二叉树的结构来维护的一维数组，利用这种结构可以快速访问到需要的值，堆可以分为大顶堆和小顶堆。大顶堆：每个结点的值都大于或等于其左右孩子结点的值小顶堆：每个结点的值都小于或等于其左右孩子结点的值过程介绍首先把待排序的元素按照大小在二叉树位置上排列，且要满足堆的特性，如果根节点存放的是最大的数，则叫做大根堆，反之就叫做小根堆了。根据这个特性就可以把根节点拿出来，然后再堆化下，即用父节点和他的孩子节点进行比较，取最大的孩子节点和其进行交换，再把根节点拿出来，一直循环到最后一个节点，就排序好了。由于堆的实现图解需要很长篇幅，故这里不画图，肖遥会单独出一篇堆的图解，感谢