它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分：分割点左边都是比它小的数，右边都是比它大的数。
然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
基本思想：
1）选择一个基准元素,通常选择第一个元素或者最后一个元素,
2）通过一趟排序讲待排序的记录分割成独立的两部分，其中一部分记录的元素值均比基准元素值小。另一部分记录的 元素值比基准值大。
3）此时基准元素在其排好序后的正确位置
4）然后分别对这两部分记录用同样的方法继续进行排序，直到整个序列有序。
快速排序的示例：
（a）一趟排序的过程：
（b）排序的全过程
核心代码
public int division(int[] list, int left, int right) { // 以最左边的数(left)为基准 int base = list[left]; while (left < right) { // 从序列右端开始，向左遍历，直到找到小于base的数 while (left < right && list[right] >= base) right--; // 找到了比base小的元素，将这个元素放到最左边的位置 list[left] = list[right]; // 从序列左端开始，向右遍历，直到找到大于base的数 while (left < right && list[left] <= base) left++; // 找到了比base大的元素，将这个元素放到最右边的位置 list[right] = list[left]; } // 最后将base放到left位置。此时，left位置的左侧数值应该都比left小； // 而left位置的右侧数值应该都比left大。 list[left] = base; return left;}快速排序采用的思想是分治思想。
快速排序是找出一个元素（理论上可以随便找一个）作为基准(pivot),然后对数组进行分区操作,使基准左边元素的值都不大于基准值,基准右边的元素值 都不小于基准值，如此作为基准的元素调整到排序后的正确位置。递归快速排序，将其他n-1个元素也调整到排序后的正确位置。最后每个元素都是在排序后的正 确位置，排序完成。所以快速排序算法的核心算法是分区操作，即如何调整基准的位置以及调整返回基准的最终位置以便分治递归。
递归完成int quicksort(vector<int> &v, int left, int right){ if(left < right){ int key = v[left]; int low = left; int high = right; while(low < high){ while(low < high && v[high] > key){ high--; } v[low] = v[high]; while(low < high && v[low] < key){ low++; } v[high] = v[low]; } v[low] = key; quicksort(v,left,low-1); quicksort(v,low+1,right); }} private void quickSort(int[] list, int left, int right) { // 左下标一定小于右下标，否则就越界了 if (left < right) { //对数组进行分割，取出下次分割的基准标号 int base = division(list, left, right); //对“基准标号“左侧的一组数值进行递归的切割，以至于将这些数值完整的排序 quickSort(list, left, base - 1); //对“基准标号“右侧的一组数值进行递归的切割，以至于将这些数值完整的排序 quickSort(list, base + 1, right); }} C#代码 using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace test { class QuickSort { static void Main( string [] args) { int [] array = { 49, 38, 65, 97, 76, 13, 27 }; sort(array, 0, array.Length - 1); Console.ReadLine(); } /**一次排序单元，完成此方法，key左边都比key小，key右边都比key大。 **@param array排序数组 **@param low排序起始位置 **@param high排序结束位置 **@return单元排序后的数组 */ private static int sortUnit( int [] array, int low, int high) { int key = array[low]; while (low < high) { /*从后向前搜索比key小的值*/ while (array[high] >= key && high > low) --high; /*比key小的放左边*/ array[low] = array[high]; /*从前向后搜索比key大的值，比key大的放右边*/ while (array[low] <= key && high > low) ++low; /*比key大的放右边*/ array[high] = array[low]; } /*左边都比key小，右边都比key大。//将key放在游标当前位置。//此时low等于high */ array[low] = key; foreach ( int i in array) { Console.Write( "{0}\t" , i); } Console.WriteLine(); return high; } /**快速排序 *@paramarry *@return */ public static void sort( int [] array, int low, int high) { if (low >= high) return ; /*完成一次单元排序*/ int index = sortUnit(array, low, high); /*对左边单元进行排序*/ sort(array, low, index - 1); /*对右边单元进行排序*/ sort(array, index + 1, high); } } } 运行结果：27 38 13 49 76 97 65 13 27 38 49 76 97 65 13 27 38 49 65 76 97 算法分析时间复杂度 当数据有序时，以第一个关键字为基准分为两个子序列，前一个子序列为空，此时执行效率最差。
而当数据随机分布时，以第一个关键字为基准分为两个子序列，两个子序列的元素个数接近相等，此时执行效率最好。
所以，数据越随机分布时，快速排序性能越好；数据越接近有序，快速排序性能越差。
空间复杂度快速排序在每次分割的过程中，需要 1 个空间存储基准值。而快速排序的大概需要 Nlog2N次 的分割处理，所以占用空间也是 Nlog2N 个。
算法稳定性在快速排序中，相等元素可能会因为分区而交换顺序，所以它是不稳定的算法
转载于:https://www.cnblogs.com/nxxshxf/p/5150501.html
