排序算法之快速排序-蒲公英云

排序算法之快速排序

Dear 丶 2022-09-25 15:24 288阅读 0赞

同样的先上这张图

Center

下面分析交换排序之快速排序：

快速排序的思想是先选择一个基准元素（一般取第一个元素），然后对剩下的元素作两端遍历，左边找到比基准元素大的元素，右边找到比基准元素小的元素，两者交换，重复下去直到low>high，再把基准元素跟high交换。这样一遍下来，基准元素左边的元素都比基准元素小，基准元素右边的元素都比基准元素大。

然后对基准元素左边和右边分别作快速排序。

快速排序是通常被认为在同数量级（O(nlog2n)）的排序方法中平均性能最好的。但若初始序列按关键码有序或基本有序时，快排序反而蜕化为冒泡排序。一般公认的比较好的排序算法是先用快速排序使序列基本有序，当快速排序递归到一定深度后转为堆排序或插入排序，比如内省排序就是先快速后堆。

快速排序最好及平均情况时间复杂度为O(nlogn)，最坏情况为O(n2)。

快速排序并不需要额外的空间，空间复杂度为O(1)。

快速排序是不稳定的。

AS代码：

/**
         * 快速排序实现函数
         * 先一个基准，把小于基准的元素放到左边，大于基准的元素放到右边
         * 返回基准
         */
        private function Partition(arr:Array,first:int,last:int):int{
            var temp:Number;
            //确定基准元素
            var privot:int=arr[first];
            var low:int=first+1;
            var high:int=last;
            while(low<high){
                //找到第一个比基准元素小的无素
                while(low<=high && arr[high]>=privot){
                    high--;
                }
                //找到第一个比基准元素大的元素
                while(low<=high && arr[low]<=privot){
                    low++;
                }
                if(low<high){
                    temp=arr[low];
                    arr[low]=arr[high];
                    arr[high]=temp;
                }
            }
            //把基准元素交换到中间去
            if(privot>arr[high]){
                arr[first]=arr[high];
                arr[high]=privot;
                return high;
            }else{
                return first;
            }
        }
        /**
         * 快速排序
         */
        private function QuickSort(arr:Array,low:int,high:int):void{
            if(low<high){
                var privotIndex:int=Partition(arr,low,high);
                QuickSort(arr,low,privotIndex-1);
                QuickSort(arr,privotIndex+1,high);
            }
        }

C++代码

/*
* 快速排序
* 确定一个基准元素，把比基准元素小的元素放左边，大的放右边
* 然后再递归对左右两边的元素作快速排序
* 最好和平均O(nlogn),最坏O(n2)
* O(1)
* 不稳定
*/
template<typename T>
void SortHelp<T>::quickSort(T l[], int length, int low, int high)
{
    if (low < high)
    {
        int pivot = partition(l, length, low, high);
        quickSort(l, length, low, pivot - 1);
        quickSort(l, length, pivot + 1, high);
    }
}
template<typename T>
int SortHelp<T>::partition(T l[], int length, int low, int high)
{
#ifdef a
    //确定基准元素下标
    int pivot = low;
    low++;
    while (low < high)
    {
        while (low < high && l[high] >= l[pivot])
        {
            high--;
        }
        while (low < high && l[low] <= l[pivot])
        {
            low++;
        }
        if (low < high)
        {
            l[low] += l[high];
            l[high] = l[low] - l[high];
            l[low] = l[low] - l[high];
        }
    }
    if (l[high] < l[pivot])
    {
        l[pivot] += l[high];
        l[high] = l[pivot] - l[high];
        l[pivot] = l[pivot] - l[high];
        pivot = high;
    }
    return pivot;
#else
    int pivot = l[low];
    while (low < high)
    {
        //从后面找大的数往前填补
        while (low < high && l[high] >= pivot)
        {
            high--;
        }
        if (l[high] < pivot)
        {
            l[low++] = l[high];
        }
        //从前面找小的数往后填补
        while (low < high && l[low] <= pivot)
        {
            low++;
        }
        if (l[low] > pivot)
        {
            l[high--] = l[low];
        }
    }
    //填补最后一个元素并返回
    l[high] = pivot;
    return high;
#endif // 0
}