快速排序的三种实现方式

快来打我* 2022-09-10 03:23 127阅读 0赞

// 把小的插入头部位置，可用于链表结构的快排一次划分
    // ps:如果是链表结果，需要将这里的 ++j 换成 j = j->next 。
    int Partition(vector<int>& nums, int l, int r) {
        
    	int pivot = nums[r];
    	int i = l - 1;
    	for (int j = l; j <= r - 1; ++j) {
        
    		if (nums[j] <= pivot) {
        	// 找到比基准小的
    			i = i + 1;			// 这里加一的意思是。当前i位置表示最小值的边界下标。
    								// 我们需要在下一位置插入新的小值。
    			swap(nums[i], nums[j]);	// 将其插入到头部
    		}
    	}
    	swap(nums[i + 1], nums[r]);// 将基准插入
    	return i + 1;
    }
    
    
    // 双指针单方向推进
    int Partition1(vector<int>& ar, int left, int right)
    {
        	// left~j  范围内元素保证为小于基准的值。
    	// j~right 范围内元素为大于基准的值
    	int i = left, j = left + 1;
    	int pivot = ar[i];
    	while (i <= right && j <= right)
    	{
        	// 注意这里的几个while条件都是带等号的
    		while (j <= right && ar[j] <= pivot) j++;	// j遍历小值，跳出后所在位置为大值
    		if (j > right) break;
    		
    		if (i < j) i = j + 1;	// 找j后面的小值
    
    		while (i <= right && ar[i] > pivot) i++;	// 找j后小值
    		if (i > right) break;
    		std::swap(ar[i], ar[j]);
    		//j++;
    	}
    	std::swap(ar[j - 1], ar[left]);
    	return j-1;
    }
    
    // 双指针，双向推进
    int Partition2(vector<int>& ar, int left, int right)
    {
        	// j从右向左，保证 j~right 为大值
    	// i从左向右，保证 left~i  为小值
    	int i = left, j = right;
    	int pivot = ar[i];
    	while (i < j)
    	{
        
    		while (i < j && ar[j] > pivot) j--;		// z
    		if (i >= j) break;
    		while (i < j && ar[i] <= pivot) i++;	// 这里 <= 是因为，i的初值是left。而基准取的也是left
    		if (i >= j) break;
    		std::swap(ar[i], ar[j]);
    	}
    	std::swap(ar[i], ar[left]);
    	return i;
    }
    
    
    // 定义函数对象。可理解为函数指针 int (*OnePartition)(vector<int>&, int, int)
    //typedef int (*OnePartition)(vector<int>&, int, int);
    using OnePartition = function<int(vector<int>&, int, int)>;
    
    // 简单的优化方案，随机选取基准
    void randomized_partition(vector<int>& nums, int l, int r) {
        
    	std::random_device rd;
    	int i = rd() % (r - l + 1) + l;	// 随机选取下标作为基准，把它放在首位
    	swap(nums[l], nums[i]);
    }
    // 快排
    void QuickSort(OnePartition Partition, vector<int>& ar, int left, int right)
    {
        
    	if (left < right)
    	{
        
    		randomized_partition(ar, left, right);	// 随机选取基准，置换到首位
    		int pos = Partition(ar, left, right);
    		QuickSort(Partition, ar, 0, pos - 1);
    		QuickSort(Partition, ar, pos + 1, right);
    	}
    }
    
    
    int main()
    {
        
    	std::random_device rd;
    	int times = 100;		// 测试n次
    	while (times--) {
        
    		int n = rd() % 20;			// 随机数组长度
    		vector<int> vec(n, 0);
    		for (int i = 0; i < n; i++)
    		{
        
    			vec[i] = rd() % 10000;	// 随机生成数组元素
    		}
    		vector<int> vec0(vec);
    		vector<int> vec1(vec);
    		vector<int> vec2(vec);
    
    		sort(vec.begin(), vec.end());
    		QuickSort(Partition, vec0, 0, vec0.size()-1);
    		QuickSort(Partition1, vec1, 0, vec1.size() - 1);
    		QuickSort(Partition2, vec2, 0, vec2.size() - 1);
    
    		// 三种快排和库提供的快排比较
    		if (vec != vec0) cout << "different： vec0" << endl;
    		if (vec != vec1) cout << "different： vec1" << endl;
    		if (vec != vec2) cout << "different： vec2" << endl;
    		cout << "pass" << endl;
    	}
    	return 0;
    }