数据结构与算法——快速排序

快速排序

一、核心原理：分治策略

1、选一个基准元素，

2、两个指针往中间遍历，比基准值小的移到一边，比基准值大的移到另一边，

一轮遍历后，指针相交位置就是基准值应该放置的位置，同时数组也以基准值分成左右两部分；

3、对两边各自进行递归快排，直到整个数组有序；

二、算法稳定性：不稳定

随机选取基准值，相同的元素可能会分为不同的子数组中；

如：（5，3，2，5，1），基准值为左边第一个5，大于等于基准值的放左边，小于的放右边；

一轮排序后第二个5就在第一个5左边，两个5之间的顺序发生了变化，即不稳定；

三、时间复杂度：平均O(nlogn)，最坏O(n^2)

平均O(nlogn)：每次对半的划分数组递归排序；最大递归树深度为log(n+1)；

最坏O(n^2)：基准元素偏向边缘元素，基准元素两边数组大小相差很大，最大递归树深度为n；

四、空间复杂度：平均O(logn)，最坏O(n)；

由于递归过程需要使用栈空间来保存每一层递归调用的信息，空间复杂度主要考虑递归树的深度；

五、C#代码示例：

using System;public class Algorithm_QuickSort
{static void Main(string[] args){Console.WriteLine("快速排序");int[] array = { 5, 4, 9, 8, 7, 6, 0, 1, 3, 2 };QuickSort(array, 0, array.Length-1);for (int i = 0; i < array.Length; i++)Console.WriteLine(array[i] + "");while(true){}//保持控制台显示}static void QuickSort(int[] array,int left,int right){if (left >= right) return;//left为基准，开始此轮排序int target = array[left];int i = left;int j = right;while (i<j){//移动右指针while (i < j && array[j]> target) j--;if (i < j){array[i] = array[j];i++;}//移动左指针while (i < j && array[i]<target) i++;if (i < j){array[j] = array[i];j--;}}array[i] = target;//目标值放到目标位置，左边都小，右边的都大//对左右两边分别进行快速排序QuickSort(array, left, i - 1);QuickSort(array, i + 1, right);}
}