首页 > 代码库 > 快速排序与递归

快速排序与递归

2024-07-16 22:34:37   223人阅读

快速排序是一种效率比较高的算法，算法的思想是取出待排序中的一个元素，想办法将小于他的元素交换到他的左边，大于他的元素交换于他的右侧，然后对左右两侧再分别递归进行上述过程，直到左右两侧的元素只有一个。从而实现了整体的排序。c++实现的代码如下：

//快速排序（递归）
template<typename T>
void quick_sort(T *arr,int b,int e)
{
    if(b<e)
    {    
        int i=b,j=e;
        T x=arr[i];
        while(i<j)
        {    
            while(i<j && arr[j] >= x)
                --j;
            if(i<j)
            {
                arr[i] = arr[j];
                ++i;
            }
            while(i<j && arr[i] <= x)
                ++i;
            if(i<j)
            {
                arr[j] = arr[i];
                --j;
            }
        }
        arr[i] = x; 
        quick_sort(arr,b,i-1);
        quick_sort(arr,i+1,e);
    }
}

但是以递归方式实现快速排序的算法是不稳定的，如果待排序元素本身并不是非常符合算法的设计需求，比如说本身已经是逆序或者正序的，不但排序效率降低，而且导致递归深度迅速增加，甚至堆栈溢出。

虽然在算法处理上采用随机下标或其他手段进行优化，但是也只是概率上减少，而不能杜绝堆栈溢出问题。

因此可以非递归的方式实现该算法类解决堆栈溢出的问题，原理是先以循环的方式进行左侧排序，再以循环的方式进行右侧排序。c++代码如下：

template<typename T>
void quick_sort_no_recursive_left(T *arr,int b,int e)
{
    int i,j;
loop:
    if(b<e)
    {    
        i=b;
        j=e;
        T x=arr[i];
        while(i<j)
        {    
            while(i<j && arr[j] >= x)
                --j;
            if(i<j)
            {
                arr[i] = arr[j];
                ++i;
            }
            while(i<j && arr[i] <= x)
                ++i;
            if(i<j)
            {
                arr[j] = arr[i];
                --j;
            }
        }
        arr[i] = x; 
        e = i-1;
        goto loop;
    }
}

template<typename T>
void quick_sort_no_recursive_right(T *arr,int b,int e)
{
    int i,j;
loop:
    if(b<e)
    {    
        i=b;
        j=e;
        T x=arr[i];
        while(i<j)
        {    
            while(i<j && arr[j] >= x)
                --j;
            if(i<j)
            {
                arr[i] = arr[j];
                ++i;
            }
            while(i<j && arr[i] <= x)
                ++i;
            if(i<j)
            {
                arr[j] = arr[i];
                --j;
            }
        }
        arr[i] = x; 
        b = i+1;
        goto loop;
    }
}

//快速排序（非递归）
template<typename T>
void quick_sort_no_recursive(T *arr,int b,int e)
{
    quick_sort_no_recursive_left(arr,b,e);
    quick_sort_no_recursive_right(arr,b,e);
}


联系
我们