原理
快速排序（Quicksort）是对冒泡排序的一种改进。
- 从数列中挑出一个元素，称为"基准"(pivot);
- 排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在本次排序退出之后，该基准就处于数列的中间位置。这个称为分区(partition)操作;
- 递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。
例子
将无序数组[3,6,4,2,5,1]进行快速排序
1)，先把第一项[3]取出来作为基准依次与其余项进行比较(3出列后大喝一声,比我小的站前边,比我大的站后边,行动吧!霸气侧漏~)，
如果比[3]小就放[3]前边,2 1都比[3]小,全部放到[3]前边
如果比[3]大就放[3]后边,6 4 5比[3]大,全部放到[3]后边,
一趟排完后变成下边这样:
排序前：3,6,4,2,5,1
排序后：2,1,3,6,4,5
2)，对前面一半[2,1]继续进行快速排序
重复步骤1)后变成下边这样:
排序前：2,1
排序后：1,2
前面一半排序完成,总的数组为:
排序前：2,1,3,6,4,5
排序后：1,2,3,6,4,5
3)，对后面一半[6,4,5]继续进行快速排序
重复步骤1)后变成下边这样:
排序前：6,4,5
排序后：4,5,6
后面一半排序完成,总的数组为:
排序前：1,2,3,6,4,5
排序后：1,2,3,4,5,6
至此，排序结束
动画演示
代码参考
static void Main(string[] args) { int[] intArray = { 3, 6, 4, 2, 5, 1 }; Quick_Sort(intArray, 0, intArray.Length - 1); foreach (var item in intArray) { Console.WriteLine(item); } Console.ReadLine(); } // 快速排序 static void Quick_Sort(int[] unsorted, int low, int high) { int loc; if (low < high) { loc = partition(unsorted, low, high); Quick_Sort(unsorted, low, loc - 1); Quick_Sort(unsorted, loc + 1, high); } } /// <summary> /// 分区操作 /// </summary> /// <param name="unsorted">带排序数组</param> /// <param name="low">起始位置</param> /// <param name="high">结束位置</param> /// <returns>排序后基准所在位置</returns> static int partition(int[] unsorted, int low, int high) { int pivot = unsorted[low]; // 基准 while (low < high) { while (low < high & unsorted[high] > pivot) high--; unsorted[low] = unsorted[high]; while (low < high & unsorted[low] <= pivot) low++; unsorted[high] = unsorted[low]; } unsorted[low] = pivot; return low; }
参考资料