思路:
利用分治法的思想,将一个大问题分解成两个相同结构的子问题,然后分为治之。
????????先确定一个key值作为基准,然后进行比较,比key值小的放在key的左面,比key大的放在key的右边。
????????以第一次为例,辅助图如下,在32位置确定之后数组变成了arry={23,18,7},32,{74,55,45},这样我们就将比32小的书放置在32的左面,比32大的数放置在32的右面,然后再将{23,18,7},{74,55,45}以上述方法分别进行排序,直到begin==height则排序结束。
?代码:
#include<bits/stdc++.h>
using namespace std;
int n1;
//一个交换函数
void swap(int *a,int *b){
int temp = *a;
*a=*b;
*b=temp;
}
void quickrow(int *arry,int begin,int end){
//如果左右标重合,则说明已经划分到最小
if(begin>=end){
return;
}
//l指左标,h指右标
int l=begin,h=end;
//若l==h则说明区域划分结束
while(l<h){
//arry[l]为基准,若arry[l]<arry[h],则说明不需要我们交换位置,右标向左移动
while(arry[l]<arry[h]){
h--;
}
//判断左右标是否重合
if(l<h){
swap(arry[l],arry[h]);
l++;
}
//arry[h]为基准,判断arry[l]<arry[h],则说明不需要我们交换位置,左标向右移动
while(arry[l]<arry[h]){
l++;
}
//判断左右标是否重合
if(l<h){
swap(arry[l],arry[h]);
h--;
}
}
quickrow(arry,begin,h-1);
quickrow(arry,h+1,end);
}
int main(){
cin>>n1;
int number[n1];
for(int i=0;i<n1;i++){
cin>>number[i];
}
quickrow(number,0,n1-1);
for(int i=0;i<n1;i++){
cout<<number[i]<<" ";
}
}
|