一、快速排序的原理
对于一个数组,我们可以随机选定其中一个值,记为 m。
比m大的数,挪动到m的右边。比m小的数,挪动到m的左边。
然后,我们分别对左右两边再次进行快速排序。
当排序区间小到1的时候,快排就结束了。
二、代码
快排的代码细节在于如何调整下标。
void quicksort(vector<int>& a, int left, int right) {if (left >= right) return; int mid = left + (right - left) / 2; int midNum = a[mid]; int leftp = left + 1; int rightp = right; // 把我们选定的值放在a[left],相当于把空位挖在目标数组的首个位置。 swap(a[mid], a[left]); // leftp - 1 指向了下一个小于 mid 的数被放置的位置, // rightp 指向了下一个大于 mid 的数被放置的位置, // 当leftp - 1 = rightp,说明数组已经分类完毕。 while(leftp <= rightp) { if (a[leftp] < midNum) { a[leftp - 1] = a[leftp]; leftp++; } else { swap(a[leftp], a[rightp]); rightp--; } } mid = rightp; a[mid] = midNum; // 对两边进行快排。 quicksort(a, left, mid - 1); quicksort(a, mid + 1, right); }