【算法】- 排序 - 快速排序
前言
编译语言：c++
编译器：vs2022
一、快速排序思想
快速排序就是，选一个在数组里的数p，按照这个数将整个数组分隔为左边都比p小，右边都比p大，再在左半部选取一个p1,右半部再选取一个p2，再次重复以上操作，直到low等于了high。这样一说我们也能够发现，要运用到递归思想。
二、快速排序
//交换
void Swap(int* Q, int low, int high)
{
int tmp = Q[low];
Q[low] = Q[high];
Q[high] = tmp;
}
//获取位置
int partition(int* Q, int low, int high)
{
int p;//获取分隔左右两边的数
p = Q[low];//将第一个下标值给p
while (low < high)
{
if (low<high && Q[high]>p)//从右边找比p小的数
high--;
Swap(Q, low, high);//找到就进行交换，把小数换到p左边
if (low < high && Q[low] < p)
low++;//从左边找比p大的数
Swap(Q, low, high);//找到就进行交换，把大数换到右边
}
return low;
}
//快速排序
//进行递归
void QSort(int* Q, int low,int high)
{
int p;//获取下标
if (low < high)
{
p = partition(Q,low,high);//获取排好序分隔的数的下标
QSort(Q, low, p - 1);//再次进行分隔，获取排好序分隔的数的下标
QSort(Q, p + 1, high);//再次进行分隔，获取排好序分隔的数的下标
}
}
//快速排序入口
void QuickSort(int arr[])
{
QSort(arr,1, MAXSIZE);//快速排序入口
}
int main()
{
int arr[MAXSIZE + 1] = { 0,5,6,7,1,2,4,9,3,10,8 };
int i;
QuickSort(arr);
for (i = 1; i <= MAXSIZE; i++)
cout << arr[i] << " ";
return 0;
}
三、快速排序优化
其实，你会发现p = Q[low]找p比较关键，如果说找到p是最大的，那排序效率是是糟糕的，这里我们对p = Q[low]进行优化。我们这里取数组的三个数，第一个，最后一个和中间的一个，比较他们大小，大小为中间的数就为p的值。
if (Q[low] > Q[high])
Swap(Q, low, high);
if (Q[mid] > Q[high])
Swap(Q, mid, high);
if (Q[mid] > Q[low])
Swap(Q, mid, high);
p = Q[low];
我们找到合适的数后，在进行移动交换，这里的交换其实也可以被优化，我们用数组下标为0作为哨兵，这样只要进行交换，我们就可以直接替换为移动，直接赋值，这样比交换还好一些，
p = Q[low];
Q[0] = p;
while (low < high)
{
if (low<high && Q[high]>=p)//从右边找比p小的数
high--;
Q[low] = Q[high];//将比p小的数移动到Q[low]的位置
if (low < high && Q[low] <= p)
low++;//从左边找比p大的数
Q[high] = Q[low];//将比p小的数移动到Q[low]的位置
}
Q[low] = Q[0];//将哨兵上的数放在low下标位置上
return low;
对递归进行优化，当排序的序列划分极端不平衡，递归深度趋近于n，而不是平衡时的log2n栈的大小是有限的，所以我们要优化递归。所以我们采用尾递法
int p;//获取下标
while (low < high)
{
p = partition(Q,low,high);//获取排好序分隔的数的下标
QSort(Q, low, p - 1);//再次进行分隔，获取排好序分隔的数的下标
low = p + 1;//在左半部分排序好后，将右半部分第一个元素给low进行右部分排序
}
四、快速排序最终版
#define MAXSIZE 10
#include <iostream>
using namespace std;
//交换
void Swap(int* Q, int low, int high)
{
int tmp = Q[low];
Q[low] = Q[high];
Q[high] = tmp;
}
//获取位置
int partition(int* Q, int low, int high)
{
int mid,p;//获取分隔左右两边的数
mid = low + (low + high) / 2;//将第一个下标值给p
if (Q[low] > Q[high])
Swap(Q, low, high);
if (Q[mid] > Q[high])
Swap(Q, mid, high);
if (Q[mid] > Q[low])
Swap(Q, mid, high);
p = Q[low];
Q[0] = p;
while (low < high)
{
if (low<high && Q[high]>=p)//从右边找比p小的数
high--;
Q[low] = Q[high];//将比p小的数移动到Q[low]的位置
if (low < high && Q[low] <= p)
low++;//从左边找比p大的数
Q[high] = Q[low];//将比p小的数移动到Q[low]的位置
}
Q[low] = Q[0];//将哨兵上的数放在low下标位置上
return low;
}
//快速排序
//进行递归
void QSort(int* Q, int low,int high)
{
int p;//获取下标
while (low < high)
{
p = partition(Q,low,high);//获取排好序分隔的数的下标
QSort(Q, low, p - 1);//再次进行分隔，获取排好序分隔的数的下标
low = p + 1;//在左半部分排序好后，将右半部分第一个元素给low进行右部分排序
}
}
//快速排序入口
void QuickSort(int arr[])
{
QSort(arr,1, MAXSIZE);//快速排序入口
}
int main()
{
int arr[MAXSIZE + 1] = { 0,5,6,7,1,2,4,9,3,10,8 };
int i;
QuickSort(arr);
for (i = 1; i <= MAXSIZE; i++)
cout << arr[i] << " ";
return 0;
}
总结
快速排序就是找一个数当作分割线，最好能使左半部分和右半部分数平均，这样这样递归，一直递归下去直到left==high，这样也就排序好了。
原文地址：https://blog.csdn.net/2302_77182146/article/details/142693421
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！