生活中有太多需要排序的场景，电影的播放时间，美团订购商家的距离远近，淘宝商品的价格，都需要排序，当产品量很大的时候，就需要我们使用适当的排序算法。
1、桶排序
桶排序是一种简单，快速的排序，时间复杂度为O（M+N）
桶排序实现的过程形象点来说就是，一个可能一个桶，将数放入该数位置桶中，这样就自然有顺序了。比如一个班的数学考试成绩进行排序，满分是100分，这样我申请一个数组，是a[100]，数组的每个元素都是0，然后如果一个学生考89分，我就让a[89]的元素+1，变为1，依次将每个学生的成绩“放入桶中”。这样就自然有顺序了。
我们用代码来实现一下：
假设班上有58(N)个学生，满分是100(M)分；
int a[M] ;int t;
//初始化
for(i=0;i<M;i++)
a[i]=0;
//输入
for（i=0;i<N;i++）{
scanf("%d",&t);//把每个学生的成绩读到变量t
a[t]++; //进行计数
}//
这样其实已经拍好循序了，剩下就是输出
for(int i=0;i<=M;i++)
for(j=0;j<a[i];j++) //出现几次就打印几次
printf("%d",i);//打印桶的序号;
这样就完成了一个桶排序的操作,时间复杂度是时输入和输出的时候都是俩次的桶个数和待排序数个数的for循环,即(M+N)*2;我们在计算时间复杂度的时候可以忽略最小的常数,即这种算法的时间复杂度是O(M+N)。这是一种相当快速的排序算法，适合在M值不算太大的情况。
2、冒泡排序
冒泡排序的基本思想是:每次比较相邻的俩个数,这样实现大数下沉,小数上浮,这样就实现了排序功能.
比如12 34 23 45进行排序,想让从大到小排序,先比较12和34,这样他们就调换了位置,然后再比较第二个第三个数,12就到了第三个位置,比完N-1次之后,12就下沉到最后了,这样下次就只需要比较N-2次了.进行N-1次循环就将整个数组排序了.
代码实现:
int a[10] = {10,4,20,30,44,56,33,22,34,11};
for(int i=0;i<10;i++){
for (int j=0; j<10-i; j++) {
if (a[j]<a[j+1]){
int k = a[j+1];
a[j+1] = a[j];
a[j] = k; }
} }
for (int i = 0; i<10; i++) { printf("%d ",a[i]); }
冒泡排序的核心是双重嵌套循环,这种方式排序的时间复杂度是O(N²).是一个很高复杂度的算法.
3、快速排序
快速排序的过程是选中数组中的一个数作为基数,然后从左右两测查找,发现比基数小的和比基数大的就进行交换,直到最后俩个选择点相交,将相交数与基数进行交换,这样基数位置就确定了,这样数组就分为两部分,然后再分别将这两部分进行上面的操作,依次将每个数的位置确定.
例如: int a[10] = {10,4,20,30,44,56,33,22,34,11};
进行排序,我选择10作为基数,然后必须先从最后的11开始向左数,碰到比10小的数停止,这样右边的指标会在4那里停止了,左边的指标再向右移一位就和右边的指标相遇了,这样就能确定此次基数的位置在4那里,这样将10和4进行交换,就完成了一个基数的排序了,这样数组分为左边的4,和右边的20,30,44,56,33,22,34,11, 这样我们只需要再排序右边的数组了,我们再将右边指标定位在最后的11,左边指标定位在20,还是必须先让右边指标动作,向左找比基数20小的数,这次右边指标在11那里就停止了,左边的指标开始行动,在30那里停止,两个数互换,数组变为 {4,10,20,11,44,56,33,22,34,30},然后右边指标继续移动,知道找到比20小的数,到11那里与左边指标相遇,这样就确定了此次基数20的位置,这样叫11与基数20交换就确定了20的位置,这样又完成了一个数的排序,这样依次下去,可以将整个数组排序. 这种排序方法,最坏的情况就是每次都是相邻的俩个数交换,这样的时间复杂度是和冒泡排序一样的O(N²),但是这种算法的平均复杂度是NLogN,比冒泡排序更快速.
代码实现:
int a[10] = {10,4,20,30,44,56,33,22,34,11}; int n;
void quicksortTest(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&&i<j) j--;
while (a[i]<=temp&&i<j)i++;
if (i<j) {
t=a[i];
a[i]=a[j];
a[j]=t; }
}
//将基准数归位
a[left] = a[i];
a[i] = temp;
//递归.继续处理分开的两个数组
quicksortTest(left, i-1);
quicksortTest(i+1, right);
return;
}
//调用 :
quicksortTest(0, 10);
for (int i=0; i<10; i++) {
printf("%d ",a[i]);
}
网友评论