【IT168技术文档】
最近测试了一个自己写的快速排序，和System.Array.Sort做了个性能对比，发现System.Array.Sort比自己写的排序算法要快很多，拿20W和1000W随机数来测试效率相差40%左右，结果如下：
快速排序的主要思想就是：将待排序数组以某一个元素为阈值分为两个子列，一个子列包含所有比改阈值小的元素，另一个子列反之。这样只要将这两个子列排好序，整个数组也就排好序了。这里有一个关键的子过程就是划分的过程Partition，一般可以选择数组中任意的元素作为划分阈值，这里选择的是数组中最右端的元素。
Partition使用了二分查找类似的思想：使用两个索引器从数组的两端进行遍历，左边的索引器遇到比阈值大的元素停止，右边的索引器遇到比自己小的元素停止，然后交换这两个元素，依次循环。这样数组就划分为了比该阈值大和小（含等于）两个子列了。
自己写的快速排序：
/// <summary> /// Swap position /// </summary> /// <param name="v"></param> /// <param name="index1"></param> /// <param name="index2"></param> private void Swrap(int[] v, int index1, int index2) { int temp = v[index1]; v[index1] = v[index2]; v[index2] = temp; } /// <summary> /// Split into left and right sub-table /// </summary> private int PivotIndex(int[] v, int first, int last) { if (last == first) { return last; } if (last - first == 1) { return first; } int mid = (first + last) / 2; int midVal = v[mid]; //Swap v[first] v[mid] Swrap(v, first, mid); int scanA = first + 1; int scanB = last - 1; for (; ; ) { while (scanA <= scanB && v[scanA] < midVal) { scanA++; } while (scanB > first && midVal <= v[scanB]) { scanB--; } if (scanA >= scanB) { break; } Swrap(v, scanA, scanB); scanA++; scanB--; } Swrap(v, first, scanB); return scanB; } public void Sort(int[] v, int first, int last) { if (last - first <= 1) { return; } if (last - first == 2) { //Sub-table contains two elements if (v[first] > v[last - 1]) { Swrap(v, first, last - 1); } return; } else { int pivotIndex = PivotIndex(v, first, last); Sort(v, first, pivotIndex); Sort(v, pivotIndex + 1, last); } }
