当前位置 博文首页 > SYP___:夜深人静写算法——快速排序(分治)
快速排序:采用分治的方法
?(一):
? ? ?(1) 将数组的第一个作为参考值,将所有小于该值的数移动到改值左侧,将所有大于该值的数移动到数组右侧(利用两个指针分别从数组的首尾开始向中间扫描);
? ? (2)将参考值的左侧和右侧看作新的两个数组
? ? (3)重新从(1)开始,直到数组的大小为0;
?
(二);
? ?如图为第一次递归,将小于23的移到左侧,大于23的移到右侧。
?
?
(三):
?程序如下:
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
using namespace std;
template <class Type>
void swap(Type *a,Type *b){
Type c;
c = *a;
*a = *b;
*b = c;
}
template <class Type>
void QuickSort(Type a[],int l,int r){ //排序从l到r的数组
if(l < r){ // 如果l >= r 不进行操作
int t = l;
int stl = l; //stl为左侧的指针
int str = r+1; //str为右侧指针
while(true){
while(a[++stl] <= a[t] && stl <= r); //stl扫描到大于 参考值 的值后停止扫描
while(a[--str]> a[t] && str >= 0); //str扫描到小于 参考值 的值后停止扫描
if(str < stl)break; //如果当前str小于stl 说明扫描完一遍,最外层while循环停止
swap(&a[stl],&a[str]); //交换两个指针的值
}
swap(&a[l],&a[str]); //交换参考值和str指针指向的值
QuickSort(a,l,str-1); //参考值左侧数组递归
QuickSort(a,str+1,r); //参考值右侧数组递归
}
}
int main(){
int a[10] = {4,3,2,6,1,5,7,9,8,0};
for(int i = 0;i < 10 ;i++){
cout<<a[i];
if(i == 9)cout<<endl;
else cout<<" ";
}
QuickSort(a,0,9);
cout<<"排序后"<<endl;
for(int i = 0 ;i < 10;i++){
cout<<a[i];
if(i == 9)cout<<endl;
else cout<<" ";
}
return 0;
}
?
cs