排序详解之快速排序
快速排序
快速排序使用分治的思想，以某个数为分割点，每一趟排序下来，左边数都比它小，右边数都比它大，然后再对左右两边数组做递归操作。
时间复杂度(平均情况)：n*lg(n)
排序步骤：
1. 以左边首元素为分割点，拿出来存在midElement里（这时候左边首位置空了）
2. 从右边找比midElement小的数，放在刚才左边空的位置，就是首位（这时，右边有一个位置空了）
3. 从左边找比midElement大的数，放在右边空的位置
4. 循环执行，直到左边索引>=右边索引
5. 把midElement放在当前左索引处
6. 以midElement为分割点，递归执行左半部分和右半部分
假设这样一组数：
5,8,1,3,7,9,2
快速排序的过程：
Step1 : 把首元素放入midElement变量中
第二步：
从右边找比MidElement小的，放左边空白位置，从左边找比midElement大的，放右边空白位置，直到leftIndex>=rightIndex
第一趟快速排序完成了，可以发现5左边的数都比5小，5右边的数都比它大。然后的步骤就是以5，左边元素为一组，右边元素为一组，做同样的事情，在此就不逐步演示了。
参考代码：
public List<int> QuickSort(List<int> arr)
{
var right= arr.Count-1;
Quick_Sort(arr,0,right);
returnarr;
}
public voidQuick_Sort(List<int> arr, int left, int right)
{
if (left>= right) return;
var refNum= arr[left];
var low =left;
var high =right;
while (low< high)
{
while(low < high && arr[high] >= refNum)
high--;
if(low < high)
arr[low++] = arr[high];
while(low < high && arr[low] < refNum)
low++;
if(low < high)
arr[high--] = arr[low];
}
arr[low] =refNum;
Quick_Sort(arr,left,right - 1);
Quick_Sort(arr,left + 1,right);
}相信你现在已经明白快速排序了，感谢您的阅读！