快速排序算法的C++实现
程序员文章站
2024-03-18 11:26:34
...
关于快速排序算法的介绍可以参看此篇博客:https://www.cnblogs.com/onepixel/articles/7674659.html
网上关于快速排序的代码大多是用递归的方式来实现的,递归看起来很晕乎,就想能不能不用递归的方法来实现。
下面就介绍一下毛毛利用栈来实现的快速排序算法,代码只为验证算法功能,并不保证没有bug。闲话少说,先上代码。
#include <stack>
#include <vector>
#include <iostream>
using namespace std;
int classify(int arr[], int low,int high){
/*此函数实现分类功能,即输入一个数组,从此数组中选择一个值作为标准值,比标准值大的放右边,小的放左边*/
//low表示数组中需要进行分类的起始位置,类似地,high表示结束位置。
// 如需要对数组a[10]中位置为3—8的元素进行分类,low=3,high=8。
int base=high; //最后一个值作为标准值
int i=high-1; //从倒数第二个值开始循环
while(i>=low){ //指定循环次数
if(arr[base]<arr[i]) { //由于标准值位置在最后,只需要把比标准值大的放到右边即可
int tmp=arr[i];
int j=i+1;
while(j<=base) //while 循环负责把数组部分元素向左移位
{
arr[j-1]=arr[j];
j++;
}
arr[base]=tmp;
base--;//标准值所在的位置已经向左移了一位,需要更新一下。
}
i--;
}
return base;
}
void sort(int a[],int arrLen)
{
stack<int> stkInt;
//int a[]={9 ,8 ,3,10,1,3,5,7,8 ,1,10,13,5,4,2};
//int a[]={9 ,8 ,7,6};
int begin=0;
int end=arrLen-1;
stkInt.push(end);//先将数组最后一个值的位置压栈
while(!stkInt.empty())
{
int b=classify(a,begin,end);//b记录下分类后标准值在数组中所在的位置
if ((b-begin)>1){//如果b-begin>1,说明位置在[begin b)之间的元素至少有两个,还需要再次分类
stkInt.push(b);//因为还需要再次分类,所以b必须压栈
end=b-1;//下一次分类的最后的位置为b前面一位
}else{ //[begin b)之间的元素至多有一个,此时[begin b)之间不需要再次分类
begin=b+1; //下一次分类的起始位置就是b后面一位
end=stkInt.top();
}
if ((end-begin)<=1){//[begin end]之间的元素至多有一个,让栈顶中的标准值的位置出栈
stkInt.pop();
}
}
return ;
}
int main(int argc, char** argv){
int b[]={1,3,58,3,45,87,6,10,9 ,8 ,3,10,1,3,5,7,8 ,1,10,13,5,4,2,3};
sort(b,sizeof(b)/sizeof(int));
return 0;
}
下面以数组[ 7 5 6 2 1 3 4 ]为例对算法进行说明:
上一篇: ES6学习总结之变量的解构赋值