## 快速排序 1. 基本思想：通过一趟排序将待排记录分成独立的两部分，其中一部分的值均比另一部分的值小，则可以分别对这两部分继续进行排序，直到整个序列有序。 2. 算法描述： 1）从数列中挑出一个元素，称为基准（pivot） 2）重新排序数列，所有元素比基准小的放在基准前面，比基准大的放在基准后面（与基准相等的可放到任意一边）。操作完成后，该基准就处于数列的中间位置。这个称为分区（partition）操作 3）递归地把小于基准元素的子序列和大于基本的子序列排序 * 最简单的快速排序 ``` template <typename T> int partition(vector<T>& data, int l, int r) { std::swap(data[r], data[rand() % (r-l+1) + l]); // 基准点随机 T pivot = data[r]; int i = l; for (int j = l; j < r; ++j) { if (data[j] < pivot) { swap(data[i++], data[j]); } } swap(data[i], data[r]); return i; } template <typename T> void _quicksort(vector<T>& data, int l, int r) { if (l >= r) return; int p = partition(data, l, r); _quicksort(data, l, p-1); _quicksort(data, p+1, r); } template <typename T> void quicksort(vector<T>& data) { srand(time(nullptr)); _quicksort(data, 0, data.size()); } ``` * 二路快速排序 ``` template <typename T> int partiton2(vector<T>& data, int l, int r) { swap(data[r], data[rand()%(r-l+1) + l]); T pivot = data[r]; int i = l, j = r-1; while (true) { while (i < r && data[i] < pivot) i++; // 不能 <= while (j >= l && data[j] > pivot) j--; // 不能 >= if (i > j) break; swap(data[i++], data[j--]); // 等于pivot的数据需要平均分配到两边 } swap(data[r], data[i]); return i; } template <typename T> void _quicksort2(vector<T>& data, int l, int r) { if (l >= r) return; int p = partiton2(data, l, r); _quicksort2(data, l, p-1); _quicksort2(data, p+1, r); } template <typename T> void quicksort2(vector<T>& data) { _quicksort2(data, 0, data.size()-1); } ``` * 三路快速排序 ``` template <typename T> void _quicksort3(vector<T>& data, int l, int r) { if (l >= r) return; int lt = l, gt = r, i = l; /* * [l, lt) < pivot * [it, i) == pivot * [gt, r-1] > pivot */ swap(data[r], data[rand()%(r-l+1) + l]); T pivot = data[r]; while (i < gt) { if (data[i] < pivot) swap(data[i++], data[lt++]); else if (data[i] > pivot) swap(data[i], data[--gt]); else i++; } swap(data[r], data[gt]); _quicksort3(data, l, lt-1); _quicksort3(data, gt+1, r); } template <typename T> void quicksort3(vector<T>& data) { srand(time(nullptr)); _quicksort3(data, 0, data.size()-1); } ```