三大屌丝排序

其实好久没摸算法和数据结构了,今拾排序一练.

说到排序,不得不提及冒泡排序,因为它是最简单也是最屌丝的排序算法:

void Bubble(int *p,int n) {
    for(int i=1;i<n;i++) {
        for(int j=i;j>0 && p[j]<p[j-1];j--) {
            p[j]+=p[j-1];
            p[j-1]=p[j]-p[j-1];
            p[j]-=p[j-1];
        }
    }
}

算法复杂度为O(N^2),但胜在稳定,简单.够屌丝.

插入排序:

void Insert(int *p,int n) {
    for(int i=1;i<n;i++) {
        int pos=0;
        for(;pos<i && p[i]>=p[pos];pos++){}
        if(i!=pos) {
            int val=p[i];
            memmove(&p[pos+1],&p[pos],(i-pos)*sizeof(int));
            p[pos]=val;
        }
    }
}

和冒泡排序极为相似,其算法复杂度也是O(N^2),但相对冒泡排序来说减少了很多交换操作.在链表等数据结构中使用效果更佳.

快速排序:

void Quick(int p,int n) {
    if(n<2) {
        return ;
    }
    int left[MAX]={0},right[MAX]={0},r=0,l=0,val=p[0];
    for(int i=1;i<n;i++) {
        if(p[i]<val) {
            left[l++]=p[i];
        } else {
            right[r++]=p[i];
        }
    }
    Quick(left,l);
    Quick(right,r);
    p[l]=val;
    memcpy(p,left,sizeof(int)l);
    memcpy(&p[l+1],right,sizeof(int)*r);
}

由于使用了数据结构中的堆积树思想,算法复杂度降低到O(NlogN).

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏机器学习从入门到成神

C/C++学习之路(二)

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/sinat_35512245/articl...

612
来自专栏程序员八阿哥

王老板Python面试(5):10个Python面试常问的问题

_class_方法指向了类对象,只用给他赋值类型A,然后调用方法show,但是用完了记得修改回来。

511
来自专栏超然的博客

js数据类型

string、number、Boolean、Array、object、Null、Undefined

771
来自专栏TungHsu

这或许是对小白最友好的python入门了吧——10,元组

元组和列表差不多,但是和列表又不一样,除了长得不一样外,还有一个很大的不同就是元组的元素不能修改。 元组是这样写的(以矩形的长宽为例): rectangle =...

2694
来自专栏Android干货园

Kotlin中级(5)- - - 初识Kotlin中的对象.md

主构造和次构造可以并存么?当然可以。但是如果类有一个主构造函数,那么每个次构造函数都需要委托给主构造函数。也就是说,次构造函数在最后还是要用到主构造函数。

602
来自专栏计算机视觉与深度学习基础

Leetcode 143 Reorder List

Given a singly linked list L: L0→L1→…→Ln-1→Ln, reorder it to: L0→Ln→L1→Ln-1→L2...

1725
来自专栏Golang语言社区

Go队列和堆栈

golang,其实我的实现是利用container/list包实现的,其实container/list包很强大. package main import ...

3417
来自专栏王磊的博客

javascript中Array的操作

concat(组合数组) join(数组转字符串) pop(删除最后一个元素) shift(删除第一个元素) push(在数组尾部添加新元素) unshift(...

2668
来自专栏每日一篇技术文章

Swift3.0 - 对象和类

1.对象中的所有变量或者常量在定义时如果不初始化,在对象初始化的时候,必须初始化,这个是swift安全性考虑,可选类型没有强制性要求初始化,因为系统默认给可选类...

671
来自专栏前端儿

JavaScript 的数据类型 相关知识点

JavaScript的数据类型分为两类:原始类型(primitive type)和对象类型(object type)

702

扫码关注云+社区