这个bug未免太机车了啦

用户名：dotcpp0651617

访问量：461

签　名：

等　　级
排　　名	19371
经　　验	720
参赛次数	0
文章发表	14
年　　龄	0
在职情况	学生
学　　校
专　　业

　　自我简介：

TA的其他文章

快速排序C++
浏览：41

归并排序C++
浏览：52

插入排序C++
浏览：35

你可能喜欢

C语言程序设计教程（第三版）课后习题5.8 （Java代码）

【求[X,Y]内被除3余1并且被除5余3的整数的和】（C语言代码）

快速排序C++

　　作者: 这个bug未免太机车了啦　　　　发表时间：2023-07-05 13:40:47 浏览：41　|　评论：0　

```cpp
#include<iostream>
#include<vector>
using namespace std;

int part(int* r, int low, int hight)  //划分函数
{
	int i = low, j = hight, pivot = r[low]; //基准元素
	while (i < j)
	{
		while (i<j && r[j]>pivot)
			j--;
		if (i < j)
			swap(r[i++], r[j]); 
		while (i < j && r[i] <= pivot)
			i++;
		if (i < j)
			swap(r[i], r[j--]);
	}
	return i;  //返回最终划分完成后基准元素所在的位置
}
void Quicksort(int* r, int low, int hight)
{
	int mid;
	if (low < hight)
	{
		mid = part(r, low, hight);  // 返回基准元素位置
		Quicksort(r, low, mid - 1); // 左区间递归快速排序
		Quicksort(r, mid+1, hight); // 右区间递归快速排序
	}
}
int main()
{
	int a[10001];
	int  N;
	cout << "请输入要排序的数据的个数： " << endl;
	cin >> N;
	cout << "请输入要排序的数据： " << endl;
	for (int i = 0; i < N; i++)
	{
		cin >> a[i];
	}
	cout << endl;
	Quicksort(a, 0, N - 1);
	cout << "排序后的序列为： " << endl;
	for (int i = 0; i < N; i++)
	{
		cout << a[i] << " ";
	}
	cout << endl;
	return 0;
}
```
```
更新：如果不需要所有元素全部排序，只需要第几个最大或最小的元素时，由于每次返回的mid值都是最终元素确定的位置，将mid与需要下标数比较，就可以只遍历左、右区间中的一个，加快了时间，并且引入随机化，减小时间复杂度。

```cpp
public:
    int randomPartition(vector<int>& a, int l, int r) {
        int i = rand() % (r - l + 1) + l;
        return i;
    }

int partion(vector<int>& nums, int start, int end){
        int left = start, right = end;
        int flag = nums[left];
        while(left<right){
            while(left<right && nums[right]>flag)
                right--;
            if(left<right){
                swap(nums[left], nums[right]);
                left++;
            }
            while(left<right && nums[left]<=flag)
                left++;
            if(left<right){
                swap(nums[left], nums[right]);
                right--;
            }
        }
        return left;
    }
    void quicksort(vector<int>& nums, int start, int end, int k){
        randomPartition(nums, start, end);
        int mid;
        if(start<end){
            mid = partion(nums, start, end);
            if(mid==nums.size()-k)
                return;
            else if(mid<nums.size()-k)
                quicksort(nums, mid+1, end, k);
            else
                quicksort(nums, start, mid-1, k);
        }
    }
    int findKthLargest(vector<int>& nums, int k) {
        quicksort(nums, 0, nums.size()-1, k);
        return nums[nums.size()-k];
    }

```

0.0分

0 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

这个bug未免太机车了啦

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题5.8 （Java代码）

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

【求[X,Y]内被除3余1并且被除5余3的整数的和】（C语言代码）

C二级辅导-进制转换（C语言代码）

C语言程序设计教程（第三版）课后习题6.9 （C语言代码）

快速排序C++

评论区

精彩推荐

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值（C语言代码）

WU-格式化数据输出（C++代码）

DNA （C语言描述，数据结构）

用筛法求之N内的素数。（C语言代码）

C语言程序设计教程（第三版）课后习题6.9 （C语言代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

C语言训练-亲密数（C语言描述,反正怎么都能对）

永远的丰碑（C语言代码）

C语言程序设计教程（第三版）课后习题6.10 （C语言代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

这个bug未免太机车了啦

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题5.8 （Java代码）

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

【求[X,Y]内被除3余1并且被除5余3的整数的和】 （C语言代码）

C二级辅导-进制转换 （C语言代码）

C语言程序设计教程（第三版）课后习题6.9 （C语言代码）

快速排序C++

评论区

精彩推荐

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值 （C语言代码）

WU-格式化数据输出 （C++代码）

DNA （C语言描述，数据结构）

用筛法求之N内的素数。 （C语言代码）

C语言程序设计教程（第三版）课后习题6.9 （C语言代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

C语言训练-亲密数 （C语言描述,反正怎么都能对）

永远的丰碑 （C语言代码）

C语言程序设计教程（第三版）课后习题6.10 （C语言代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

【求[X,Y]内被除3余1并且被除5余3的整数的和】（C语言代码）

C二级辅导-进制转换（C语言代码）

　　评论区

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值（C语言代码）

WU-格式化数据输出（C++代码）

用筛法求之N内的素数。（C语言代码）

C语言训练-亲密数（C语言描述,反正怎么都能对）

永远的丰碑（C语言代码）