欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

快速排序算法的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 ]为例对算法进行说明:

 

快速排序算法的C++实现