江苏龙网

  1. 主页 > 生活百科 > >

算法基础：冒了个泡，快了个排( 二 )

算法


其实思想是蛮简单的 ， 就是通过第一遍的遍历（让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 。
1 using System; 2 using System.Collections.Generic; 3 using System.Linq; 4 using System.Text; 5 using System.Threading; 6 using System.Diagnostics; 78 namespace QuickSort 9 { 10 public class Program 11 { 12 static void Main(string[] args) 13 { 14 //5次比较 15 for (int i = 1; i <= 5; i++) 16 { 17 List<int> list = new List<int>(); 1819 //插入200个随机数到数组中 20 for (int j = 0; j < 200; j++) 21 { 22 Thread.Sleep(1); 23 list.Add(new Random((int)DateTime.Now.Ticks).Next(0, 10000)); 24 } 2526 Console.WriteLine("n第" + i + "次比较："); 2728 Stopwatch watch = new Stopwatch(); 2930 watch.Start(); 31 var result = list.OrderBy(single => single).ToList(); 32 watch.Stop(); 3334 Console.WriteLine("n系统定义的快速排序耗费时间：" + watch.ElapsedMilliseconds); 35 Console.WriteLine("输出前是十个数:" + string.Join(",", result.Take(10).ToList())); 3637 watch.Start(); 38 new QuickSortClass().QuickSort(list, 0, list.Count - 1); 39 watch.Stop(); 4041 Console.WriteLine("n俺自己写的快速排序耗费时间：" + watch.ElapsedMilliseconds); 42 Console.WriteLine("输出前是十个数:" + string.Join(",", list.Take(10).ToList())); 4344 } 45 } 46 } 4748 public class QuickSortClass 49 { 5051 ///<summary> 52 /// 分割函数 53 ///</summary> 54 ///<param name="list">待排序的数组</param> 55 ///<param name="left">数组的左下标</param> 56 ///<param name="right"></param> 57 ///<returns></returns> 58 public int Division(List<int> list, int left, int right) 59 { 60 //首先挑选一个基准元素 61 int baseNum = list[left]; 6263 while (left < right) 64 { 65 //从数组的右端开始向前找 ， 一直找到比base小的数字为止(包括base同等数) 66 while (left < right && list[right] >= baseNum) 67 right = right - 1; 6869 //最终找到了比baseNum小的元素 ， 要做的事情就是此元素放到base的位置 70 list[left] = list[right]; 7172 //从数组的左端开始向后找 ， 一直找到比base大的数字为止（包括base同等数） 73 while (left < right && list[left] <= baseNum) 74 left = left + 1; 757677 //最终找到了比baseNum大的元素 ， 要做的事情就是将此元素放到最后的位置 78 list[right] = list[left]; 79 } 80 //最后就是把baseNum放到该left的位置 81 list[left] = baseNum; 8283 //最终 ， 我们发现left位置的左侧数值部分比left小 ， left位置右侧数值比left大 84 //至此 ， 我们完成了第一篇排序 85 return left; 86 } 8788 public void QuickSort(List<int> list, int left, int right) 89 { 90 //左下标一定小于右下标 ， 否则就超越了 91 if (left < right) 92 { 93 //对数组进行分割 ， 取出下次分割的基准标号 94 int i = Division(list, left, right); 9596 //对“基准标号“左侧的一组数值进行递归的切割 ， 以至于将这些数值完整的排序 97 QuickSort(list, left, i - 1); 9899 //对“基准标号“右侧的一组数值进行递归的切割 ， 以至于将这些数值完整的排序100 QuickSort(list, i + 1, right);101 }102 }103 }104 }


推荐阅读


上一篇：空调扇滴水什么原因,空调扇可以不放水吹吗

下一篇：装修好的房子漏电怎么办,家里漏电有什么危害