文档章节

算法系列15天速成——第一天 七大经典排序【上】

BobbyLou
 BobbyLou
发布于 2015/08/20 10:42
字数 1260
阅读 20
收藏 1

今天是开篇,得要吹一下算法,算法就好比程序开发中的利剑,所到之处,刀起头落。

 

针对现实中的排序问题,算法有七把利剑可以助你马道成功。

 

首先排序分为四种: 

      交换排序: 包括冒泡排序,快速排序。

      选择排序: 包括直接选择排序,堆排序。

      插入排序: 包括直接插入排序,希尔排序。

      合并排序: 合并排序。

 

那么今天我们讲的就是交换排序,我们都知道,C#类库提供的排序是快排,为了让今天玩的有意思点,

我们设计算法来跟类库提供的快排较量较量。争取KO对手。

 

冒泡排序:

首先我们自己来设计一下“冒泡排序”,这种排序很现实的例子就是:

我抓一把沙仍进水里,那么沙子会立马沉入水底, 沙子上的灰尘会因为惯性暂时沉入水底,但是又会立马像气泡一样浮出水面,最后也就真相大白咯。

 

关于冒泡的思想,我不会说那么官方的理论,也不会贴那些文字上来,我的思想就是看图说话。

那么我们就上图.

           

要达到冒泡的效果,我们就要把一组数字竖起来看,大家想想,如何冒泡?如何来体会重的沉底,轻的上浮?

 

第一步:  我们拿40跟20比,发现40是老大,不用交换。

第二步:  然后向前推一步,就是拿20跟30比,发现30是老大,就要交换了。

第三步:拿交换后的20跟10比,发现自己是老大,不用交换。

第四步:拿10跟50交换,发现50是老大,进行交换。

 

最后,我们经过一次遍历,把数组中最小的数字送上去了,看看,我们向目标又迈进了一步。

 

现在大家思想都知道了,下面我们就强烈要求跟快排较量一下,不是你死就是我活。

复制代码

  System;
  System.Collections.Generic;
  System.Linq;
  System.Text;
  System.Diagnostics;
  System.Threading;
 
  BubbleSort
 {
       Program
     {
           Main([] args)
         {
                           ( i = ; i <= ; i++)
             {
                 List<> list =  List<>();
                                   ( j = ; j < ; j++)
                 {
                     Thread.Sleep();
                     list.Add( Random(()DateTime.Now.Ticks).Next(, ));
                 }
                 Console.WriteLine( + i + );
                 Stopwatch watch =  Stopwatch();
                 watch.Start();
                  result = list.OrderBy(single => single).ToList();
                 watch.Stop();
                 Console.WriteLine( + watch.ElapsedMilliseconds);
                 Console.WriteLine( + .Join(, result.Take().ToList()));
                 watch.Start();
                 result = BubbleSort(list);
                 watch.Stop();
                 Console.WriteLine( + watch.ElapsedMilliseconds);
                 Console.WriteLine( + .Join(, result.Take().ToList()));
             }
         }
 
                   List<> BubbleSort(List<> list)
         {
              temp;
                           ( i = ; i < list.Count - ; i++)
             {
                                    ( j = list.Count - ; j > i; j--)
                 {
                                           (list[j - ] > list[j])
                     {
                         temp = list[j - ];
                         list[j - ] = list[j];
                         list[j] = temp;
                     }
                 }
             }
              list;
         }
     }
 }

复制代码

 

 

呜呜,看着这两种排序体检报告,心都凉了,冒泡被快排KO了,真惨,难怪人家说冒泡效率低,原来真tmd低。

 

快速排序:

既然能把冒泡KO掉,马上就激起我们的兴趣,tnd快排咋这么快,一定要好好研究一下。

首先上图:    

 

从图中我们可以看到:

left指针,right指针,base参照数。

其实思想是蛮简单的,就是通过第一遍的遍历(让left和right指针重合)来找到数组的切割点。

第一步:首先我们从数组的left位置取出该数(20)作为基准(base)参照物。

第二步:从数组的right位置向前找,一直找到比(base)小的数,

            如果找到,将此数赋给left位置(也就是将10赋给20),

            此时数组为:10,40,50,10,60,

            left和right指针分别为前后的10。

第三步:从数组的left位置向后找,一直找到比(base)大的数,

             如果找到,将此数赋给right的位置(也就是40赋给10),

             此时数组为:10,40,50,40,60,

             left和right指针分别为前后的40。

第四步:重复“第二,第三“步骤,直到left和right指针重合,

             最后将(base)插入到40的位置,

             此时数组值为: 10,20,50,40,60,至此完成一次排序。

第五步:此时20已经潜入到数组的内部,20的左侧一组数都比20小,20的右侧作为一组数都比20大,

            以20为切入点对左右两边数按照"第一,第二,第三,第四"步骤进行,最终快排大功告成。

 

同样,我们把自己设计的快排跟类库提供的快拍比较一下。看谁牛X。

复制代码

  System;
  System.Collections.Generic;
  System.Linq;
  System.Text;
  System.Threading;
  System.Diagnostics;
 
  QuickSort
 {
       Program
     {
           Main([] args)
         {
                           ( i = ; i <= ; i++)
             {
                 List<> list =  List<>();
 
                                   ( j = ; j < ; j++)
                 {
                     Thread.Sleep();
                     list.Add( Random(()DateTime.Now.Ticks).Next(, ));
                 }
 
                 Console.WriteLine( + i + );
 
                 Stopwatch watch =  Stopwatch();
 
                 watch.Start();
                  result = list.OrderBy(single => single).ToList();
                 watch.Stop();
 
                 Console.WriteLine( + watch.ElapsedMilliseconds);
                 Console.WriteLine( + .Join(, result.Take().ToList()));
 
                 watch.Start();
                  QuickSortClass().QuickSort(list, , list.Count - );
                 watch.Stop();
 
                 Console.WriteLine( + watch.ElapsedMilliseconds);
                 Console.WriteLine( + .Join(, list.Take().ToList()));
 
             }
         }
     }
 
       QuickSortClass
     {
 
                          Division(List<> list,  left,  right)
         {
                           baseNum = list[left];
 
              (left < right)
             {
                                   (left < right && list[right] >= baseNum)
                     right = right - ;
 
                                  list[left] = list[right];
 
                                   (left < right && list[left] <= baseNum)
                     left = left + ;
 
 
                                  list[right] = list[left];
             }
                          list[left] = baseNum;
 
                            left;
         }
 
           QuickSort(List<> list,  left,  right)
         {
                           (left < right)
             {
                                   i = Division(list, left, right);
 
                                  QuickSort(list, left, i - );
 
                                  QuickSort(list, i + , right);
             }
         }
     }
 }

复制代码

 

 

不错,快排就是快,难怪内库非要用他来作为排序的标准。

 

嗯,最后要分享下:

冒泡的时间复杂度为: 0(n) - 0(n^2)

快排的时间复杂度为: 

    平均复杂度: N(logN)

    最坏复杂度:  0(n^2)


添加好友

小额赞助

微信
支付宝

本文转载自:http://www.cnblogs.com/huangxincheng/archive/2011/11/14/2249046.html

BobbyLou
粉丝 8
博文 149
码字总数 5825
作品 0
海淀
程序员
私信 提问
我的2013,成功当选微软最有价值专家

伴随着圣诞节的到来,我的2013也即将画上句号,回首这一年,收获颇多。首先,在这一年里我结识了很多优秀的朋友,也从他们身上学到了很多做事和做人的道理。其次,无论从编程技术还是个人成长...

morewindows
2013/12/24
0
0
MoreWindows博客目录(微软最有价值专家,原创技术文章152篇)

为了方便大家查找和学习,现将本人博客中所有博客文章列出目录。 一. 白话经典算法 目前有17篇,分为七大排序和经典面试题讲解两大类 1. 《白话经典算法系列之一 冒泡排序的三种实现》 2. 《...

morewindows
2013/12/24
0
0
STL系列之四 heap 堆

下面再介绍STL中与堆相关的4个函数——建立堆make_heap(),在堆中添加数据push_heap(),在堆中删除数据pop_heap()和堆排序sort_heap(): 头文件 #include 下面的_First与_Last为可以随机访问...

彭博
2012/04/12
706
0
STL系列之四 heap 堆

下面再介绍STL中与堆相关的4个函数——建立堆make_heap(),在堆中添加数据push_heap(),在堆中删除数据pop_heap()和堆排序sort_heap(): 头文件 #include 下面的_First与_Last为可以随机访问...

长平狐
2012/12/10
95
0
白话经典算法系列之十 一道有趣的GOOGLE面试题

微博http://weibo.com/MoreWindows已开通,欢迎关注。 最近在微博上看到一道有趣的GOOGLE面试题,见下图: 文字版: 一个大小为n的数组,里面的数都属于范围[0, n-1],有不确定的重复元素,找...

长平狐
2012/12/10
112
0

没有更多内容

加载失败,请刷新页面

加载更多

CSS定位

CSS定位 relative相对定位 absolute绝对定位 fixed和sticky及zIndex relative相对定位 position特性:css position属性用于指定一个元素在文档中的定位方式。top、right、bottom、left属性则...

studywin
19分钟前
4
0
从零基础到拿到网易Java实习offer,我做对了哪些事

作为一个非科班小白,我在读研期间基本是自学Java,从一开始几乎零基础,只有一点点数据结构和Java方面的基础,到最终获得网易游戏的Java实习offer,我大概用了半年左右的时间。本文将会讲到...

Java技术江湖
昨天
5
0
程序性能checklist

程序性能checklist

Moks角木
昨天
7
0
VUE 计算属性

本文转载于:专业的前端网站▶VUE 计算属性 1、示例代码 <!DOCTYPE html><html lang="zh"> <head> <meta charset="UTF-8" /> <title>vue示例</title> </hea......

前端老手
昨天
6
0
快速搭建LNMT平台和环境部署 Tomcat详解

Tomcat部署的基本概念 1. CATALINA_HOME与CATALINA_BASE分别指什么?     CATALINA_HOME指的是Tomcat的安装目录     bin:\\Tomcat一些脚本存放目录,比如启动脚本startup.bat/start...

网络小虾米
昨天
8
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部