常见排序主要有以下四种：
1.交换排序
2.选择排序
3.插入排序
4.归并排序
（以下代码基本都有输出每步排序结果）
一.交换排序
交换排序主要是冒泡排序和快排
1.冒泡排序
流程：
（1）对数组中各个数字，一次比较相邻两个
（2）如果前面大于后面，就交换这两个数据
（3）再用同样的方法继续排，直到外层循环排完
#include<iostream> #include<cstdlib> #include<ctime> using namespace std; void BubbleSort(int a[],int len) { int t; for (int i = 0; i < len-1; i++) { for (int j = len-1; j>i; j--) { if (a[j]<a[j-1]) //比较相邻两个，前大于后，交换 { t=a[j-1]; a[j-1]=a[j]; a[j]=t; } } cout<<"Sort results in"<<i+1<<" step :"; //输出每一步排序结果 for (int k = 0; k <len ; k++) cout<<a[k]<<" "; cout<<endl; } }int main() { int array1[10]; srand(time(NULL)); cout<<"Array1 before sorting:"<<endl; for (int i = 0; i < 10; i++) //利用随机数作为数组输入 { array1[i]=rand()/1000; cout<<array1[i]<<" "; } cout<<endl; BubbleSort(array1,10); cout<<"Array1 after sorting:"<<endl; for (int i = 0; i < 10; i++) cout<<array1[i]<<" "; cout<<endl;return 0; }
2.快速排序
流程：
（1）首先设定一个分界值，通过分界值将数组分成左右两部分。
（2）将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。
（3）左右两个部分重复上述排序。
（详细解释见代码）
#include<iostream> #include<ctime> #include<cstdlib> using namespace std; void QuickSort(int *a,int left,int right) { int rt,lt,t,base; rt=right; //rt为基准分组后的左半部分上边界 lt=left; //lt为基准分组后的右半部分的下边界 base=a[left]; /*这里定义分界值，这个分界值定在哪里都是可以的，定在中间更为直观，若定在其他地方，手动排一下就知道，边界值会换到中间去，和定在中间一个样*/ while (lt < rt) { while(a[lt] < base) lt++; //从左边开始寻找大于分界值的值 while(a[rt] > base) rt--; //从右边开始寻找小于边界值的值 if(lt < rt) { /*lt小于rt，就交换这两个的值，lt与rt必不会在边界值同一侧， 手动按照算法排一下就知道，lt或rt到了边界值的时候就会停下来，交换的时候就会把边界值换到中间去了*/ t = a[lt] ; a[lt] = a[rt] ; a[rt] = t ; lt++; rt--; } } while(a[lt]<base) lt++; //因为右半部分可能还到不了下边界，所以需要继续递增 while(a[rt]>base) rt--;//因为左半部分可能还到不了上界，所以需要继续递减 if(lt == rt) lt++; //此处为了避免两个边界模糊不清 if( left < rt ) QuickSort(a,left,rt); //递归对左半部分快排 if( right > lt) QuickSort(a,lt,right); //递归对右半部分快排 } int main() { srand(time(NULL)); int n; cout<<"Please cin the size of array:"<<endl;//输入数组的大小 cin>>n; int a[n]; cout<<"Array before sorting is:"<<endl; for (int i = 0; i < n; i++) { a[i]=rand()/1000; //随机数作为数组输入 cout<<a[i]<<" "; } cout<<endl; QuickSort(a,0,n-1); cout<<"Array after sorting is:"<<endl; for (int i = 0; i < n; i++) cout<<a[i]<<" "; cout<<endl; return 0; }
二.选择排序
常见的选择排序有简单的选择排序和堆排序
1.简单的选择排序
流程：
（1）先从原始数组选择一个最小数据和第一个位置交换
（2）剩下的n-1个数据选择最小的和第二个位置交换
（3）不断重复直到最后执行完成
#include<iostream> #include<cstdlib> #include<ctime> using namespace std; void SelectionSort(int a[],int len) { int k,t; for (int i = 0; i < len-1; i++) { k=i; for (int j = i+1; j < len; j++) //选择第i+1个小的数据 { if (a[j]<a[k]) k=j; } if (k!=i) //选好后就可以交换了 { t=a[k]; a[k]=a[i]; a[i]=t; } cout<<"Sort Result in"<<i+1<<"step:"<<endl; for (int k = 0; k < len; k++) cout<<a[k]<<" "; cout<<endl; } } int main() { int array[10]; srand(time(NULL)); cout<<"Array before sorting:"<<endl; for (int i = 0; i < 10; i++) //随机数作为数组输入 { array[i]=rand()/1000; cout<<array[i]<<" "; } cout<<endl; SelectionSort(array,10); cout<<"Array after sorting:"<<endl; for (int i = 0; i < 10; i++) cout<<array[i]<<" "; cout<<endl; return 0; }
2.堆排序
堆排序关键是构造堆结构。这是一个完全二叉树结构。在这个树中每个节点对应原始数据一个记录。每个节点满足以下条件：
（1）若按照从小到大排序，要求非叶节点的数据大于等于其左右子节点的数据
（2）若按照从大到小排序，要求非叶节点的数据要小于等于其左右子节点的数据
可以看出，这只规定父节点和子节点的数据之间必须满足的大小关系。
完整的堆排序需要反复经过两个步骤：
（1）构造堆结构，
（2）堆排序输出。
下面介绍如何构造堆结构：
由完全二叉树的下层向上层逐层对父子节点的数据进行比较，使父节点的数据大于等于子节点的数据。（最小堆）
这里需要用到筛选运算不断调整，直到节点满足堆结构为止：
（1）先将原始数据排成一个二叉树
（2）对最后一个非叶节点进行筛运算。
*筛运算：比较左右子树，最大值放右子树，比较右子树与非叶节点，最大值放非叶节点。（比较过程中并非直接等，而是值互换）
（3）对倒数第二个非叶节点进行筛运算，
（4）一直重复，直到根节点进行筛运算为止。（若根节点的值被互换了，那么就要对互换的节点进行筛运算，一直下去）这时就形成了堆结构。
形成了堆结构，接下来就是堆排序输出（现在是按照从小到大的方式排序）：
（1）输出根节点，把最后一个结点的数放到根节点
（2）重新构造堆结构
（3）重复（1）（2）步，直到全部输出。
（这里并不构建树，直接对数组操作，关于树如果不理解的可以自己依据完全二叉树画法，首元素为树根，依次往下得出树结构，详细见代码及代码注释）
#include<iostream> #include<cstdlib> #include<ctime> using namespace std; void HeapSort(int a[],int n) { int t; for (int i = n/2-1; i >=0; i--) //第n/2-1个节点为止，都是非叶子节点 { while (2*i+1<n) //节点2*i+1是i的子树 { int j=2*i+1; if (j+1<n) //判定是否为一个子树 { //不是一个子树 if(a[j]<a[j+1]) j++; //判定哪个子树大，较大的子树与父节点比较 } if (a[i]<a[j]) //与父节点比较 { t=a[i]; //交换 a[i]=a[j]; a[j]=t; t=j; //因为与父节点的值交换了，所以需要对交换的节点重新进行筛选运算 } else break; } } cout<<"The original heap structure is:"<<endl; //输出原始堆结构 for(int i=0;i<n;i++) cout<<a[i]<<" "; cout<<endl; int i; for (i = n-1; i >=0; i--) //开始排序 { t=a[0]; //交换根节点的值到数组最后 a[0]=a[i]; a[i]=t; int k=0; while (2*k+1<i) //开始重新构造堆结构，因为从i开始，所以到i截止 { int j=2*k+1; //接下来与构造堆结构同 if (j+1<i) { if(a[j]<a[j+1]) j++; } if (a[k]<a[j]) { t=a[k]; a[k]=a[j]; a[j]=t; k=j; } else break; } cout<<"Array after "<<n-i<<"step:"; //输出每一步排序 for (int c = 0; c < n; c++) cout<<a[c]<<" "; cout<<endl; } } int main() { srand(time(NULL)); //随机数作为数组输入 int n; cout<<"Please cin the size of array:"<<endl; cin>>n; int a[n]; cout<<"Array before sorting:"<<endl; for (int i = 0; i < n; i++) { a[i]=rand()/1000; cout<<a[i]<<" "; } cout<<endl; HeapSort(a,n); cout<<"Array after sorting:"<<endl; for(int i=0;i<n;i++) cout<<a[i]<<" "; cout<<endl; return 0; }
三.插入排序
插入排序：通过对未排序的数据逐个插入合适的位置而完成排序工作
常见的插入排序有简单的插入排序和Shell排序
1.简单的插入排序
流程：
（1）先对数组前两个数据进行从小到大排序
（2）将第三个数据与前两个数据比较，将第三个数据插入合适的位置
（3）将第四个数据插入已排序好的前三个数据中
（4）不断重复，直到把最后一个数据插入合适的位置
（详细见代码及注释）
#include<iostream> #include<cstdlib> #include<ctime> using namespace std; void InsertionSort(int a[],int len) { int t; for (int i = 0; i < len; i++) { t=a[i]; //对第i个数进行标记（从零开始算，下同） int j=i-1; //从第i-1个数倒着回去找位置（第i-1个数前面的都从小到大排好了） while (j>=0&&t<a[j]) //找位置，小于第j个数继续找，而比较过的数就往后退留出空位置 {//由于我们标记了第i个数，所以我们比较过的数往后退的时候可以留出一个位置，因为第i个数位置空出来了 a[j+1]=a[j]; j--; } a[j+1]=t; cout<<"Sort result after"<<i+1<<"step:"; for(int k=0;k<len;k++) cout<<a[k]<<" "; cout<<endl; } } int main() { int a[10]; srand(time(NULL)); cout<<"Array before sorting:"<<endl; //随机数作为数组输入 for (int i = 0; i < 10; i++) { a[i]=rand()/1000; cout<<a[i]<<" "; } cout<<endl; InsertionSort(a,10); cout<<"Array after sort:"<<endl; for (int i = 0; i < 10; i++) cout<<a[i]<<" "; cout<<endl; return 0; }
2.Shell排序 （处理数据量比较大的时候的插入排序）
流程：
（1）将n个元素数组分成n/2个数字序列，第一个数据和第n/2个数据为一对，等等，以此类推
比如说 8 6 5 4 2 1 9 7
就分为数字序列 8 6 5 4 以及 2 1 9 7
那么8 和 2就是一个数对
（2）一次循环使每一个数对排列好顺序（假设从小到大）
依据上述，排序好后就是 2 1 5 4 和 8 6 9 7（2小于8，交换，1小于6，交换，9大于5，7大于4所以不用交换）
（3）变成n/4个数对，再次排序。
（数字序列就成为 2 1 ，5 4，8 6，9 7，这个时候有三次比较，设四个序列分别为a,b,c,d,那么此时b与a比较，然后c与b比较，然后d与c比较，后面以此类推 ）
（4）不断重复上述过程，随着序列减少直至最后变为1个（此时就成为插入排序了），完成排序。
（详细见代码及注释）
#include<iostream> #include<cstdlib> #include<ctime> using namespace std; void ShellSort(int *a,int len) { int x,t,j; for (int r = len/2; r >=1 ; r/=2) //外层循环分序列 { for (int i = r; i < len; i++) {//内层循环设置一定间距r，分别比较对应元素，当r=1时，这个时候就为插入排序，数组量大时这时效率比较高。 t=a[i]; j=i-r; while (j>=0&&t<a[j]) { a[j+r]=a[j]; j-=r; } a[j+r]=t; x++; cout<<"Sort result after "<<x<<" step "; //输出每一步排序结果 for (int k = 0; k < len; k++) cout<<a[k]<<" "; cout<<endl; } } } int main() { srand(time(NULL)); int n; cout<<"Please cin the size of array:"<<endl; //输入数组的大小 cin>>n; int a[n]; cout<<"Array before sorting:"<<endl; for (int i = 0; i < n; i++) //利用随机数作为数组输入 { a[i]=rand()/1000; cout<<a[i]<<" "; } cout<<endl; ShellSort(a,n); cout<<"Array after sorting:"<<endl; //输出排序后的数组 for (int i = 0; i < n; i++) cout<<a[i]<<" "; cout<<endl; return 0; }
四.归并排序
一个待排序的原始数据序列进行排序归并排序的基本思路：
（1）将n个待排序数据看成n个有序子表，这时候无所谓有序无序。
（2）将他们依次两两合并，得到长度为2的有序子表
（3）再两两合并，得到长度为4的有序子表。不能合并的留到下次一起合并
（4）重复上述步骤，直到表长度为n
eg.（1）待排序数据24 30 29 3 2 21 3 8 ，这里就是8个有序子表，无所谓有序无序
（2）两两合并，对子表排序，得到 24 30 ，3 29，2 21，3 8四个长度为2的有序子表
（3）再两两合并，得到长度为4的有序子表 3 24 29 30，2 3 8 21
（4）再合并得到 2 3 3 8 21 24 29 30
详细见代码及注释
#include<iostream> #include<cstdlib> #include<ctime> using namespace std; void MergeOne(int *a,int *p,int n,int len) { int i,j,k,begin,edge; //i,j分别代表合并前左子表和右子表的初始下标，k表示要赋值的数组的下标 begin=0; //begin代表合并的两组子表的初下标 while(begin+len<n) { edge=begin+2*len-1; //edge代表合并后的两组子表的末下标 if(edge>=n) edge=n-1; //因为有可能并不能全部一次性合并，有奇数，这时就会剩下未合并的 i=begin; k=begin; j=begin+len; while (i<begin+len&&j<=edge) //当子表下标都在合并范围内的时候 { if(a[i]<a[j]) p[k++]=a[i++]; //哪个小，哪个就赋值到数组 else p[k++]=a[j++]; } while(i<begin+len) p[k++]=a[i++];//如果左边子表剩下了，就把剩下的都放进数组 while(j<=edge) p[k++]=a[j++]; //如果右子表剩下了，就把剩下的放进数组 begin=edge+1; //继续合并下两组子表 } if(begin<n) for(;begin<n;begin++) p[begin]=a[begin]; //未合并的，单个的，先放进数组 } void MergeSort(int *a,int n) { int *p=new int [n]; //合并的数组 int len=1; //子表长度 int f=0; //标记，以a为初始数组还是以p为初始数组 int count=0; //记录合并步骤 while (len<n) //合并后子表长度小于n时，可以继续合并 { if(f==1) MergeOne(p,a,n,len); //以p为初始数组 else MergeOne(a,p,n,len); //以a为初始数组 f=1-f; //切换 len*=2; //合并一次，子表长度double count++; //合并次数递增 cout<<count<<" step:"; //输出每步结果 if(f) for (int i = 0; i < n; i++) cout<<p[i]<<" "; else for (int i = 0; i < n; i++) cout<<a[i]<<" "; cout<<endl; } if (f) {//判断最后一次是否以a为初始数组，如果是的话，就要把p的值全部赋值给a for(int i=0;i<n;i++) a[i]=p[i]; } delete []p; } int main() { srand(time(NULL)); cout<<"Please cin the size of array:"<<endl; int n; cin>>n; int a[n]; cout<<"Array before sorting:"<<endl; for (int i = 0; i < n; i++) { a[i]=rand()/1000; cout<<a[i]<<" "; } cout<<endl; MergeSort(a,n); cout<<"Array after sorting:"<<endl; for(int i=0;i<n;i++) cout<<a[i]<<" "; cout<<endl; return 0; }
以上是常见的排序，望大家轻喷。（狗头保命）