算法基础：冒了个泡，快了个排 _算法

文章插图

算法是程序员手中的利剑，所到之处，刀起头落。
四大类（七把宝剑）排序算法交换排序：包括冒泡排序，快速排序。
选择排序：包括直接选择排序，堆排序。
插入排序：包括直接插入排序，希尔排序。
合并排序：合并排序。
前端时间普及的基础《算法的时间和空间复杂度，就是这么简单》，得到了程序员们不错的反响，所以我再多出一些实践，帮助大家磨一磨手中的利剑。
今天我们先来比较一下冒泡和快排，让他们PK一把。
冒泡排序首先我们自己来设计一下“冒泡排序” ，这种排序很现实的例子就是：
我抓一把沙仍进水里，那么沙子会立马沉入水底，沙子上的灰尘会因为惯性暂时沉入水底，但是又会立马像气泡一样浮出水面，最后也就真相大白咯。
关于冒泡的思想，我不会说那么官方的理论，也不会贴那些文字上来，我的思想就是看图说话。
那么我们就上图.

文章插图

要达到冒泡的效果，我们就要把一组数字竖起来看，大家想想，如何冒泡？如何来体会重的沉底，轻的上浮？
第一步: 我们拿40跟20比，发现40是老大，不用交换。
第二步: 然后向前推一步，就是拿20跟30比，发现30是老大，就要交换了。
第三步：拿交换后的20跟10比，发现自己是老大，不用交换。
第四步：拿10跟50交换，发现50是老大，进行交换。
最后，我们经过一次遍历，把数组中最小的数字送上去了，看看，我们向目标又迈进了一步。
现在大家思想都知道了，下面我们就强烈要求跟快排较量一下，不是你死就是我活。
1 using System; 2 using System.Collections.Generic; 3 using System.Linq; 4 using System.Text; 5 using System.Diagnostics; 6 using System.Threading; 78 namespace BubbleSort 9 {10 public class Program11 {12 static void Main(string[] args)13 {14 //五次比较15 for (int i = 1; i <= 5; i++)16 {17 List<int> list = new List<int>();18 //插入2k个随机数到数组中19 for (int j = 0; j < 2000; j++)20 {21 Thread.Sleep(1);22 list.Add(new Random((int)DateTime.Now.Ticks).Next(0, 100000));23 }24 Console.WriteLine("n第" + i + "次比较：");25 Stopwatch watch = new Stopwatch();26 watch.Start();27 var result = list.OrderBy(single => single).ToList();28 watch.Stop();29 Console.WriteLine("n快速排序耗费时间：" + watch.ElapsedMilliseconds);30 Console.WriteLine("输出前是十个数:" + string.Join(",", result.Take(10).ToList()));31 watch.Start();32 result = BubbleSort(list);33 watch.Stop();34 Console.WriteLine("n冒泡排序耗费时间：" + watch.ElapsedMilliseconds);35 Console.WriteLine("输出前是十个数:" + string.Join(",", result.Take(10).ToList()));36 }37 }38 39 //冒泡排序算法40 static List<int> BubbleSort(List<int> list)41 {42 int temp;43 //第一层循环：表明要比较的次数，比如list.count个数，肯定要比较count-1次44 for (int i = 0; i < list.Count - 1; i++)45 {46 //list.count-1：取数据最后一个数下标， 47 //j>i: 从后往前的的下标一定大于从前往后的下标，否则就超越了。48 for (int j = list.Count - 1; j > i; j--)49 {50 //如果前面一个数大于后面一个数则交换51 if (list[j - 1] > list[j])52 {53 temp = list[j - 1];54 list[j - 1] = list[j];55 list[j] = temp;56 }57 }58 }59 return list;60 }61 }62 }