专栏首页AngelNI排序算法-2

排序算法-2

桶排序,又简单,又快速,适合处理大量数据

桶排序

#include<iostream>
using namespace std;
int n ;
int a[1000];
//   O(m+n)
int main()
{
    while(cin>>n)
    {
        for(int i=1;i<=n;++i)
        {
            int t;
            cin>>t;
            a[t]++;
        }
        //桶排序
        for(int i = 1;i<1000;++i)//从小到大
        //for(int i =1000-1;i>=0;--i)//从大到小
        {
            for(int j =1;j<=a[i];++j)
            {
                cout<<i<<" ";
            }
        }
        cout<<endl;
    }
    return 0;
}

归并排序

#include<iostream>
using namespace std;
typedef long long ll;
ll a[1000000];
void merge(ll *A,ll start,ll mid,ll end)
{
	ll p =start,q = mid+1;
	ll arr[end-start+1],k =0;
	for(ll i =start;i<=end;i++)
	{
		if(p>mid)
			arr[k++] = A[q++];
		else if(q>end)
		{
			arr[k++] = A[p++];
		}
		else if(A[p]<A[q])
		{
			arr[k++] = A[p++];
		}
		else
		{
			arr[k++] = A[q++];
		}
	}
	for(int p=0;p<k;++p)
	{
		A[start++] =arr[p];
	}
}
void mergesort(ll *A,ll start,ll end)
{
	if(start<end)
	{
		ll mid = (start+end)/2;
		mergesort(A,start,mid);
		mergesort(A,mid+1,end);
		merge(A,start,mid,end);
	}
}
int main()
{
    int n;
    while(cin>>n)
    {
        for(int i =0;i<n;++i)
            cin>>a[i];
        mergesort(a,0,n-1);
        for(int i=0;i<n;++i)
            cout<<a[i]<<" ";
        cout<<endl;
    }
    return 0;
}

堆排序

#include<iostream>
using namespace std;
typedef long long ll;
ll a[100000];
void swap(ll *a,ll i,ll j)
{

	ll t = a[i];
	a[i] = a[j];
	a[j] = t;
}
void heapify(ll *tree,ll n,ll i)
{
	if(i>=n)
		return ;
	ll c1 = 2*i+1;
	ll c2 = 2*i+2;
	ll max = i;
	if(c1<n&&tree[c1]>tree[max])
	{
		max = c1;
	}
	if(c2<n&&tree[c2]>tree[max])
	{
		max = c2;
	}
	if(max != i)
	{
		swap(tree,max,i);
		heapify(tree,n,max);
	}
}
void heapsort(ll *a,ll n)
{
	for(ll i =n/2-1;i>=0;i--)
	{
		heapify(a,n,i);
	}
	for(ll i=n-1;i>=0;i--)
	{
		swap(a,i,0);
		heapify(a,i,0);
	}
}
int main()
{
    int n;
    while(cin>>n)
    {
        for(ll i =0;i<n;++i)
            cin>>a[i];
        heapsort(a,n);
        for(ll i =0;i<n;++i)
            cout<<a[i]<<" ";
        cout<<endl;
    }
    return 0;
}

qsort

c++的函数库

#include<iostream>
#include<cstdlib>
using namespace std;
int cmp(const void *a,const void *b)
{
    return *(int *)a - *(int *)b;
}
int main()
{
    int n = 10;
    int a[10] = {-7,6,2,0,3,9,8,4,1,5};
    qsort(a,n,sizeof(n),cmp);
    for(int i =0;i<=10;++i)
        cout<<a[i]<<" ";
    cout<<endl;
    system("pause");
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 排序算法-1

    排序一共有十种排序算法,虽然都没有Algorithm的sort简单好用,但多学无害。

    AngelNH
  • 矩阵快速幂

    AngelNH
  • Winter Camp 1

    AngelNH
  • 『ACM-算法-枚举法』信息竞赛进阶指南--枚举方法

    你以为枚举是一个一个的找? 还真是 你以为枚举都是for循环? 还真是 但你真的会枚举吗?组合型枚举,指数型枚举,排列型枚举?难道你只会线形...

    风骨散人Chiam
  • 快速找到自己想要用到的cocos2d-x的缓冲动画

    游戏中在做很多动画时,需要用到缓冲来增强表现。比如宝箱“鼓”几下,然后“蹦”的一下打开。很多时候要调效果时,需要轮着试,如果有一张图和实际示例效果,那就省很多事...

    meteoric
  • 【HDU - 5845】Best Division(xor-trie、01字典树、dp)

    饶文津
  • 未来已来——如何在VR游戏中实现3D语音

    我们实际使用GME SDK完成相关的开发,一起来看下代码是如何运行的。本篇是基于Google开源的CardBoard SDK进行的示例程序。

    shusen
  • aapt获取apk版本等信息

    简介: aapt即Android Asset Packaging Tool,我们可以在SDK的platform-tools目录下找到该工具。aapt可以查看、 ...

    苦咖啡
  • 【cf842D】Vitya and Strange Lesson(01字典树)

    01字典树保存每个节点下面有几个数,然后当前总异或的是sw,则sw为1的位的节点左右孩子交换(不用真的交换)。左孩子的值小于左边总节点数则mex在左子树,否则在...

    饶文津
  • 每天一道面试题——计算器

    作为软件测试工程师,我们都会经历面试。我常对我的学员说,面试的时候,对于面试官提问的任何问题,不要着急回答,先花几秒钟时间思考面试官提问这个问题的目的:他们为什...

    张树臣

扫码关注云+社区

领取腾讯云代金券