什么是快速排序
关键词： 交替填充 或 换位
时间复杂度： O(log2n)
快速排序算法
思路
对于一个排好序的数组，我们假设为从小到大排序。
那么对于这个数组而言，其中的每一个元素，左边都是比它小的元素；
右边都是比它大的元素（若大小相等，在左边或右边都可以）。
所以我们进行排序，可以反过来想，即将每一个元素都放到它应该在的位置。
当放完所有的元素后，排序完成。
做法
那么我们要做的就是一个一个的找到元素所在的位置，并放好他们。
所以我们假设第一个元素为待放置元素。
通过以下的方式将其放置好，之后再递归的将其左边和右边再次进行排序即可。
图解Partition函数（例子）
写法1
将 partition 与 sort 函数写在一个函数里。
函数参数 : nums（需要排序的数组），startIndex（起始元素的下标），endIndex（最后一个元素的下标 + 1）
返回值： void
单层逻辑：先移动 R 指针，若遇到小于基准的值，则进行放置，接着换移动 L 指针。
结束条件： startIndex 与 endIndex 相交或 startIndex > endIndex
void quicksort1(vector<int> &nums, int startIndex, int endIndex)
{
if (!(startIndex < endIndex))
return;
int left = startIndex, right = endIndex - 1;
int temp = nums[left];
while (right > left)
{
while (right > left)
{
if (nums[right] < temp)
{
nums[left] = nums[right];
left++;
break;
}
right--; // nums[right] > temp
}
while (right > left)
{
if (nums[left] > temp)
{
nums[right] = nums[left];
right--;
break;
}
left++;
}
}
nums[left] = temp;
quicksort1(nums, startIndex, left);
quicksort1(nums, left + 1, endIndex);
}
写法2
将 partition 与 sort 函数写在一个函数里。利用交换。
函数参数 : nums（需要排序的数组），startIndex（起始元素的下标），endIndex（最后一个元素的下标 + 1）
返回值： void
单层逻辑：先移动 R 指针若找到小于 temp 的值，停止；移动 L 指针找到大于 temp 的值，停止；
交换 L 与 R的值，继续循环直到 L 与 R相交，交换 基准位置与 R 位置
结束条件： startIndex 与 endIndex 相交或 startIndex > endIndex
void quicksort2(vector<int> &nums, int startIndex, int endIndex)
{
if (!(startIndex < endIndex))
return;
int left = startIndex, right = endIndex - 1;
int &temp = nums[startIndex];
while (left < right)
{
while (left < right)
{
if (nums[right] < temp)
{
break;
}
right--;
}
while (left < right)
{
if (nums[left] > temp)
{
break;
}
left++;
}
swap(nums[left], nums[right]);
}
swap(temp, nums[left]);
quicksort2(nums, startIndex, left);
quicksort2(nums, left + 1, endIndex);
}
写法3
将 sort 与 partition分开写
sort 函数：
函数参数：nums（待排序数组）， startIndex（排序开始位置）， endIndex（排序结束位置的后一个位置）。
返回值：void
单层逻辑：先利用partition函数排好第一个元素，取得元素位置，排序元素位置的左边与右边。
结束条件：startIndex 超过 endIndex 或 与其相交。
partition函数：
函数参数：nums（待排序数组）， startIndex（排序开始位置）， endIndex（排序结束位置的后一个位置）。
返回值：int 排好位置后的合适位置
单层逻辑：定好 L 与 R 的含义，分别指向最左与最右，设置基准兵，开始比较以及调整数组位置。
结束条件：L == R
void quicksort(vector<int> &nums, int startIndex, int endIndex)
{
if (!(startIndex < endIndex))
return;
int pivot = partition(nums, startIndex, endIndex - 1);
quicksort(nums, startIndex, pivot);
quicksort(nums, pivot + 1, endIndex);
}
int partition(vector<int> &nums, int startIndex, int endIndex)
{
int pivot = startIndex;
int temp = nums[startIndex];
int left = startIndex, right = endIndex;
while (left < right)
{
while (left < right)
{
if (nums[right] < temp)
{
nums[left] = nums[right];
left++;
break;
}
right--;
}
while (left < right)
{
if (nums[left] > temp)
{
nums[right] = nums[left];
right--;
break;
}
left++;
}
}
nums[left] = temp;
return left;
}
快速选择算法
快速选择算法，基于快速排序算法演化而来的算法。
上文写道：我们可以得到任意一个值应该安排到的位置，假如我们要找第 3 大的元素，那么按照从小到大排序，它在下标为size() - 3的位置，我们从而可以采取上文的 partition 函数。
具体怎么使用呢？
我们知道使用一次partition函数，会返回一个当前元素的正确排序下标。
假设这个下标为size() - 3，是不是就表示我们找到了这个第三大的元素了？
假设这个下标为size() - 4，那么答案则在它的右边，而它的左边我们则不需要去考虑了。
这就比排序所有的元素要快。
下面我们来举一个例子。
图解快速选择算法（例子）
写法1
关键词： 基于快速排序的选择算法
时间复杂度： O(n)
int nLargeNum(vector<int> &nums, int startIndex, int endIndex, int n)
{
int pivot = partition(nums, startIndex, endIndex - 1); // 同上文
if (pivot == n - 1)
return nums[pivot];
else if (n > pivot + 1)
{
return nLargeNum(nums, pivot + 1, endIndex, n);
}
else
{
return nLargeNum(nums, startIndex, pivot, n);
}
}