亲宝软件园·资讯

展开

0基础学算法 第二弹 排序

球君 人气:0

    大家好啊,这是0算法基础学算法系列第二篇,上次我在第一弹里讲了关于流程图的内容,我寻思着,这次讲些什么好呢,于是我决定,教大家一个很基础的算法,那就是排序,排序有很多方法,如果你有更多方法请在评论区里留言哦。

排序在程序中特别实用,常用的有快速排序,桶排序,冒泡排序,插入排序等等,在这里我不建议使用冒泡排序或者插入排序,建议桶排序和快速排序,这两个排序非常实用,时间复杂度低,理解起来也很容易,首先,你先思考一下,怎么用程序进行排序,然后你再来看看你的思路合理不合理,最后试着用程序实现它,实现后你就有了自己的方法,没实现的话也没关系,这篇博文会讲的,实现的也请耐心的看完,说不定有比你的方法更好的呢qaq

接下来切入正题

一,冒泡排序

    英文bubble sort,其执行方法和他的名字一样,就是像泡泡不断向上判断,自己是否大于接下来的泡泡,如果大于,就差到前面去,类似于泡泡一样向水平面冒,但是由于操作不是很简单,实现起来很复杂,造成很多情况下都会以超时结束,也就是TLE,最坏的时候,时间复杂度甚至可以达到O(n^2),是不是被震撼到了,也就是说录入100个数,他却要10000的时间,虽然不是很推荐,但还是要介绍一下,毕竟也是很经典嘛

    

#include <iostream>
using namespace std;
template<typename T>
//整数或浮点数皆可使用
void bubble_sort(T arr[], int len)
{
    int i, j;  T temp;
    for (i = 0; i < len - 1; i++)
        for (j = 0; j < len - 1 - i; j++)
        if (arr[j] > arr[j + 1])
        {
            temp = arr[j];
            arr[j] = arr[j + 1];
            arr[j + 1] = temp;
        }
}
int main()
{
    int arr[] = { 61, 17, 29, 22, 34, 60, 72, 21, 50, 1, 62 };
    int len = (int) sizeof(arr) / sizeof(*arr);
    bubble_sort(arr, len);
    for (int i = 0; i < len; i++)
        cout << arr[i] << ' ';
 
    cout << endl;
 
    float arrf[] = { 17.5, 19.1, 0.6, 1.9, 10.5, 12.4, 3.8, 19.7, 1.5, 25.4, 28.6, 4.4, 23.8, 5.4 };
    len = (int) sizeof(arrf) / sizeof(*arrf);
    bubble_sort(arrf, len);
    for (int i = 0; i < len; i++)
        cout << arrf[i] << ' ';
 
    return 0;
}

上面这个例子就是非常经典的纯冒泡排序,通过程序可以清楚地看到这给了两组数据,分别是整型和浮点型,原理是从第一个数开始,如果他大于后面的数,就往后一个,如果小于他则在他前面停住,然后接着看下一个数,做同样的操作,因为有一个嵌套循环,所以时间复杂度是O(n*n),这里我也不好多说,毕竟萝卜白菜各有所爱,有时候冒泡还可以做出不可思议的陈旧呢

二,插入排序

    插入排序和冒泡排序很相似,连时间复杂度都是相同的,也一样没人用不常用,毕竟时间复杂度O(n^2)的排序很容易超时,但还是介绍一下吧

    插入排序(Insertion sort)是一种简单直观且稳定的排序方法。如果有一个已经有序的数据序列,要求在这个已经排好的数据序列中插入一个数,但要求插入后此数据序列仍然有序,插入排序的稳定程度是毋庸置疑的,但是出于时间复杂度而言,还有更多简便的排序方法兴起令插入排序逐渐被埋没了,还是像冒泡排序一样,发一个代码来说明吧

#include<iterator>
template<typename biIter>
void insertion_sort (biIter begin,biIter end)
{
    typedef typename std::iterator_traits<biIter>::value_type value_type;
    biIter bond=begin;
    std::advance(bond,1);
    for(;bond!=end;std::advance(bond,1))
    {
        value_type key=*bond;
        biIter ins=bond;
        biIter pre=ins;
        std::advance(pre,-1);
        while(ins!=begin&&*pre>key)
        {
            *ins=*pre;
            std::advance(ins,-1);
            std::advance(pre,-1);
        }
        *ins=key;
    }
}

上面的代码可以说明,插入排序也是和他的名字一样,就是不断抽出数值然后插入到合适的地方去,来达到排序的目的,超高时间复杂度,超难理解的原理,唯一的优点是稳定,但是弊大于利,所以渐渐也就不常用了

接下来是超超超推荐环节

一,快速排序

    快速排序相信大家都不陌生,因为比起冒泡和插入,快速排序会方便很多,也会快很多,快排英文quick sort,大致原理是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,由于这种排序方法好理解,实现起来又简单,更重要的是时间复杂度只有O(nlog2n),因此,该排序方法被认为是目前最好的一种内部排序方法,被广泛使用,值得一提的是,他是基于冒泡排序的一种优化排序,所以有的时候时间复杂度还是会飙到O(n^2),接下来还是展示一个代码吧

#include <iostream>
 
using namespace std;
 
void Qsort(int arr[], int low, int high){
    if (high <= low) return;
    int i = low;
    int j = high + 1;
    int key = arr[low];
    while (true)
    {
        /*从左向右找比key大的值*/
        while (arr[++i] < key)
        {
            if (i == high){
                break;
            }
        }
        /*从右向左找比key小的值*/
        while (arr[--j] > key)
        {
            if (j == low){
                break;
            }
        }
        if (i >= j) break;
        /*交换i,j对应的值*/
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    /*中枢值与j对应值交换*/
    int temp = arr[low];
    arr[low] = arr[j];
    arr[j] = temp;
    Qsort(arr, low, j - 1);
    Qsort(arr, j + 1, high);
}
 
int main()
{
    int a[] = {57, 68, 59, 52, 72, 28, 96, 33, 24};
 
    Qsort(a, 0, sizeof(a) / sizeof(a[0]) - 1);/*这里原文第三个参数要减1否则内存越界*/
 
    for(int i = 0; i < sizeof(a) / sizeof(a[0]); i++)
    {
        cout << a[i] << "";
    }
     
    return 0;
}

根据代码和注释可以看到,这期是非常眼熟,对,就是冒泡,他和冒泡的差别绝对比你想象中要小得多,因为和他同样,都是一个一个的扫描,不断往后插入,但和冒泡不同的是,他会进行几次划分,快速排序的一次划分算法从两头交替搜索,直到low和high重合,因此其时间复杂度是O(n);而整个快速排序算法的时间复杂度与划分的趟数有关,由于冒泡是单向的,但是快速排序可以通过划分大大地节省时间,这就是为什么他可以成为最好的内部排序方法。

二,桶排序

    其实我个人是非常喜欢桶排序的,因为它太简单了,理解起来又容易,不像快拍看起来那么复杂,我认为他应该是最直观的

    桶排序 (Bucket sort)或所谓的箱排序,大致的工作原理就是定义一个数组变量,然后录入要排序的数,在定义一个数组作为桶,以每个录入的数位下标,让该下标的桶的值+1,而且,他有时候比快速排序还要快很多,因为它只用根据下标加值就行了,所以他的时间复杂度是O(n),是不是很快呢,他非常快可以说,接下来我们还是结合代码说一下吧,注意,我已给出两个桶排序,一个是简易版,一个是真正的桶排序。

#include<stdio.h>
int main()
 {
     int buc[6]={0};        //定义木桶并初始化,因为我们要在012345个分数中排序所以要定义6个桶。
     int i,j,t,n;           
     scanf("%d",&n);        //输入一个数n+1,表示接下来有n个数要排序
     for(i=1;i<n;i++)       //循环读入n个数,并进行排序
     {
         scanf("%d",&t);    //把每一个数读到变量t中;
         buc[t]++;          //进行计数;
     }
     for(i=0;i<=5;i++)      //判断0到5的桶
         for(j=1;j<=buc[i];j++)//出现了几次就将桶的编号打印几次;
            printf("%d",i);
 
}

————————————————
版权声明:本文为CSDN博主「颜十三郎」的原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接及本声明。
原文链接:https://blog.csdn.net/qq_36156580/articlehttps://img.qb5200.com/download-x/details/91415941

⚠️注意,这个的代码非原创,但博文原创(主要是实在没时间自己去写一个了)

这就是简易版的桶排序,可以说非常简单,就是将对应下标的桶里面数值加一,输出的时候就只要输出桶里的下标桶里值次,所以运行起来很简单,就让他占据的一定的地位

最后,肯定要把正规的桶排序代码放出来了,留个思考题吧,好好想想为什么桶排序要这么做吧,记得自己去运行一下哦

#include<iostream>
usingnamespace std;
int a[]={1,255,8,6,25,47,14,35,58,75,96,158,657};
const int len=sizeof(a)/sizeof(int);
int b[10][len+1]={0};//将b全部置0
void bucketSort(int a[]);//桶排序函数
void distribute Elments(int a[],int b[10][len+1],int digits);
void collectElments(int a[],int b[10][len+1]);
int numOfDigits(int a[]);
void zeroBucket(int b[10][len+1]);//将b数组中的全部元素置0
int main()
{
cout<<"原始数组:";
for(int i=0;i<len;i++)
cout<<a[i]<<",";
cout<<endl;
bucketSort(a);
cout<<"排序后数组:";
for(int i=0;i<len;i++)
cout<<a[i]<<",";
cout<<endl;
return 0;
}
void bucketSort(int a[])
{
int digits=numOfDigits(a);
for(int i=1;i<=digits;i++)
{
distributeElments(a,b,i);
collectElments(a,b);
if(i!=digits)
zeroBucket(b);
}
}
int numOfDigits(int a[])
{
int largest=0;
for(int i=0;i<len;i++)//获取最大值
if(a[i]>largest)
largest=a[i];
int digits=0;/https://img.qb5200.com/download-x/digits为最大值的位数
while(largest)
{
digits++;
largest/=10;
}
return digits;
}
void distributeElments(int a[],int b[10][len+1],int digits)
{
int divisor=10;//除数
for(int i=1;i<digits;i++)
divisor*=10;
for(int j=0;j<len;j++)
{
int numOfDigist=(a[j]%divisor-a[j]%(divisor/10))/(divisor/10);
//numOfDigits为相应的(divisor/10)位的值,如当divisor=10时,求的是个位数
int num=++b[numOfDigist][0];//用b中第一列的元素来储存每行中元素的个数
b[numOfDigist][num]=a[j];
}
}
void collectElments(int a[],int b[10][len+1])
{
int k=0;
for(int i=0;i<10;i++)
for(int j=1;j<=b[i][0];j++)
a[k++]=b[i][j];
}
void zeroBucket(int b[][len+1])
{
for(int i=0;i<10;i++)
for(int j=0;j<len+1;j++)
b[i][j]=0;
}

三,无敌快排sort

    如果上面的排序方式你都不能接受,我还有杀手锏呢,那就是sort,sort是一个函数,不需要自己编写,只要加一个头文件 <algorithm>,就可以快乐的直接用sort了,真是的,sort函数不香吗,介绍一下他的用法吧

sort(数组名,数组名+数字个数)

注意一下,上面的数组默认为第一位下标为0,如果想下标为一,那么就必须写成这样

sort(数组名+1,数组名+数字个数+1)

以此类推,要是第一位下标为2,为3也可以进行相似的操作

今天就到这里了,如果你觉得不错,请点赞

加载全部内容

相关教程
猜你喜欢
用户评论