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也可以进行相似的操作
今天就到这里了，如果你觉得不错，请点赞
加载全部内容
- 猜你喜欢
- 用户评论