- A+
阳光明媚的一天，狄霸哥有点儿想出去走走，毕竟一连7天7夜躲在自己造的豪华大别墅里面。要不是外面的太阳明媚无比，咕咕咕，好吧，要不是肚子饿了，没有存粮了，我才不出去呢？豪华大别墅爽到爆炸啊！
狄霸哥走在街道上，看着街上的美食框框的流口水，他走进了一家豪华的大旅馆，吆喝小二过来，豪气对问小二这里有什么好吃的。小二说：口水鸡，黄金猪蹄，麻婆豆腐.....!狄霸哥：我不知到哪个好吃的，这样吧，简单一点，全部都给我上一份吧！我这人做事就喜欢简单！小二：好嘞！这位客官。
吧唧吧唧，吃得走不动的狄霸哥实在是吃不下了，准备买单的时候，呃，没有带钱。但是狄霸哥一点都不慌，利用程序之力绘制出大量的金币，叫小二过来买单，摔出大量的金币，亮瞎了小二的眼睛。看着小二一脸懵逼，狄霸哥洋洋得意。突然，小二：老板，这里有人用假币。棒棒棒，来了一群人，把狄霸哥围了起来，这下狄霸哥蒙蔽了，恨自己没学到家啊！
善良的老板没有用武力解决问题，而是甩出了一大本记账本，里面有所有客户的消费累计，但是没有排序好，要狄霸哥将这个由低到高的排序一下。仁慈的老板说了也就10W个客户罢了。苦逼的狄霸哥一脸惆怅，突然他想到了选择排序。
选择排序
选择排序，通过对比每一个元素来选择一个合适的数据来放置在合适的位置上。一个很简单的排序算法。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
static void SortChoice(int[] datas) { int length = datas.Length; int index = 0; for (int i = 0; i < length; i++) { index = i; for (int j = i + 1; j < length; j++) { if (datas[j] < datas[index]) { //选取更合适原来位置的值 index = j; } } if (index != i) { //有更合适这个位置的数，进行交换 int temp = datas[i]; datas[i] = datas[index]; datas[index] = temp; } } } |
在SortChoice函数中，有一个嵌套的循环，其中内层循环是从i+1开始的，i表示的是要对比的元素，i+1开始，表示只对比后面的元素，因为前面的已经比较过了
例如：5 1 3 9，一、首先比较 5 和 1，发现1小，所以交换，变为 1 5 3 9。二、再比较1 和 3，比较1 和 9，都比1大，不用交换，变为：1 5 3 9，此时你可以发现1这个元素已经和所有的元素都对比过了，所以下轮循环就没必要再和前面元素对比了。三、进行对比 5 和 3 ，3小，交换，变为：1 3 5 9。四、继续对比3和9，5和9，好了排序好了
选择排序的层层对比数是递减的，由n-1递减到1，所以执行时间为 （n-1+1）* n/2 = O(n^2)。哒哒哒，狄霸哥等了几十秒了，所有用户的数据才排序好，不耐烦的狄霸哥很是嫌弃，想要更快的解决办法。突然狄霸哥想到了快速排序。
快速排序
快速排序是通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
static List<int> quickSort(List<int> datas) { int length = datas.Count; if (length < 2) { return datas; } //随机一个参考数 Random r = new Random(); int random_index = r.Next(0, length); int val = datas[random_index]; datas.RemoveAt(random_index); List<int> left = new List<int>(); List<int> right = new List<int>(); foreach (int data in datas) { if (data < val) { left.Add(data); } else { right.Add(data); } } left = quickSort(left); right = quickSort(right); left.Add(val); left.AddRange(right); return left; } |
主要思想就是每个大块都分成分成3块，直到不能分为止，数组只有一个元素或者没有，其中一块就是中间那块（参考值），把比参考值小的放在左边，大的放在右边，然后继续对左边的也这样做，右边的也这样做，最后分成了n块，直到每一块都是排好序的（只有一个元素或则没有，当然是排好序的了），而且都是通过参考值来排好序的，所以合并起来，就排好了
例如：5 1 3 9，随机参考值为5，分为3块：1 3，5，9。再对左右边执行分块，右边只有一个元素，所以直接返回，左边为：1 3，随机参考数为：1，3比1大所以放在右边，左边为空，此时3块为：null，1，3。再对左右边进行分割，左边为空，右边只有一个，所以直接返回。不能再分割了，进行合并操作，从栈顶开始，null,1,3合并为：1 3。再进行1 3，5，9合并，最总得到：1 3 5 9
快速排序的运行时间为O(nlog(n))，运气不好的话，其实也是O(n^2)。这次狄霸哥很是满意，几百毫秒不到一秒钟就完成排序了。这里采用了集合来管理元素分组，这样也比较明确快速排序的思想。可能是这拖慢了速度，不然其实几十毫秒就能完成。可以去我的笔记那里看不用List的办法。
一般来说，数据库等代码等的排序都是使用的快速排序算法，快速排序算法的优势在数据量越来越大的时候具有更显著的效果，而选择排序只适合在数据量小的情况下使用。
狄霸哥拿着已经排好序的账本，甩到了旅馆老板的脸上。旅馆老板一脸懵逼的看着已经排好序的账本，打呼一声：大神！在众多诧异的眼光下，狄霸哥潇洒的走出了旅馆门口，这样就吃了个霸王餐，真是爽！
