快速排序算法 百科名片
快速排序
快速排序（Quicksort）是对冒泡排序的一种改进。由C. A. R. Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。 目录 算法介绍 示例 算法 排序 性能分析 展开 算法介绍 示例 算法 排序 性能分析 展开
编辑本段算法介绍
快排图
设要排序的数组是A*0+……A*N-1]，首先任意选取一个数据（通常选用第1个数据）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一趟快速排序。值得注意的是，快速排序不是一种稳定的排序算法，也就是说，多个相同的值的相对位置也许会在算法结束时产生变动。 一趟快速排序的算法是：
1）设置两个变量i、j，排序开始的时候：i=0，j=N-1；
2）以第一个数组元素作为关键数据，赋值给key，即key=A[0]；
3）从j开始向前搜索，即由后开始向前搜索（j -- ），找到第一个小于key的值A[j]，A[i]与A[j]交换；
4）从i开始向后搜索，即由前开始向后搜索（i ++ ），找到第一个大于key的A[i]，A[i]与A[j]交换；
5）重复第3、4、5步，直到 I=J； (3,4步是在程序中没找到时候j=j-1，i=i+1，直至找到为止。找到并交换的时候i， j指针位置不变。另外当i=j这过程一定正好是i+或j-完成的最后令循环结束。 编辑本段示例
待排序的数组A的值分别是：（初始关键数据：key=49）注意关键key永远不变，永远是和key进行比较，无论在什么位置，最后的目的就是把key放在中间，小的放前面大的放后面。 A[0] 49 A[1] 38 A[2] 65 A[3] 97 A[4] 76 A[5] 13 A[6] 27 进行第一次交换后：27 38 65 97 76 13 49
( 按照算法的第三步从后面开始找，此时:J=6） 进行第二次交换后：27 38 49 97 76 13 65
( 按照算法的第四步从前面开始找>key的值，65>49,两者交换，此时：I=2 ) 进行第三次交换后：27 38 13 97 76 49 65
( 按照算法的第五步将又一次执行算法的第三步从后开始找 进行第四次交换后：27 38 13 49 76 97 65
( 按照算法的第四步从前面开始找大于key的值，97>49，两者交换，此时：I=3,J=5 )
此时再执行第三和四步的时候就发现i=J=4，从而结束一趟快速排序，那么经过一趟快速排序之后的结果是：27 38 13 49 76 97 65，即所有大于key49的数全部在49的后面，所有小于key（49）的数全部在key（49）的前面。 编辑本段算法
C++递归实现快速排序优化版 1 void quickSort(int *a,size_t left,size_t right) 2 { 3 size_t p = (left + right)/2; 4 int key = a[p]; 5 for(size_t i = left,j = right; i < j;) 6 { 7 while(!(key < a[i] || p < i)) 8 i++; 9 if(i < p) 10 { 11 a[p] = a[i]; 12 p = i; 13 } 14 while(!(j < p || a[j] < key)) 15 j--; 16 if(p < j) 17 { 18 a[p] = a[j]; 19 p = j;
20 21 22 23 24 25 26 27 } }
a[p] = key; if(p - left > 1)
quickSort(a,left,p-1); if(right - p > 1)
quickSort(a,p + 1, right); }
C#实现快速排序 1 public class QuickSort{ 2 public static void main(String[] ary){ 3 int[] arry = {49, 38, 65, 97, 76, 13, 27}; 4 sort(arry, 0, arry.length - 1); 5 } 6 /** 7 * 一次排序单元，完成此方法，key左边都比key小，key右边都比key大。 8 * @param array 排序数组 9 * @param low 排序起始位置 10 * @param high 排序结束位置 11 * @return 单元排序后的数组 12 */ 13 private static int sortUnit(int[] array, int low, int high){ 14 int key = array[low]; 15 while (low < high){ 16 //从后向前搜索比key小的值 17 while (array[high] >= key && high > low) 18 --high; 19 //比key小的放左边 20 array[low] = array[high]; 21 //从前向后搜索比key大的值，比key大的放右边 22 while (array[low] <= key && high > low) 23 ++low; 24 //比key大的放右边 25 array[high] = array[low]; 26 System.out.println(low + \27 } 28 //左边都比key小，右边都比key大。将key放在游标当前位置。此时low等于high 29 array[high] = key; 30 System.out.println(Arrays.toString(array)); 31 return high; 32 } 33 /** 34 * 快速排序 35 * @param arry
36 37 38 39 40 41 42 43 44 45 46 47
* @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快速排序就是递归调用此过程——在以49为中点分割这个数据序列，分别对前面一部分和后面一部分进行类似的快速排序，从而完成全部数据序列的快速排序，最后把此数据序列变成一个有序的序列，根据这种思想对于上述数组A的快速排序的全过程如图6所示：初始状态 {49 38 65 97 76 13 27} 进行一次快速排序之后划分为 {27 38 13} 49 {76 97 65} 分别对前后两部分进行快速排序{27 38 13} 经第三步和第四步交换后变成 {13 27 38} 完成排序。{76 97 65} 经第三步和第四步交换后变成 {65 76 97} 完成排序。图示
C++实现快速排序 1 void quicksort(int a[], int left, int right) { 2 if (left >= right) 3 return; 4 5 int li = left, ri = right; 6 int key = a[(left + right) / 2]; 7 while (li <= ri) { 8 for (; a[ri] > key; --ri); 9 10 for (; a[li] < key; ++li); 11 //swap 12 if (li <= ri) { 13 int temp = a[li]; 14 a[li] = a[ri]; 15 a[ri] = temp; 16 ++li, --ri; 17 } 18 } 19 if (li < right) { 20 quicksort(a, li, right); 21 } 22 if (ri > left) { 23 quicksort(a, left, ri); 24 }
25 }
pascal 实现快速排序
(假设被排序的数组是a,且快排后按升序排列）： 1 procedure qsort(l,h:integer); 2 var 3 i,j,t,m:integer; 4 begin 5 i:=l; j:=h; 6 m:=a[(i+j) div 2]; //注意：本句不能写成：m:=(i+j) div 2; 7 repeat 8 while a[i]