快速排序王道写法
作者:
我是高情商
,
2024-09-09 19:12:32
,
所有人可见
,
阅读 3
#include<iostream>
#include<algorithm>
using namespace std;
//
如果你先执行 第二个 while(low < high && a[low] <= mid),从左往右寻找大于 mid 的元素并将它放在 a[high] 中,会导致右边的元素尚未经过检查,无法保证右边的元素都大于等于 mid。此时就可能把原本在右边的大元素错误地放到了左边,从而打乱了数组分割的正确性。
正确的顺序是先从右边找一个比 mid 小的元素,把它放到 low 的位置;再从左边找一个比 mid 大的元素,把它放到 high 的位置。通过这样的顺序,可以保证每次交换时,左侧区域的元素始终小于等于 mid,右侧区域的元素始终大于等于 mid。
因此,两个 while 循环的顺序确保了整个分割过程的正确性,不能颠倒。
int partition(int a[],int low,int high)//用来每次找最中间的那个元素(分割元素)
{
int mid=a[low];
while(low<high)
{
while(low<high&&a[high]>=mid) high--;
a[low]=a[high];
while(low<high&&a[low]<=mid) low++;
a[high]=a[low];
}
a[low]=mid;
return low;
}
void quicksort(int a[],int low,int high)//主要进行递归的函数,用来进行快速排序,quicksort
{
if(low<high)
{
int mid=partition(a,low,high);
quicksort(a,low,mid-1);
quicksort(a,mid+1,high);
}
}
int main()
{
int a[] = {1, 4, 2, 5, 7, 3, 2};
int n=sizeof(a)/sizeof(int);
quicksort(a,0,n-1);
for(int i=0;i<n;i++)
cout<<a[i]<<" ";
}