算法概述
一、分而治之
什么十快速排序算法的最好情况？
每次正好中分：T(N) = O(NlogN)
void Quicksort(ElementType A[], int N) { pivot = 从A[]中选一个主元; 将S = { A[] \ pivot } 分成2个独立子集： A1 = { a属于S | a≤ pivot } 和 A2 = { a属于S | a≥ pivot }; A[] = Quicksort(A1, N1) U { pivot} U Quicksort(A2, N2); }
实现算法
void Quicksort(ElementType A[], int Left, int Right) { if(Cutoff <= Right-Left) { Pivot = Median3(A, Left, Right); i = Left; j = Right - 1; for( ; ; ) { while(A[++i] < Pivot) { } while(A[--j] > Pivot) { } if(i < j) Swap(&A[i], &A[j]); else break; } Swap(&A[i], &A[Right-1]); Quicksort(A, Left, i-1); Quicksort(A, i+1, Right); } else Insertion_Sort(A+Left, Right-Left+1); } void Quick_Sort(ElementType A[], int N) { Quicksort(A, 0, N-1); }
原文：https://www.cnblogs.com/ch122633/p/9025283.html
