題目鏈接

這道題目鏈接可以用來測驗我們所書寫的演算法是否正確

排序陣列
在這里插入圖片描述

思路分析

首先我們來看快速排序的定義

快速排序由C. A. R. Hoare在1960年提出，它的基本思想是：通過一趟排序將要排序的資料分割成獨立的兩部分，其中一部分的所有資料都比另外一部分的所有資料都要小，然后再按此方法對這兩部分資料分別進行快速排序，整個排序程序可以遞回進行，以此達到整個資料變成有序序列，

我們可以看到的是快速排序首先需要確定一個基準元素，然后經過一趟快速排序，我們可以將陣列內元素以基準元素分為兩部分，前面一部分比基準元素小，后半部分比基準元素大，然后繼續分組，比較，最終得到一個有序陣列

因此我們整理出大概思路

挑選基準元素，作為我們比較的依據，我們一般默認為陣列的第一個元素作為我們基準元素
使用雙指標從后往前找第一個比基準元素小的元素從前往后找第一個比基準元素大的元素
當我們找到一個比基準元素大的元素和一個比基準元素小的元素時，我們交換兩個數字
當我們不斷交換，交換到最后兩個指標指向同一位置，說明我們一趟排序已經結束，我們再交換基準元素與指標指向的元素，觀察此時陣列就按斬訓準元素分為兩部分
我們按斬訓準元素將陣列劃分為兩個部分，然后分別進行上述程序

示例圖
在這里插入圖片描述
快速排序分步決議

先確定基準元素，然后從后往前找第一個比基準元素小的數
然后從左往右找第一個比基準元素大的元素
當兩方都找到后，進行交換

在這里插入圖片描述

然后繼續尋找

直到兩個指標指向同一個位置
將該位置與基準元素進行交換

這樣我們的一趟快速排序就結束了，然后一句左右劃磁區間，重復上述程序

我們知道的是，快速排序除了不穩定之外，還存在一個問題就是當陣列本身接近有序的時候，此時快速排序性能很差，因此，我們針對這個問題，提出一種三數取中的方法來對基準元素進行處理
我們比較陣列頭部，尾部，和中間元素，選擇一個中位數作為我們的基準元素，這樣就恩能夠改善快速排序在陣列基本有序時的性能問題

解題代碼

class Solution {
public:
	//三數取中
    int midValue(vector<int>&nums , int left, int right)
    {
        int mid = left + (right-left)/2;
        int ret = 0;
        if(nums[left] > nums[mid])
        {   
            if(nums[mid] > nums[right])
                return mid;
            else
            {
                ret = (nums[left] > nums[right]) ? right : left;
                return ret;
            }
        }
        else
        {
            if(nums[right] > nums[mid])
                return mid;
            else
            {
                ret = ((nums[left] > nums[right]) ? right : left);
                return ret;
            }
        }
    }
    void quickSort(vector<int>& nums, int left, int right)
    {
        if(left > right)
            return ;
        //取中位數
        int mid = midValue(nums, left, right);
        swap(nums[left], nums[mid]);
        int begin = left;
        int end = right;
        int key = left;
        while(left < right)
        {
            //從右往左找，找到一個比key小的值
            while(left < right && nums[right] >= nums[key])
            {
                --right;
            }
            //從左往右找，找到一個比key大的值
            while(left < right && nums[left] <= nums[key])
            {
                ++left;
            }
            //這里說明我們已經找到了兩個需要交換的數字
            swap(nums[left], nums[right]);
        }
        //這里說明交換完畢，這里我們需要將key值與right值進行交換
        //為什么是right？ 因為每次right先開始找，所以我們能保證right一定是較小值
        swap(nums[key], nums[right]);
        //這里進入遞回程序
        quickSort(nums, begin, right-1);
        quickSort(nums, right+1, end);
    }
    vector<int> sortArray(vector<int>& nums) {
        quickSort(nums, 0, nums.size()-1);
        return nums;
    }
};

進階指南

點擊此處可以跳轉至八大排序之歸并排序C++詳解

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/280999.html

標籤：其他

上一篇：FPGA實作正弦波加和及濾波（Vivado實作，內含IP核呼叫）

下一篇：位元組單位