c++排序算法
前言
我相信再看这篇文章的童鞋已经学完语言部分了吧。
学完语言后就应该学习算法，而最先应该学的算法就是排序
虽然排序函数（sort）可以解决一切问题，但是这种（好）东西并不是万能的，在某些题目中，不仅需要记录排序后的答案，还需要记录排序过程（例如排序的次数）
所以要想学到排序思想就只有一个办法：
乖乖的写几遍代码理解、背过
下面正式开启文章内容
一、算法概述
十大常见算法基本上就可以分成两类了
非线性时间比较类排序：通过比较来决定元素间的相对次序，称为非线性时间比较类排序。
线性时间非比较类排序：不通过比较来决定元素间的相对次序，以线性时间运行，称为线性时间非比较类排序。
下面这个图就可以清楚地分类：
思维导图好
下面就是各种排序算法的复杂度和是否稳定的表格。
Excel好
下面是注释：
稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。（会交换）
不稳定：如果a原本在b的前面，而a=b，排序之后 a 可能会出现在 b 的后面。（不会交换）
时间复杂度：对排序数据的总的操作次数。反映当n变化时，操作次数呈现什么规律。
空间复杂度：是指算法在计算机内执行时所需存储空间的度量，它也是数据规模n的函数。
在这里我就不一一给大家讲解各种算法了，我会挑5个给大家简单讲解。
二、算法讲解
1.冒泡排序
我偷偷和大家说一下，本蒟蒻第一个学习的排序算法就是冒泡排序。
***************************************************************
//整数或浮点数皆可使用 void Sort(a[], int len) { int i, j,temp; for (i = 0; i < len - 1; i++) for (j = 0; j < len - 1 - i; j++) if (a[j] > a[j + 1]) { temp = a[j]; arr[j] = a[j + 1]; a[j + 1] = temp; } }
代码已经给您找来了，其中的Sort函数即为排序过程。
2.桶排序
为什么第二个就要学习桶排序嘞？
因为简单
***************************************************************
桶排序或所谓的箱排序，是一个排序算法，工作的原理是将数组分到有限数量的桶子里，每个桶子再个别排序。
***************************************************************
使用方法：
把每一个数字放在对应下标的“桶”中。
从头输出“桶”的下标。
***************************************************************
这是一种牺牲空间保空间的做法，数字有多大，就要开多大的数组。
并且不支持浮点数。
时间复杂度是O（n+c）
上代码！
void Sort(int a[],int len) { int x=0; for(int i=1;i<=len;i++) { b[a[i]]++; x=max(x,a[i]) } for(int i=0;i<=x;i++) { if(b[i]>=0) { while(b[i]!=0) { b[i]--; cout<<i; } } } }
代码已经给您找来了，其中的Sort函数即为排序过程。
3.归并排序
***************************************************************
归并排序是将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。
***************************************************************
***************************************************************
这是一种比较不错的方法，这个方法也会分为几种：二路归并和多路归并。
这种方法也是利用了分治的方法，也就是分而治之。
大家可以看一看下面的这个图：（来源：百度百科）
上代码！
void Merge(int* data,int a,int b,int length,int n) { int right; if(b+length-1 >= n-1) right=n-b; else right=length; int* temp=new int[length+right]; int i=0,j=0; while(i<=length-1&&j<=right-1) { if(data[a+i]<=data[b+j]) { temp[i+j]=data[a+i];i++; } else { temp[i+j]=data[b+j]; j++; } } if(j == right) {//a中还有元素，且全都比b中的大,a[i]还未使用 memcpy(temp + i + j, data + a + i, (length - i) * sizeof(int)); } else if(i == length) { memcpy(temp + i + j, data + b + j, (right - j)*sizeof(int)); } memcpy(data+a, temp, (right + length) * sizeof(int)); delete [] temp; } void MergeSort(int* data, int n) { int step = 1; while(step<n) { for(int i=0;i<=n-step-1;i+=2*step) Merge(data,i,i+step,step,n); //将i和i+step这两个有序序列进行合并 //序列长度为step //当i以后的长度小于或者等于step时，退出 step*=2;//在按某一步长归并序列之后，步长加倍 } } //由于比较懒，所以这个也是百度百科的，我给稍加了调整。
懒癌发作……
4.选择排序
这就是我们常说的“打擂台”的方法。
***************************************************************
选择排序的工作原理是：第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。
***************************************************************
这个跟冒泡排序很像，但也有区别：
选择排序与冒泡排序的区别：冒泡排序通过依次交换相邻两个顺序不合法的元素位置，从而将当前最小（大）元素放到合适的位置；而选择排序每遍历一次都记住了当前最小（大）元素的位置，最后仅需一次交换操作即可将其放到合适的位置。
上代码！
void Sort(int* h, size_t len) { if(h==NULL) return; if(len<=1) return; int minindex,i,j; //i是次数，也即排好的个数;j是继续排 for(i=0;i<len-1;++i) { minindex=i; for(j=i+1;j<len;++j) { if(h[j]<h[minindex]) minindex=j; } Swap(h[i],h[minindex]); } return; }
代码已经给您找来了，其中的Sort函数即为排序过程。
5.插入排序
关于我的话……这个我真的没什么可说的了……直接介绍吧
***************************************************************
插入排序是一种简单直观且稳定的排序算法。如果有一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一个数，但要求插入后此数据序列仍然有序，这个时候就要用到一种新的排序方法——插入排序法,算法适用于少量数据的排序，时间复杂度O(n^2)。
***************************************************************
插入算法把要排序的数组分成两部分：第一部分包含了这个数组的所有元素，但将最后一个元素除外（让数组多一个空间才有插入的位置），而第二部分就只包含这一个元素（即待插入元素）。在第一部分排序完成后，再将这个最后元素插入到已排好序的第一部分中。
***************************************************************
如果过不理解的话看看这个图片吧：（来源：百度百科）
百度百科好
上代码！
void Sort(int* h, size_t len) { if(h==NULL) return; if(len<=1) return; int i,j; //i是次数，也即排好的个数;j是继续排 for(i=1;i<len;++i) for(j=i;j>0;--j) if(h[j]<h[j-1]) Swap(h[j],h[j-1]); else break; return; }
代码已经给您找来了，其中的Sort函数即为排序过程。
好了，到这里这篇文章基本就结束了。
6.其他
在我的程序中，程序都没有写主函数，主函数的问题一个是输入（如果过不会输入请重新学习c++）
在一个就是寻找各种方法的标记点等等，这里就不说了把。
后记
这就是这篇文章的全部内容了，如果过有问题的话可以通过侧边栏的QQ或者在评论区里通知我，我会尽量在第一时间查看。
还有就是……
客官，点个赞再走呗！