C++五种排序方法详解
C++五种排序方法详解
排序算法是编程中常见的基础算法之一，掌握多种排序方法对于提升编程能力和解决实际问题具有重要意义。本文将详细介绍五种常用的C++排序方法：sort函数、桶排序、冒泡排序、选择排序和快速排序。通过本文的学习，读者将能够理解这些排序算法的基本原理，并掌握其在C++中的实现方式。
模板函数sort( )
sort是一个模板函数，可以接受两个或三个参数。这里先介绍两个参数的用法，因为三个参数的用法尚未研究。
使用sort()时需要包含头文件<algorithm>，这个英文单词的意思是“运算法则”。
接受两个参数时默认的排序方式是升序，添加第三个参数是为了实现降序。第一个参数是所要排序的数列的首地址，而第二个参数是该数列的最后一个数的地址加一。比如要对数组a[7]={5,7,9,10,8,2,3}排序，则是sort(a,a+7)。
#include<iostream>
#include<algorithm>
using namespace std;
int main() {
int a[10]= {9,6,3,8,5,2,7,4,1,0};
for(int i=0; i<10; i++)
cout<<a[i]<<" ";
cout<<endl;
sort(a,a+10); //注意这是a+10
for(int i=0; i<10; i++)
cout<<a[i]<<" ";
return 0;
}
运行结果：
9 6 3 8 5 2 7 4 1 0
0 1 2 3 4 5 6 7 8 9
桶排序方法
桶排序以前真没听说过。。。。看图：(其实是看表格了）
0 0 0 0 0 0 0 0 0 0 ...
a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] a[...]
这是一个初始化为零的数列，如果想要利用它来进行排序，例如这样一组数：6，3，9，6，8，7，5，4。
首先按照下标进行赋值，即：
0 0 0 1 1 1 2 1 1 1 ...
a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] a[...]
实际上已经按照下标的顺序排好了，只需按照里面的值输出就ok了。
#include<iostream>
#include<algorithm>
using namespace std;
int main() {
int x,n;
cin>>n;
int a[100]= {0};
for (int i=0; i<n; i++) {
cin>>x;
a[x]++;
}
for(int i=0; i<100; i++) {
for(int m=1;m<=a[i];m++){
cout<<i<<" ";}
}
}
其实桶排序并没有在数组内部将这些数按照升序的方式排列，只是借助了下标将它们输出了。
冒泡排序
这种排序方法上课时老师讲过。主要的原理就是冒泡，哈哈哈。冒泡可以实现升序和降序的排列，例如一列数：2 3 6 8 10 5 1 七个数
升序排列的话 ，第一次循环：相邻的两个数进行比较，大的数则放在后面，这样第一次循环比较了六次：2 3 6 8 5 1 10。
可以看出第一次循环最大的值10浮出了水面。所以，可以推想出要想完成排序，最多要进行n-1次循环才行。并且每次循环所比较的次数在逐渐减小，因为一部分值已经按照顺序排好了位置。
#include<iostream>
using namespace std;
int main() {
int n,exchange;
cout<<"要排几个数：";cin>>n;
int a[100];
for (int i=0; i<n; i++) {
cin>>a[i]; }
for(int i=1; i<=n-1; i++) //主要算法
{
for(int j=1;j<=n-i;j++)
{
if(a[j-1]>a[j])
{exchange=a[j-1];
a[j-1]=a[j];
a[j]=exchange;
}
}
}
for(int i=0;i<n;i++)
{
cout<<a[i]<<" ";
}
}
选择排序
还是这2 3 6 8 10 5 1七个数，按照升序的方法排，这次不再是冒泡，而是选择。
具体思路：也要进行6次循环。第一次循环，将2与后面的六个数进行比较，选出最小的即1放在第一个位置；下一次则是从第二个数开始，与后面的五个数进行比较，然后将第二小的数即2放在第二个位置；然后以此类推，直到排完为止。
#include<iostream>
using namespace std;
int main() {
int n,exchange;
cout<<"要排几个数：";
cin>>n;
int a[100];
for (int i=0; i<n; i++) {
cin>>a[i];
}
for(int i=0;i<=n;i++)
{
for(int j=i+1;j<=n-1;j++)
{
if(a[i]>a[j])
{exchange=a[i];
a[i]=a[j];
a[j]=exchange;
}
}
}
for(int i=0; i<n; i++) {
cout<<a[i]<<" ";
}
}
快速排序
快速排序可以说是比上面几个都不好理解的排序方法了。但它的效率却比较高思维方式也比较巧妙，需要用到二分法思想和递归。
这里参考了啊哈磊的文章，还是想要按照自己的语言来总结一下快速排序的算法，哈哈。
先看这样一个未排序之前的数列 6 1 2 7 9 3 4 5 10 8 ,然后再看一下它的变形：3 1 2 5 4 6 9 7 10 8。
会发现这十个数以6为基准分成了两个阵营：左边都比6小，右边都比6大。这里将6称为基准数，它将扮演重要的角色。
快速排序正是这样一个利用基准数不断分阵营的过程。咱们先看上面两个数列是如何变换的：
（图片源自于啊哈磊博客，侵删。）
首先假如选择6作为基准数，并定义两个小兵（变量）i和j。初始值分别为1和10，即分别位于该数列的左右两边。
接下来分别交给这两个小兵不同的任务：小兵 j 先出发，向左走j--，它的任务是寻找比基准数6小的数，当它走到5这里时停住了；
小兵i然后出发，向右走i++，它的任务是寻找比基准数6大的数，当它走到7这里时停住了；如图所示：
下一步要做的就是交换，交换小兵脚下的值，到这里，第一波交换结束。
紧接着，小兵j继续出发，执行之前的任务。这次它在4这里停了下来；小兵i也出发，它在9这里停了下来；同样，仍然需要交换，交换后如图所示：
紧接着j继续走 ，寻找比6小的数，它发现了3，于是它停住了；紧接着i开始出发，却在3这里偶遇了j；此次它们的任务还尚未结束，它们还需要将脚下的值与基准数6进行交换。
至此，任务完成。 这一组数变成了这样：3 1 2 5 469 7 10 8，以6为基准分别在两边站好了对。
所以，上面的方法掌握了下面的就不难办了。即利用递归，分别再在两边的两组数中寻找基准数。比如：左边的3 1 2 5 4 ，
以3作为这组数的基准数，按照上面的方法，如果没错的话，一波操作下来应该变成了2 135 4 .
接下来需要处理3左边的序列2 1和右边的序列5 4。对序2 1以2为基准数进行调整，处理完毕之后的序列为“1 2”，到此2已经归位。序列“1”只有一个数，也不需要进行任何处理。至此我们对序列“2 1”已全部处理完毕，得到序列是“1 2”。序列“5 4”的处理也仿照此方法。
最终即可得1 2 3 4 5 6 7 8 9 10.
所以整个过程中不断更换基准数，不断的站队。
对上述过程中几个细节做一些解释：
- 基准数的选取：
- 小兵出发的先后:
附一下代码：
#include<iostream>
using namespace std;
int a[100],n;
void quicksort(int left,int right) {
int i,j,t,temp;
if(left>right)
return;
temp=a[left];
i=left;
j=right;
while(i!=j) {
while(a[j]>=temp&&j>i)
j--;
while(a[i]<=temp&&j>i)
i++;
if(i<j) {
t=a[i];
a[i]=a[j];
a[j]=t;
}
}
a[left]=a[i];
a[i]=temp;
quicksort(left,i-1);
quicksort(i+1,right);
}
int main() {
cout<<"排几个数：";
cin>>n;
for(int i=0; i<n; i++) {
cin>>a[i];
}
quicksort(0,n-1);
for(int i=0; i<n; i++) {
cout<<a[i]<<" ";
}
}
另外还有其他的快速排序的思路，贴个地址：挖坑填数+分治法。这个思路也很好。