17.【快速排序及三分取中优化详解】

发布于:2023-01-24 ⋅ 阅读:(15) ⋅ 点赞:(0) ⋅ 评论:(0)

(一)、快速排列的基本原理:

关于快速排序,它的基本思想就是选取一个基准,一趟排序确定两个区间,一个区间全部比基准值小,另一个区间全部比基准值大,接着再选取一个基准值进行排序,依次类推,最后得到一个有序的数列.
在这里插入图片描述

(二)、运用快速排列的注意事项:

切记在while 循环中,时是右边的先动,然后左边的后动,前后位置可不能整反.

(三)、基本思想和思路:

首先我们要进行函数调用设置:把数组的地址,起始位置、终点位置都要传送给回调函数,然后我们要在回调函数中进行一下操作,判断左边位置是否要小于右边位置,假如说小于进行: while循环,进行i++,j–操作,当就遇到的数字比基准值小的时候就停止,i遇到比基准值大的数值时停止,假如说此时此刻的位置是i<j的,那么就让他俩交换数据.如果时i>j的那么就要i的值和基准值进行交换。退出while循环,然后再重新定义一个基准值进行交换,然后再递归两次函数即可.

(四)、实战项目:

1.升序代码展现:

#include <iostream>
#include <string.h>
using namespace std;
void Qicklysort(int arry[],int left, int right)
{
	if (left >= right)return;           //假如说左边大于等于右边    退出这个结构体
	int l = left;
	int r = right;
	int base = arry[left];
	while (l < r)
	{
		while (l < r && arry[r] >= base)                  //从右向左开始移动直到遇到小于base的值为止
		{
			r--;
		}
		while (l < r && arry[l] <= base)                //从左向右开始移动直到遇到大于base的值为止。
		{
			l++;
		}
		if (l < r)                                  //停止后是为了交换位置:
		{
			int temp;
			temp = arry[l];
			arry[l] = arry[r];
			arry[r] = temp;
		}
	}
	base = arry[left];
	arry[left] = arry[l];           //目的是为了让基准数和最左边的数据交换换
	arry[l] = base;
	Qicklysort(arry, left, l - 1);          //判断从0到l的项目 ,不包括l
	Qicklysort(arry, l+1, right);
}
int main()
{
	int n, a[100];
	cout << "请输入你要排序的个数:" << endl;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cout << "请输入第" << i + 1 << "个数:" << endl;
		cin >> a[i];
	}
	Qicklysort(a, 0, n - 1);
	cout << "排序后为:" << endl;
	for (int i = 0; i < n; i++)
	{
		cout << a[i] << " ";
	}

}

2.升序效果展现:

在这里插入图片描述

3.降序代码展现:

在这里插入图片描述

#include <iostream>
#include <string.h>
using namespace std;
void Qicklysort(int arry[],int left, int right)
{
	if (left >= right)return;          
	int l = left;
	int r = right;
	int base = arry[left];
	while (l < r)
	{
		while (l < r && arry[r] <= base)                  //改变
		{
			r--;
		}
		while (l < r && arry[l] >= base)                  //改变
		{
			l++;
		}
		if (l < r)                                  
		{
			int temp;
			temp = arry[l];
			arry[l] = arry[r];
			arry[r] = temp;
		}
	}
	base = arry[left];
	arry[left] = arry[l];           
	arry[l] = base;
	Qicklysort(arry, left, l - 1);          
	Qicklysort(arry, l+1, right);
}
int main()
{
	int n, a[100];
	cout << "请输入你要排序的个数:" << endl;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cout << "请输入第" << i + 1 << "个数:" << endl;
		cin >> a[i];
	}
	Qicklysort(a, 0, n - 1);
	cout << "排序后为:" << endl;
	for (int i = 0; i < n; i++)
	{
		cout << a[i] << " ";
	}

}

4.降序效果展现:

在这里插入图片描述

(五)、if(表达式)return; 介绍

在这里插入图片描述

1.简单介绍:

if()return;表示假如表达式为真,那么后面的就不再执行了。为假就继续执行.

2.代码展示:

切记主函数可能为 int 只能为void

#include <iostream>
using namespace std;
void main()
{
	int a = 3;
	cout << "a1=" << a << endl;
	if (a < 4) return;
	cout << "a2=" << a << endl;
	cout << "a3=" << a << endl;

}

3.效果展示:

在这里插入图片描述

(六)、EOF介绍:

在这里插入图片描述

1.简单说明:

2.代码展示:

3.效果展示:

(七)、三分取中法

在这里插入图片描述

1.什么是三分取中?

为了提高快速排序的时间效率,使用三分取中的方法,可以降低时间复杂度。三分区中的基本概念就是:取第一个值,中间值,最后值。然后取三个值的中位数作为基准,进行运算.

2.三分取中的思想和基本思路?

首先我们要确定我们想要进行排序的数目,然后设置一个回调函数Quickly(),然后进行轴的位置确定,然后将基准值放在最后一位。代入partition()函数,目的是为了进行初步排序,然后再进行基准值的改定,其余思路和普快一样.

3.降序实战项目:

代码展示:

#include<iostream>
using namespace std;
int partition(int* P, int l, int r, int& pivot) {
	int temp;
	while (l < r) {
		while (P[l] >= pivot && l < r)    // l右移直到l对应的值小于轴值
			l++;
		while (P[r] <= pivot && l < r)    // r左移直到r对应的值大于于轴值
			r--;
		temp = P[l];    // 交换l和r对应的值
		P[l] = P[r];
		P[r] = temp;
	}
	return l;
}
void Quick_sort(int* P, int i, int j) {
	if (j <= i) return;           // 判断元素个数为0或1时不进行排序直接返回
	int temp;
	int pivotindex = (i + j) / 2;  // 确定轴值的位置
	temp = P[j];               // 将轴值调放在最后
	P[j] = P[pivotindex];
	P[pivotindex] = temp;
	int k = partition(P, i, j, P[j]); // 将右边的第一个位置放在k中
	temp = P[k];           // 将轴值放到r和l相遇的位置
	P[k] = P[j];
	P[j] = temp;
	Quick_sort(P, i, k - 1);   // 递归调用将序列分段排序
	Quick_sort(P, k + 1, j);
}
int main() {
	int A[10];
	for (int i = 0; i < 5; i++)
		cin >> A[i];
	Quick_sort(A, 0, 4);
	for (int i = 0; i < 5; i++)
		cout << A[i] << " ";
	system("pause");
}

效果展示:

在这里插入图片描述

1.升序实战项目:

代码展示:

#include<iostream>
using namespace std;
int partition(int* P, int l, int r, int& pivot) {
	int temp;
	while (l < r) {
		while (P[l] <= pivot && l < r)    // l右移直到l对应的值小于轴值
			l++;
		while (P[r] >= pivot && l < r)    // r左移直到r对应的值大于于轴值
			r--;
		temp = P[l];    // 交换l和r对应的值
		P[l] = P[r];
		P[r] = temp;
	}
	return l;
}
void Quick_sort(int* P, int i, int j) {
	if (j <= i) return;           // 判断元素个数为0或1时不进行排序直接返回
	int temp;
	int pivotindex = (i + j) / 2;  // 确定轴值的位置
	temp = P[j];               // 将轴值调放在最后
	P[j] = P[pivotindex];
	P[pivotindex] = temp;
	int k = partition(P, i, j, P[j]); // 将右边的第一个位置放在k中
	temp = P[k];           // 将轴值放到r和l相遇的位置
	P[k] = P[j];
	P[j] = temp;
	Quick_sort(P, i, k - 1);   // 递归调用将序列分段排序
	Quick_sort(P, k + 1, j);
}
int main() {
	int A[10];
	for (int i = 0; i < 5; i++)
		cin >> A[i];
	Quick_sort(A, 0, 4);
	for (int i = 0; i < 5; i++)
		cout << A[i] << " ";
	system("pause");
}

效果展示:

在这里插入图片描述