你所能用到的数据结构(二)

      周末开始更新了,首先感谢各位对我写的东西还能保持兴趣,先回答几个留言中的一个问题和我对无损编码那一节的一个留言的一个看法,第一个是推荐算法书,首先,我不是什么高手和大牛,所以当不起“推荐”这个词。我见过很多人,对于这个问题我觉得很多人都会说出《算法导论》,但是我不完全这么认为,我始终认为人和人是不一样的,《算法导论》肯定是一本经典的书,但是学习知识的目的是要学懂,比谁的能力大不是比谁看的经典书籍多,而是比谁懂得多。所以如果让我推荐的话,我觉得要分三种情况,第一种,你有很深的数学基础,高中特别喜欢做数学题,我觉得可以尝试看看《算法导论》甚至是传说中的《计算机程序设计艺术》,第二种就是高中并不对数学很感兴趣,但是大学确实很喜欢编程但是对于数学看多了觉得头会昏昏的人,其实我特别觉得好的是《算法概论》和《算法设计与分析基础》,除了这两本,我觉得看一些《离散数学》对于培养算法的基本思维方式真很有帮助,第三种是对于数学理解不是那么强的,我觉得不妨看看《编程之美》这类的有实际例子不会那么抽象的书,培养出兴趣,有了兴趣,后面只是时间问题了。

      第二个是对无损编码有一个朋友说的这是“时间换空间”,从编程上说确实是时间换空间,但是这些一般都是在有实际应用背景下的,比如我的所谓研究方向是“可逆水印”,这个玩意儿必须要靠无损编码做前期处理,所以这个看法是正确的,但是却不是最需要考虑的,因为这个有应用背景。

      好了,开始这次的内容,不同于很多数据结构先从列表和堆栈说起,我先几个和数据结构结合不太强的排序算法开始,因为我觉得在学这一系列之前对算法的效率建立一个认识是必要的。

二、从几种“屌丝”的排序算法开始

  先介绍几种简单的时间效率是O(N*N)的排序算法,虽然这些排序算法比较初级,但是任何高级的东西都是从初级的东西演化推理出来的,不学小学的123你也不可能学会高数的微积分。所以说这些算法虽然“屌丝”,但是没有这些“屌丝”哪来的“高帅富”?可以证明的出来,通过交换的排序算法效率最快只能到O(N*logN)。

      除了上面的这个,我还想强调的一点是在有的书里面提到的排序算法是否是稳定的这个概念,所谓有序就是说待排序数列中相等的值在经过排序算法之后是否会交换位置,比如一组数据(2,0,2),在排序之后自然是(0,2,2),如果这个排序算法是稳定的,那么(0,2,2)中第一个出现的2应该是(2,0,2)中的第一个2,也就是待排序数列中的两个2的相对位置不会发生交换。关于稳定的定义可以参看百度的这个http://baike.baidu.com/view/547325.htm?fromTaglist 这个看似不起眼的知识点就是昨天微软校园招聘倒数第二题的考点,不得不说大公司出的题目牛逼。

     选择排序是最为符合人类自然思维的一种排序方式,不断找到数列中的最小值,将其放在目前最小的位置上,简单方便快捷,不得不说是最“屌丝”的排序算法,没有什么特殊的技巧,完全靠两个循环,代码如下所示:

 1 void SelectionSort(int a[],int length)
 2 {
 3     for(int i=0;i<length;i++)
 4     {
 5         cout<<"Sort time number "<<(i+1)<<":";
 6                int min=i;        
 7         int j=i;
 8         for(;j<length;j++)
 9         {
10             if(a[min]>a[j])
11                min=j;
12         }
13         int tmp=a[min];
14         a[min]=a[i];
15         a[i]=tmp;
16 
17         for(int k=0;k<length;k++)
18             cout<<a[k]<<" ";
19         cout<<endl;
20 
21     }
22 }

    运行结果如下所示:

    从结果中可以看到,第一轮排序中,最小的元素3被安排在了第一个位置上,第二轮5被安排在次小的位置上,以此类推。选择排序算法是不是稳定的呢?选择排序明显不是有序的,就像连接里面写的那样,因为你在交换的过程中,如果出现相同的元素,无法保证交换的过程中元素被交换的位置是否在第二次出现该元素之后。

    接下来当然是冒泡排序,这种排序算法通过不断比较相邻两个数的大小并交换位置来达到排序的目的,这种算法比较符合人类的自然思维,这样就自然需要两个循环,第一个循环是遍历整个数组,第二个循环是不停地未排序的数列中两个相邻的元素,每一轮之后,最大的元素都可以排在目前最大的位置(当然这取决于你的比较部分的代码是如何写的),所以这个算法也很容易写出来。

 1 void bubble(int a[],int length)
 2 {
 3     int temp=0;
 4     for(int j=0;j<length;j++)
 5     { 
 6        cout<<"Sort time number "<<(j+1)<<":";
 7       
 8        for (int i=0;i<length-1;i++)
 9         if (a[i]>a[i+1])
10         { 
11             temp=a[i];
12             a[i]=a[i+1];
13             a[i+1]=temp;
14         }
15         for(int k=0;k<length;k++)
16          cout<<a[k]<<" ";
17         cout<<endl;
18     }
19 
20 } 

     其结果如下图所示:

     这个简单的排序算法却反应出了排序算法的一个最初级的思路就是比较和交换,别小看任何不起眼的概念,因为后面大牛们对于排序算法的改进就是通过相近办法减少比较和交换,或者是不做相邻元素的比较。可以看到每一趟排序之后,当前最大的元素都到了当前最大的位置上,冒泡排序算法是稳定的排序算法,但是前提是你不会在比较的过程中使用<=或者>=这种符号,交换两个相等的元素是没有意义的,加上算法一般是到大数据集中才显示出作用,这些环境下一个重要的因子就是要快,这种交换会无谓的增大程序的开销,所以一般在排序算法中不会用到=的交换,你也就不用钻牛角尖的说排序算法的稳定性会取决于用于比较的符号。

      除了冒泡排序,插入排序我觉得是最符合人的排序自然思维方式的拓展,这个算法的思想基本就是不停地排出有序的数列,比如10个数,先将前两个数的顺序排好,再看第三个数,然后将这三个数排好,不断吸收元素,不断的排序,这样会保持了待排序数列的相对稳定性,也保持了算法排序的稳定性。其实现代码如下:

 1 void InsertSort(int numbers[],int array_size)
 2 {
 3     int j;
 4     for(int p=1;p<array_size;p++)
 5     {
 6         cout<<"Sort time number "<<p<<":";
 7         int tmp=numbers[p];
 8         
 9         for(j=p;j>0&&tmp<numbers[j-1];j--)
10         {
11              numbers[j]=numbers[j-1];
12         }
13         numbers[j]=tmp;
14        for(int k=0;k<array_size;k++)
15          cout<<numbers[k]<<" ";
16         cout<<endl;
17     }
18 }

      实现结果如下图所示:

     可以看到这种排序算法,吸收,排序的特点,最开始是两个元素的数组编程有序的,第二次是3个元素变成的,如此往复。

     这三种最简单的排序算法是排序算法的入门,如果想测试其效率,可以使用我上一节的代码,这里我还要说一句的是,我写的这三段代码参数的命名都是不一样的,这是因为我是好几天写的,这也反过来说明了在软件开发中有一个规范的重要性,试想如果是很多人一起开发软件,一样的参数意思,你今天想到用着表示,明天想到用那个表示,对于别人这是一种莫大的痛苦。

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏ACM算法日常

朋友圈(拉姆齐定理)- HDU 6152

拉姆齐Ramsey定理是一个稍微难于理解的定理,该定理又称拉姆齐二染色定理,是要解决这样的问题:

1522
来自专栏贾志刚-OpenCV学堂

图形图像算法中必须要了解的设计模式(2)

AI越来越火热,人工智能已然成风!而人工智能最重要是各种算法,因此机器学习越来越受到追捧,算法越来越被重视。

1082
来自专栏我的python

递归方法的理解

递归思想算是编程中比较常见但对初学者而言又有些难以理解的方法了。在leetcode上刷了几道题都用递归思想成功解决后觉得应该贯彻互联网的开源共享精神,总结一下自...

1190
来自专栏CDA数据分析师

就算不做数据分析师也要学会这8个IF函数

今天所讲的IF函数,包括excel中含有IF的系列函数,共有8个,每个函数列举最了常用的2~3个公式,希望能对同学们有用。 一、IF函数 作用:根据条件进行判断...

2086
来自专栏Java成长之路

【c语言】简单学生信息管理系统

1.有10个学生,每个学生的数据包括学好、姓名、4门课的成绩、总成绩和平均成绩。从键盘输入10个学生的数据(包括学好、姓名以...

1.1K1
来自专栏前端新视界

一道看似非常难的面试算法题

这是昨天面试百度时碰到的一道算法题:任意数分三组,使得每组的和尽量相等(感谢博友提供的关于该问题的相关资料 划分问题)。由于时间仓促,加之面试时头昏脑涨,这道题...

2568
来自专栏喔家ArchiSelf

IOT语义互操作性之本体论

这个系列文章描述了一个单一的语义数据模型来支持物联网和建筑、企业和消费者的数据转换。 这种模型必须简单可扩展, 以便能够在各行业领域之间实现插件化和互操作性。 ...

1315
来自专栏程序员互动联盟

【答疑解惑】失之毫厘谬以千里

1、scanf使用陷阱 ? ? 如果scanf中%d是连着写的如“%d%d”,在输入数据时,数据之间不可以加逗号,只能是空格或tab键或者回车键“1 2” 或 ...

3047
来自专栏数据库

用SQL高性能解决字符串的连续匹配

高性能解决有序集合的连续匹配问题 场景: A集合有8个元素:ali、boy、c、dog、e、f、g、h, B集合有5个元素:boy、c、dog、e、h 问B中...

2009
来自专栏落影的专栏

程序员进阶之算法练习(二十八)

前言 四道题,分别锻炼哈希、贪心、贪心+排序、二分四个能力。 第一题较为简单,后续的题目都需要一定的基础。 贪心是最基础的能力,codeforce有专门的 ...

4619

扫码关注云+社区

领取腾讯云代金券