生活中无处不在都是被排序过的东西，电子邮箱中的邮件按时间来排序，考完试后出了成绩也会进行一定的排序。在面试中，排序算法也是层出不穷，从简单的冒泡排序问到快速排序，再问到堆排序，希尔排序……现在，让我们开启排序之旅吧~
说到排序，给出了一定的数据，我们最容易想到的，其实并不是冒泡，也并不是快速等排序法，为什么？这些算法虽然有效率上或者思想上的优势，但，如果只是将一堆凌乱的数据放在你面前，第一反应，目的只是将它排序排好，至于什么方法，有什么样的效率，是不会去思考的，因为，如果你连最基础的排序都想不出来的话，又从哪里去思考如何提高效率呢？
假设现在在面前的凌乱的数据有：5，2，4，1，8，10，3
数据结构中的算法先撇开，从我们最基础的思维来做，只需借助一个一维数组就可以解决这个问题，此处，记得先忽略空间上的浪费情况，我们的目的是用一维数组完成排序的操作……
定义一个大小为11的数组: int[] num = new int[11];
1 int[] num = new int[11];
好，现在有了11个变量，num[0]~num[10]，此时，我们需要做的是，将数字填入数组中，比如，第一个数是5，则num[5] = 1, 同理，遇到数字2则num[2]=1, 遇到数字4则num[4]=1……
1 for (int h = 0; h < sortNum.Length; h++) 2 { 3 for (int j = 0; j < 11; j++) 4 { 5 if (sortNum[h] == j) 6 { 7 num[j]++; 8 } 9 }10 } 最后，遍历num数组将num[i]中的值输出，由于此例没有重复数字，因此，只需要验证num[i]!=0即可以将i输出：
1 for (int i = 10; i >= 0; i--)2 {3 if (num[i] != 0)4 {5 Console.Write("{0} ", i);6 }7 } 以上是将凌乱的数据从大到小排列，这段代码的排序只针对没有重复或者去除重复的数据进行排序，那么，有重复数据如何做呢？
假设现在的凌乱数据是：5，2，4，1，8，5，10，3， 这里出现了两次5， 如果再用上面的代码只会输出一个5，接下来的代码用从小到大排序并确保不遗漏数据：
1 for (int i = 0; i <= 10; i++)2 {3 for (int j = 1; j <= num[i]; j++)4 {5 Console.Write("{0} ", i);6 }7 } 以上的排序算是告一段落了，其实这种排序方法也可以称为“桶排序”，不过真正的桶排序比这个要复杂一些。
冒泡排序
说到冒泡排序，几乎已经没有人会陌生了，这里不做冗余介绍，只是需要明白，冒泡排序的基本思想是：每次比较两个相邻的元素，如果它们的顺序错误就把它们交换过来。而冒泡排序的核心部分是双重嵌套循环，这里使用泛型，让其能通用于任何数据，面试的时候如果可以允许你写冒泡排序，写出带泛型参数的冒泡有加分哟~
1 public static void BubbleSort(T[] array) 2 { 3 BubbleSort (array, Comparer .Default); 4 } 5 6 private static void BubbleSort (T[] array, IComparer comparer) 7 { 8 int length = array.Length; 9 10 for (int i = 0; i <= length - 2; i++)11 {12 for (int j = length - 1; j >= 1; j--)13 {14 if (comparer.Compare(array[j], array[j - 1]) < 0)15 {16 swap(ref array[j], ref array[j - 1]);17 }18 }19 }20 21 for (int i = 0; i < array.Length; i++)22 {23 Console.Write("{0} ", array[i]);24 }25 26 }27 28 private static void swap (ref T x, ref T y)29 {30 T temp = x;31 x = y;32 y = temp;33 }
冒泡排序解决了第一个解决方案中空间浪费的问题，当然，引入了泛型也增加了其可移植性，但是冒泡排序的执行效率并不高，其复杂度达到了O(N2)。
快速排序
快速排序需要设置一个基准数，假设最左边的数为基准数，然后设置两个哨兵i, j,哨兵i站在最左边向右走，哨兵j站在最右边向左走，记住，哨兵j必须先走，遇到比基准数数小的数字即停止，然后哨兵i开始走，遇到比基准数大的数字停止，两者交换值之后继续向前，直至两者相遇，将相遇时的值与基准数交换，此时，基准数左边的数均小于基准数，而基准数右边的值均大于基准数。多次反复此操作直至排序完成。
快速排序之所以笔记快，是因为相比冒泡排序来说，每次交换都是跳跃式的。当然，在最坏的情况下，仍可能是相邻的两个数进行交换，因此，快速排序的最差时间复杂度和冒泡排序是一样的，它的平均复杂度是O(NlogN)。
其实快速排序是基于一种叫做“二分”的思想，代码如下：
1 public static void QuickSort(int[] sortNum, int left, int right) 2 { 3 if (left > right) 4 { 5 return; 6 } 7 int temp = sortNum[left]; 8 int i = left; 9 int j = right;10 int swap;11 12 while (i != j)13 {14 while (sortNum[j] >= temp && i < j)15 {16 j--;17 }18 while (sortNum[i] <= temp && i < j)19 {20 i++;21 }22 if (i < j)23 {24 swap = sortNum[i];25 sortNum[i] = sortNum[j];26 sortNum[j] = swap;27 }28 }29 sortNum[left] = sortNum[i];30 sortNum[i] = temp;31 QuickSort(sortNum, left, i - 1);32 QuickSort(sortNum, i + 1, right); 33 } 除了以上列出的排序算法之外，我们熟知的比较简单的还有插入排序，选择排序，以及有点难度的希尔排序，归并排序等，研究排序的目的有三个，第一，从日常生活中常见的排序现象来学习算法是什么，第二，从不同的算法中学习不同的思想，开拓自己的算法思维，在以后的编码过程中也能有多种选择，第三，知道不同的算法有不同的优劣势，选择不同的方式可能会遇到不同的问题，是选择节约时间还是节约空间，如何节约比较合适。
以下代码为测试代码：
1 public class Program 2 { 3 static int[] num = { 5, 2, 4, 1, 8, 5, 10, 3 }; 4 static void Main(string[] args) 5 { 6 BucketSortTest(); 7 BubbleSortTest(); 8 QuickSortTest(); 9 Console.ReadKey();10 }11 12 private static void BucketSortTest()13 {14 Sorting.BucketSort(num);15 }16 17 private static void BubbleSortTest()18 {19 Sorting.BubbleSort (num);20 }21 22 private static void QuickSortTest()23 {24 Sorting.QuickSort(num, 0, num.Length-1);25 26 for (int t = 0; t < num.Length; t++)27 {28 Console.Write("{0} ", num[t]);29 }30 }31 } 测试结果：
