三路快速排序是快速排序针对相等元素较多情况的改进版本。
三路快排的C实现:
void quicksort3(int *n, int len) { int i=0, j=0, k=len-1; if (len<2) return; while (i<k) { if (*(n+i) < *(n+len-1)) { swap(n+ i++, n+ j++); } else if (*(n+i) == *(n+len-1)) { swap(n+i, n+ --k); } else { i++; } } // k-j is length of nums larger than tail num, len-k is length of nums // equal to tail num int m = (k-j) < (len-k) ? (k-j) : (len-k); int _i; for (_i=0; _i<m; _i++) { swap(n+j+_i, n+len-m+_i); } // j is len of nums less than tail num if (j>1) quicksort3(n, j); if (k-j>1) quicksort3(n+len-k+j, k-j); }
三路快排比传统快排稍微复杂,但它继承了快排的所有优点,而且针对相等元素较多的情况速度提升非常明显。