排序算法-1
记住一切都会好起来。给他一点时间。
排序一共有十种排序算法，虽然都没有Algorithm的sort简单好用，但多学无害。
如果你对代码理解起来比较难，你可以参考这篇博文，介绍了十种排序算法排序的动画演示GIF
下面就看是介绍比较简单的三种排序算法，分别是冒泡排序，选择排序，计数排序，简单插入排序，折半插入排序，希尔排序，快速排序，话不多说，上代码。
冒泡排序
冒泡排序有两种方法，一种是最原始的，还有一种是改进过的。
#include<iostream>
using namespace std;
typedef long long ll;
#define rep(i,x,y) for(ll i =x;i<=y;++i)
#define MAX 1000000
ll a[MAX],n;
inline void swap(ll i ,ll j)
{
ll t = a[i];
a[i] = a[j];
a[j] = t;
}
//ordinary sort
inline void bubblesort(ll a[])//
{
for(ll i=1;i<n;++i)
{
for(ll j =n-1;j>=i;--j)
// for(ll j =1;i<=n-j;++j)
{
if(a[j]>a[j+1])
{
swap(j,j+1);
}
}
}
}
//Optimized sort
inline void bubblesort_1(ll a[])
{
int flag =1;
for(ll i =1;i<n&&flag;++i)
{
flag = 0;
for(ll j = n-1;j>=i;--j )
{
if(a[j]>a[j+1])
{
swap(j,j+1);
flag = 1;
}
}
}
}
int main()
{
cout<<"please input the size of the data："<<endl;
while(cin>>n)
{
ll i;
rep(i,1,n)
{
cin>>a[i];
}
//two measures of sorting data
//first
//bubblesort(a);
//second
bubblesort_1(a);
rep(i,1,n)
{
cout<<a[i]<<" ";
}
cout<<endl;
cout<<"Please input the size of the data:"<<endl;
}
return 0;
}选择排序
#include<iostream>
using namespace std;
typedef long long ll;
ll a[10000],n;
inline void swap(ll i,ll j)
{
ll t = a[i];
a[i] = a[j];
a[j] = t;
}
inline void selectsort(ll a[])
{
ll k,t;
for(ll i =1;i<n;++i)
{
k =i;
for(ll j =i+1;j<=n;++j)
{
if(a[j]>a[k])
k = j;
}
if(k!=i)
{
swap(k,i);
}
}
}
int main()
{
while(cin>>n)
{
for(ll i=1;i<=n;++i)
{
cin>>a[i];
}
selectsort(a);
//select_sort(a);
for(ll i =1;i<=n;++i)
{
cout<<a[i]<<" ";
}
cout<<endl;
}
return 0;
}计数排序
#include<iostream>
#include<stdlib.h>
#include<time.h>
using namespace std;
//bilibili
//https://www.bilibili.com/video/av54557540/?spm_id_from=333.788.videocard.1
int a[10000];
void getarray(int *a,int n)
{
//unsigned sr = time(NULL);
int t=1000; srand(time(NULL));
while(t<1||t>100)
{
for(int i=0;i<n;++i)
{
t=rand()%100;
a[i] = t;
}
}
cout<<"Random array is: "<<endl;
for(int i =0;i<n;++i)
cout<<a[i]<<" ";
cout<<endl;
}
void countsort(int *A,int *Aux,int *sortedA,int n)
{
int k =0;
for(int i=0;i<n;++i)
{
k = max(k,A[i]);
}
for(int i=0;i<k;++i)
{
Aux[i] = 0;
}
for(int i=0;i<n;++i)
{
Aux[A[i]]++;
}
int j =0;
for(int i=0;i<=k;++i)
{
int t = Aux[i];
while(t--)
{
sortedA[j] = i;
j++;
}
}
}
int main()
{
int n;
cout<<"请输入数量"<<endl;
while(cin>>n)
{
getarray(a,n);
int b[10000],c[1000];
countsort(a,b,c,n);
cout<<"排序结果为：\n";
for(int i =0;i<n;++i)
cout<<c[i]<<" ";
cout<<endl;
cout<<"请输入数量"<<endl;
}
return 0;
}简单插入排序
#include<iostream>
using namespace std;
#define MAX 100000
#define rep(i,x,y) for(int i =x;i<=y;++i)
typedef long long ll;
typedef struct
{
ll aa;
}data;
typedef struct
{
data a[MAX];
ll length;
}List;
void insertsort(List &L)
{
ll i,j;
rep(i,2,L.length)
{
if(L.a[i].aa<L.a[i-1].aa)
{
L.a[0] = L.a[i];
L.a[i] = L.a[i-1];
for( j =i-2;L.a[0].aa<L.a[j].aa;--j)
{
L.a[j+1] = L.a[j];
}
L.a[j+1] = L.a[0];
}
}
}
int main()
{
int n;
List L;
cout<<"请输入数据大小"<<endl;
while(cin>>n)
{
ll i;
L.length = n;
rep(i,1,n)
{
cin>>L.a[i].aa;
}
insertsort(L);
rep(i,1,n)
{
cout<<L.a[i].aa<<" ";
}
cout<<endl;
cout<<"请输入数据大小"<<endl;
}
return 0;
}折半插入排序
#include<iostream>
using namespace std;
typedef long long ll;
#define MAX 10000
#define rep(i,x,y) for(int i =x;i<=y;++i)
typedef struct
{
ll aa;
}data;
typedef struct
{
data a[MAX];
ll length;
}List;
void binary_insert_sort(List &L)
{
ll i;
ll low,high,m;
rep(i,2,L.length)
{
L.a[0] = L.a[i];
low = 1;high = i-1;
while(low<=high)
{
m = (low+high)/2;
if(L.a[0].aa<L.a[m].aa) high = m-1;
else low = m+1;
}
for(ll j = i-1;j>=high+1;--j)
L.a[j+1] = L.a[j];
L.a[high+1] = L.a[0];
}
}
int main()
{
int n;
List L;
cout<<"请输入数据大小"<<endl;
while(cin>>n)
{
ll i;
L.length = n;
rep(i,1,n)
{
cin>>L.a[i].aa;
}
binary_insert_sort(L);
rep(i,1,n)
{
cout<<L.a[i].aa<<" ";
}
cout<<endl;
cout<<"请输入数据大小"<<endl;
}
return 0;
}希尔排序
#include<iostream>
using namespace std;
typedef long long ll;
ll n,a[10000];
inline void shellsort(ll a[])
{
int t;
for(int gap = n/2;gap>0;gap/=2)
{
for(int i=gap;i<n;++i)
{
for(int j = i-gap;j>=0&&a[j]>a[j+gap];j-=gap )
{
t = a[j];
a[j] = a[j+gap];
a[j+gap] = t;
}
}
}
}
int main()
{
cout<<"请输入数据大小"<<endl;
while(cin>>n)
{
for(int i =0;i<n;++i)
{
cin>>a[i];
}
shellsort(a);
for(int i =0;i<n;++i)
{
cout<<a[i]<<" ";
}
cout<<endl;
cout<<"请输入数据大小"<<endl;
}
return 0;
}快速排序
#include<iostream>
using namespace std;
typedef long long ll;
ll n,a[100000];
inline ll partition(ll a[],ll begin,ll end)
{
a[0] = a[begin];
ll key = a[begin];
while(begin<end)
{
while(begin<end&&a[end]>=a[0]) end--;
a[begin] = a[end];
while(begin<end&&a[begin]<=a[0]) begin++;
a[end] = a[begin];
}
a[end] = a[0];
return end;
}
inline void quicksort(ll a[],ll begin, ll end)
{
if(begin<end)
{
ll pivotkey = partition(a,begin,end);
quicksort(a,begin,pivotkey-1);
quicksort(a,pivotkey+1,end);
}
}
int main()
{
cout<<"Please input the size of the data"<<endl;
while(cin>>n)
{
for(ll i=1;i<=n;++i)
{
cin>>a[i];
}
quicksort(a,1,n);
for(ll i=1;i<=n;++i)
{
cout<<a[i]<<" ";
}
cout<<endl;
cout<<"Please input the size of the data"<<endl;
}
return 0;
}本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2019-11-27|，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
