c#中快速排序的学习_.net

最近看了一句话，说的是在现实生活中，会写字的人不见得会写出好文章，学习编程语言就像是学会了写字，学会了编程语言并不一定能写出好程序。

我觉得就是很有道理，以前读书的时候，基本学完了C#中的语法知识，算是入了个门，但是一到写程序就毫无头绪，做出来的程序就像是小学生日记，仅仅只是用一些简单的api把功能拼凑起来，没有一点逻辑性，毫不美观优雅。

所以我决定慢慢的开始学习算法知识，虽然我数学很烂，逻辑能力差到极点，看这些算法的代码看的我是心态爆炸，真的头皮发麻，只有长期坚持学习，一点一点的慢慢进步了。

快速排序是分治法中的一种常见排序算法，主要运用递归求解。

算法思想是将一个数组分为小于等于基准数的子数组和大于基准数的子数组，然后通过递归调用，不断对这两个子数组进行排序，直到数组元素只有0个或1个元素时，停止递归，再将各个排好序的子数组加起来，最终就得到了排好序的数组。

步骤如下：

1. 选择一个基准值

2. 将数组分为两个子数组：小于基准值的元素和大于基准值的元素

3. 对这两个子数组进行排序

接着对子数组重复以上3步，直到子数组无法分解（子数组只有0个或1个元素时）

可以使用函数递归重复上述过程，在递归函数中必须满足2个条件

1.基线条件——指满足某个条件以后，函数不在调用自身进行递归

2.递归条件——满足递归条件就调用自身函数进行递归

我看的书举例是使用Python代码实现的快速排序，代码如下：

 1 def quicksort(array):
 2     if len(array) < 2: #基线条件：为空或者只包含一个元素的数组是“有序”的
 3         return array 
 4     else:#递归条件
 5         pivot = array[0] 
 6         less = [i for i in array[1:] if i<= pivot]#由所有小于等于基准值的元素组成的数组
 7         greater = [i for i in array[1:] if i> pivot]#由所有大于基准值的元素组成的子数组
 8         return quicksort(less) + [pivot] + quicksort(greater)
 9 
10 
11 print(quicksort([10, 5, 2, 3]))

在这段代码里，首先满足递归条件时，取得一个基准数，基准数通常为数组的第一个元素，然后分成两个子数组，一个是小于等于基准数的子数组和大于基准数的子数组，不断进行递归调用对这两个子数组进行排序，最后得到排序好的数组。

书中讲解看完后，头脑里很快就有了思绪，但是当我想把上面的代码转换成C#时，就摸不着头脑，打脑壳的遭不住，因为在C#里并不能像上面一样简简单单的就实现，最主要的就是C#中数组不能通过直接相加来合并。

所以还是在网上看了不少C#快速排序的详解后写出了以下代码：

 1         /// <summary>
 2         /// 快速排序对数组进行升序排序
 3         /// </summary>
 4         /// <param name="array">要排序的数组</param>
 5         /// <param name="leftIndex">从左边遍历的第一个数的索引</param>
 6         /// <param name="rightIndex">从右边遍历的第一个数的索引</param>
 7         public static void QuickSort(int[] array, int leftIndex, int rightIndex)
 8         {
 9             if (leftIndex >= rightIndex)//基线条件
10                 return;
11             int n = leftIndex;
12             int m = rightIndex;
13             int pivot = array[leftIndex];
14             while (n != m)
15             {
16                 for (; n < m; m--)
17                 {
18                     if (array[m] < pivot)
19                     {
20                         array[n] = array[m];//交换位置
21                         break;
22                     }
23                 }
24                 for (; n < m; n++)
25                 {
26                     if (array[n] > pivot)
27                     {
28                         array[m] = array[n];
29                         break;
30                     }
31                 }
32             }
33             array[n] = pivot;//循环完成后已经按照小于基准数和大于基准数左右排好序，基准数放中间。
34             QuickSort(array, leftIndex, n - 1);//对着两个子数组进行递归
35             QuickSort(array, n + 1, rightIndex);
36         }

网上快速排序的思路如上，甚至来说基线条件和我在书中看见的都已经完全不一样，并且和书中的逻辑也不太相同，只是依旧是分治法解决问题。

不仅是分出两个子数组，而是对当前的数组进行排序，排序过程也不好理解，从右至左循环，找出比基准数大的数，再从左至右循环，找出比基准数小的数，然后将两个数字调换位置，到最后只剩一个数的时候，就是基准数该在的位置，把基准数放到这个位置。

所以我足足想了2天，才能够独立写出上面的快速排序代码，不过我已经不知道我到底是真真切切理解了排序的思路，还是说因为看了太久，已经把排序的方式背在脑中了，真是悲哀，聪明的小伙伴一定一下就能学会，我却想了两天连自己也不清楚到底想明白没有了。

最后，我依旧有一个疑问，快速排序的时间复杂度是O(nlogn)，那么上面的Python代码依旧是O(nlogn)吗？

新声明数组，然后将他们赋值，再合并，这样的操作会影响时间复杂度吗？

甚至我想用Linq语法

1             int[] less = (from i in array where i < pivot select i).ToArray();
2             int[] greater = (from i in array where i > pivot select i).ToArray();

返回的数组甚至还是排好序的，那我直接用将这两个数组和基准数加起来不是更简单吗？我已经完全懵逼了，不知道时间复杂度是如何计算的，学习的长路真是漫漫啊！