1v1视频软件源码，如何优化快速排序算法低效问题？
快速排序
快速排序也遵循分治的思想，它与归并排序不同的是，快速排序是原地排序，而且快速排序会先排序当前数组，再对子数组进行排序，它的算法步骤如下：
1、哨兵划分：选取数组中最左端元素为基准数，将小于基准数的元素放在基准数左边，将大于基准数的元素放在基准数右边
2、排序子数组：将哨兵划分的索引作为划分左右子数组的分界，分别对左右子数组进行哨兵划分和排序
快速排序的代码实现如下：
private void sort(int[] nums, int left, int right) {
if (left >= right) {
return;
}
// 哨兵划分
int partition = partition(nums, left, right);
// 分别排序两个子数组
sort(nums, left, partition - 1);
sort(nums, partition + 1, right);
}
/**
* 哨兵划分
*/
private int partition(int[] nums, int left, int right) {
// 以 nums[left] 作为基准数，并记录基准数索引
int originIndex = left;
int base = nums[left];
while (left < right) {
// 从右向左找小于基准数的元素
while (left < right && nums[right] >= base) {
right--;
}
// 从左向右找大于基准数的元素
while (left < right && nums[left] <= base) {
left++;
}
swap(nums, left, right);
}
// 将基准数交换到两子数组的分界线
swap(nums, originIndex, left);
return left;
}
private void swap(int[] nums, int left, int right) {
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
}
算法特性：
1、时间复杂度：平均时间复杂度为 O(nlogn)，最差时间复杂度为 O(n2)
2、空间复杂度：最差情况下，递归深度为 n，所以空间复杂度为 O(n)
3、原地排序
4、非稳定排序
5、自适应排序
归并排序的时间复杂度一直是 O(nlogn)，而快速排序在最坏的情况下时间复杂度为 O(n2)，为什么归并排序没有快速排序应用广泛呢？
答：因为归并排序是非原地排序，在合并阶段需要借助非常量级的额外空间
快速排序有很多优点，但是在哨兵划分不平衡的情况下，算法的效率会比较低效。下面是对快速排序排序优化的一些方法：
切换到插入排序
对于小数组，快速排序比插入排序慢，快速排序的 sort() 方法在长度为 1 的子数组中也会调用一次，所以，在排序小数组时切换到插入排序排序的效率会更高，如下：
/**
* M 取值在 5 ~ 15 之间大多数情况下都能令人满意
*/
private final int M = 9;
public void sort(int[] nums, int left, int right) {
// 小数组采用插入排序
if (left + M >= right) {
insertSort(nums);
return;
}
int partition = partition(nums, left, right);
sort(nums, left, partition - 1);
sort(nums, partition + 1, right);
}
/**
* 插入排序
*/
private void insertSort(int[] nums) {
for (int i = 1; i < nums.length; i++) {
int base = nums[i];
int j = i - 1;
while (j >= 0 && nums[j] > base) {
nums[j + 1] = nums[j--];
}
nums[j + 1] = base;
}
}
private int partition(int[] nums, int left, int right) {
int originIndex = left;
int base = nums[left];
while (left < right) {
while (left < right && nums[right] >= base) {
right--;
}
while (left < right && nums[left] <= base) {
left++;
}
swap(nums, left, right);
}
swap(nums, left, originIndex);
return left;
}
private void swap(int[] nums, int left, int right) {
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
}
基准数优化
如果数组为倒序的情况下，选择最左端元素为基准数，那么每次哨兵划分会导致右数组长度为 0，进而使快速排序的时间复杂度为 O(n2)，为了尽可能避免这种情况，我们可以对基准数的选择进行优化，采用三取样切分的方法：选取数组最左端、中间和最右端这三个值的中位数为基准数，这样选择的基准数大概率不是区间的极值，时间复杂度为 O(n2) 的概率大大降低，代码实现如下：
public void sort(int[] nums, int left, int right) {
if (left >= right) {
return;
}
// 基准数优化
betterBase(nums, left, right);
int partition = partition(nums, left, right);
sort(nums, left, partition - 1);
sort(nums, partition + 1, right);
}
/**
* 基准数优化，将 left, mid, right 这几个值中的中位数换到 left 的位置
* 注意其中使用了异或运算进行条件判断
*/
private void betterBase(int[] nums, int left, int right) {
int mid = left + right >> 1;
if ((nums[mid] < nums[right]) ^ (nums[mid] < nums[left])) {
swap(nums, left, mid);
} else if ((nums[right] < nums[left]) ^ (nums[right] < nums[mid])) {
swap(nums, left, right);
}
}
private int partition(int[] nums, int left, int right) {
int originIndex = left;
int base = nums[left];
while (left < right) {
while (left < right && nums[right] >= base) {
right--;
}
while (left < right && nums[left] <= base) {
left++;
}
swap(nums, left, right);
}
swap(nums, originIndex, left);
return left;
}
private void swap(int[] nums, int left, int right) {
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
}
三向切分
在数组有大量重复元素的情况下，快速排序的递归性会使元素全部重复的子数组经常出现，而对这些数组进行快速排序是没有必要的，我们可以对它进行优化。
一个简单的想法是将数组切分为三部分，分别对应小于、等于和大于基准数的数组，每次将其中“小于”和“大于”的数组进行排序，那么最终也能得到排序的结果，这种策略下我们不会对等于基准数的子数组进行排序，提高了排序算法的效率，它的算法流程如下：
从左到右遍历数组，维护指针 l 使得 [left, l - 1] 中的元素都小于基准数，维护指针 r 使得 [r + 1, right] 中的元素都大于基准数，维护指针 mid 使得 [l, mid - 1] 中的元素都等于基准数，其中 [mid, r] 区间中的元素还未确定大小关系，图示如下
它的代码实现如下：
public void sort(int[] nums, int left, int right) {
if (left >= right) {
return;
}
// 三向切分
int l = left, mid = left + 1, r = right;
int base = nums[l];
while (mid <= r) {
if (nums[mid] < base) {
swap(nums, l++, mid++);
} else if (nums[mid] > base) {
swap(nums, mid, r--);
} else {
mid++;
}
}
sort(nums, left, l - 1);
sort(nums, r + 1, right);
}
private void swap(int[] nums, int left, int right) {
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
}
以上就是1v1视频软件源码，如何优化快速排序算法低效问题？， 更多内容欢迎关注之后的文章
标签：低效,right,nums,int,源码,数组,排序,1v1,left From： https://www.cnblogs.com/yunbaomengnan/p/18620378