三大屌丝排序

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

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

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 条评论
登录 后参与评论

相关文章

来自专栏前端儿

Web 前端颜色值--字体--使用,整理整理

颜色值 CSS 颜色使用组合了红绿蓝颜色值 (RGB) 的十六进制 (hex) 表示法进行定义。对光源进行设置的最低值可以是 0(十六进制 00)。最高值是 2...

2322
来自专栏WOLFRAM

错觉艺术的巅峰,错觉图形大师M.C. Escher的不可能方块的可能模型

1343
来自专栏MelonTeam专栏

Bitmap 源码阅读笔记

导语: Android 系统上的图片的处理,跟Bitmap 这个类脱不了关系,我们有必要去深入阅读里面的源码,以便在工作中能更好的处理Bitmap相关的问题...

2518
来自专栏Petrichor的专栏

Dataset 列表:机器学习研究

In computer vision, face images have been used extensively to develop face recog...

1521
来自专栏Golang语言社区

Knapsack problem algorithms for my real-life carry-on knapsack

I'm a nomad and live out of one carry-on bag. This means that the total weight o...

1142
来自专栏WOLFRAM

向日葵中的数学之美

1843
来自专栏Pulsar-V

Save Camera Document

#pragma once #include "HCCamera.h" #include <time.h> #include <cstdio> #incl...

2828
来自专栏linux驱动个人学习

高通Audio中ASOC的machine驱动

ASoC被分为Machine、Platform和Codec三大部分,其中的Machine驱动负责Platform和Codec之间的耦合以及部分和设备或板子特定的...

9784
来自专栏增长技术

App Guide相关

##TourGuide https://github.com/worker8/TourGuide

702
来自专栏码匠的流水账

java9系列(五)Stack-Walking API

java9新增这个类的目的是提供一个标准API用于访问当前线程栈,之前只有Throwable::getStackTrace、Thread::getStackTr...

421

扫码关注云+社区