h啊哈哈哈哈，开心，终于有时间，来搞我们的各种排序算法了
不懂算法的程序员，都不是合格的程序员；
首先要明白两个基本概念；
1.时间复杂度和空间复杂度；
http://blog.csdn.net/booirror/article/details/7707551/
2.还有稳定与不稳定；
首先，你要觉得很神奇：就一个数组+for循环+if+else，就实现我们这么多的排序；
这里，我们要考虑到一个稳定性的考虑；就是当两个数相等的时候；如：冒泡排序，当两个数一样的时候，我们就没有必要交换它（当然，你也可以交换它，这样就不是稳定了），这样就是稳定的
看看我们的快速排序呢是否是稳定的呢；
常见的算法：
1.冒泡排序；
2.选择排序；
3.快速排序；
在做快速排序的算法总结之前；我们先做这样的一道栗子；将数组分成两部分；一部分比key大，一部分比key小；
然后做法，目前有三种；方式一和方式二雷同；方式三和前面两种实现方式完全不同，我具体的开代码的实现；
方式一是存的value，我们也可以存index，大同小异，我这里只写一种；
/// <summary> /// 这个是利用一次遍历，一个数，要么比key大，要么比key小； /// 我们分别申明两个数组；min 和 max 来存储； /// 然后将min 和max 进行合并； /// </summary> /// <param name="arr"></param> public static void TestSplitArr(int [] arr) { int len = arr.Length; int[] min = new int[len]; //只能用最大值的方式进行容纳； int[] max = new int[len]; int key = arr[0]; //默认取第一位吧； int minIndex=0, maxIndex=0; for(int i = 0; i < len; i++) { if (arr[i] < key) { min[minIndex++] = arr[i]; } else { max[maxIndex++] = arr[i]; //等于当成max 来处理； } } //遍历完之后，就会得到我们的；想要的结果；newArr=min+max; int index = 0; for(int i = 0; i < minIndex; i++) { arr[index++] = min[i]; } for (int i = 0; i < maxIndex; i++) { arr[index++] = max[i]; } //这样，就组合完毕啦滴啊； }
然后我们看方式二；方式二的实现，是我们快速排序的基础；
/// <summary> /// 这样的话，我们就需要我么的中间min 和 max 了；这样就节约了我们的内存； /// </summary> /// <param name="arr"></param> public static void TestSplitArr2(int[] arr) { int len = arr.Length; int low = 0; int high = len - 1; int key = arr[0]; //暂定默认为第一位； while (true) { //从左边开始 while (arr[high]>key && low < high) { high--; } //从右边开始； while(arr[low]<key && low < high) { low++; } //找到i 和 j 之后，我们开始交换； if (low >= high) return; //退出我们的查找； //进行交换； int temp = arr[low]; arr[low] = arr[high]; arr[high] = temp; } }
从上面的写法中，我们可以总结一些东西出来；当我们需要进行折半查找的时候；
如果len=5(奇数) loopTimes=len/2=2(向下取整)
如果len=4(偶数) loopTimest=len/2=2(刚好等于2)
这样我们的循环次数（不管奇数偶数），循环的次数都是2次；
如果恰好为偶数，那么根据小标来遍历，刚好遍历完；
如果是是奇数，那么，我们就会少遍历一次；
如果所示：
这样不管是奇数个数的数组，还是偶数个数的数组，我们都有解决方法；
下面我就要上神奇的代码了；
/// <summary> /// /// </summary> public static void TestPointer() { //var arr = new[] {1,2,3,4,5,6}; //偶数 var arr = new[] { 1, 2, 3, 4, 5}; //奇数 int len = arr.Length; int high = len - 1 + 1; int low = 0 - 1; while (low<high) { while (--high > low) { Console.WriteLine("high address output:"+arr[high]); break; } while (++low < high) { Console.WriteLine("low address output:" + arr[low]); break; } } //这个操作的特点四，在进行比较的时候，先进行一次自鞥，或 自减； //当是 偶数的时候， 关键点在 low=2 high=3; 这样的我们的遍历刚好结束；在进来遍历的时候， 先自减一次；--high ==2 这个时候 不满足 high>low 不进行数组输出； //当是 奇数的时候， 关键点在 low=1 high=3; 这样的我们的遍历刚好结束；在进来遍历的时候 先自减一次; --high ==2; 2>1 可以输出我们的中间数（3），下一步；先自加 ++low low=2 high=2 不满足我们的添加，不执行后面的代码； //你可以理解成将我们的中间数，让给了 high 进行输出； //这段是很神奇的； }
这里就涉及一个循环中添加检查的先后顺序的问题；
var arr = new[] { 1, 5, 3, 4, 57, 5, 5, 53 };
这段数组，很神奇；
然后，再来实现，我们的快速排序了三；现在，我将上面的方法改成通用的，就可以实现我们递归调用；
/// <summary> /// 这样我们一次交换就算完成了； /// </summary> /// <param name="arr"></param> /// <param name="low"></param> /// <param name="high"></param> public static int QuickSortUnit(int [] arr ,int low,int high) { while (low < high) { int key = arr[low]; //从high=>low while(arr[high]>=key && low < high) { high--; } while(arr[low]<key && low < high) { low++; } int temp = arr[low]; arr[low]=arr[high]; arr[high] = temp; } return high; } /// <summary> /// 递归调用； /// </summary> /// <param name="arr"></param> /// <param name="low"></param> /// <param name="high"></param> public static void Sort(int [] arr,int low,int high) { if (low >= high) return; int index=QuickSortUnit(arr, low, arr.Length - 1); //完成第一次排序将问题，分成了两个部分；小于key 和 大于的key的部分；一份为2； //然后对不同的部分进行排序； Sort(arr,low,index-1);//左边单元进行排序 Sort(arr,index+1,high);//右边单元进行排序 } /// <summary> /// 测试 /// </summary> public static void Test() { var arr = new int[] {3,4,23,2,333,5,6, }; int low = 0; int high = arr.Length - 1; Sort(arr,low,high); foreach (var item in arr) { Console.WriteLine(item); } }
然后，我们尝试从中间取值为key 进行排序；
这里面，还有一个非常重要的，需要靠的就是，稳定性，当遇到相等的值的时候，如何进行交换呢；？？？？
这个考虑的问题还是比较多的；
1.如何去中间的值？
2.算法是否稳定，当遇到相等的值，我们应该如何处理？ 然后又如何交换呢；
4.插入排序；
5.希尔排序；
6.并归排序；
7.堆排序；
8.计数排序；
9.桶排序；
10基数排序；