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

算法系列15天速成——第一天 七大经典排序【上】。算法就好比程序开发中的利剑，所到之处，刀起头落。

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

1. usingSystem;
2. usingSystem.Collections.Generic;
3. usingSystem.Linq;
4. usingSystem.Text;
5. usingSystem.Threading;
6. usingSystem.Diagnostics;
7.  
8. namespaceQuickSort
9. {
10. publicclassProgram
11. {
12. staticvoidMain(string[]args)
13. {
14. //5次比较
15. for(inti=1;i<=5;i++)
16. {
17. Listlist=newList();
18.  
19. //插入200个随机数到数组中
20. for(intj=0;j<200;j++)
21. {
22. Thread.Sleep(1);
23. list.Add(newRandom((int)DateTime.Now.Ticks).Next(0,10000));
24. }
25.  
26. Console.WriteLine("\n第"+i+"次比较：");
27.  
28. Stopwatchwatch=newStopwatch();
29.  
30. watch.Start();
31. varresult=list.OrderBy(single=>single).ToList();
32. watch.Stop();
33.  
34. Console.WriteLine("\n系统定义的快速排序耗费时间："+watch.ElapsedMilliseconds);
35. Console.WriteLine("输出前是十个数:"+string.Join(",",result.Take(10).ToList()));
36.  
37. watch.Start();
38. newQuickSortClass().QuickSort(list,0,list.Count-1);
39. watch.Stop();
40.  
41. Console.WriteLine("\n俺自己写的快速排序耗费时间："+watch.ElapsedMilliseconds);
42. Console.WriteLine("输出前是十个数:"+string.Join(",",list.Take(10).ToList()));
43.  
44. }
45. }
46. }
47.  
48. publicclassQuickSortClass
49. {
50.  
51. ///
    ///分割函数

    ///
52. ///待排序的数组
53. ///数组的左下标
54. ///
55. ///
56. publicintDivision(Listlist,intleft,intright)
57. {
58. //首先挑选一个基准元素
59. intbaseNum=list[left];
60.  
61. while(left<>
62. {
64. //从数组的右端开始向前找，一直找到比base小的数字为止(包括base同等数)
65. while(left=baseNum)
66. right=right-1;
67.  
68. //最终找到了比baseNum小的元素，要做的事情就是此元素放到base的位置
69. list[left]=list[right];
70.  
71. //从数组的左端开始向后找，一直找到比base大的数字为止（包括base同等数）
72. while(left<>
73. left=left+1;
75.  
76.  
77. //最终找到了比baseNum大的元素，要做的事情就是将此元素放到最后的位置
78. list[right]=list[left];
79. }
80. //最后就是把baseNum放到该left的位置
81. list[left]=baseNum;
82.  
83. //最终，我们发现left位置的左侧数值部分比left小，left位置右侧数值比left大
84. //至此，我们完成了第一篇排序
85. returnleft;
86. }
87.  
88. publicvoidQuickSort(Listlist,intleft,intright)
89. {
90. //左下标一定小于右下标，否则就超越了
91. if(left<>
92. {
94. //对数组进行分割，取出下次分割的基准标号
95. inti=Division(list,left,right);
96.  
97. //对“基准标号“左侧的一组数值进行递归的切割，以至于将这些数值完整的排序
98. QuickSort(list,left,i-1);
99.  
100. //对“基准标号“右侧的一组数值进行递归的切割，以至于将这些数值完整的排序
101. QuickSort(list,i+1,right);
102. }
103. }
104. }
105. }

     

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

     嗯，最后要分享下：

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

     快排的时间复杂度为:

     平均复杂度： N(logN)

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