Hello,米娜桑們，這里是君兮_，國慶長假結(jié)束了，無論是工作還是學(xué)習(xí)都該回到正軌上來了，從今天開始恢復(fù)正常的更新頻率，今天為大家?guī)淼膬?nèi)容是快速排序的兩大優(yōu)化和非遞歸實(shí)現(xiàn)

• 好了廢話不多說，開始我們今天的學(xué)習(xí)吧！！
  

快速排序優(yōu)化

• 有關(guān)快速排序的基本內(nèi)容可以去看看這篇博客，講的已經(jīng)非常詳細(xì)了
  【算法速查】萬字圖解帶你快速入門八大排序(下）
• 我們在這里就以hoare版本的快速排序來講講還可以優(yōu)化的地方以及為什么
• hoare版本的快速排序代碼如下：

Swap(int* p1, int* p2)
{
    int tmp = *p1;
    *p1 = *p2;
    *p2 = tmp;
}
int getMid(int* a, int left, int right)
{
    assert(a);
    int mid = (left + right) / 2;
    if (a[left] > a[mid])
    {
        if (a[mid] > a[right])
            return mid;
        else if(a[right]>a[left])
        {
            return left;
        }
        else
        {
            return right;
        }
    }
    else
    {
        if (a[mid] < a[right])
            return mid;
        else if (a[left] > a[right])
        {
            return left;
        }
        else
        {
            return right;
        }

    }
}
int PartSort1(int* a, int left, int right)
{
    int mid = getMid(a, left, right);//三數(shù)取中
    //把取好的key放到left中
    Swap(&a[left], &a[mid]);
    int key = left;
    while (left<right)
    {
    //右邊先走
        while (left < right && a[right] >= a[key])
        {
            right--;
        }
      //左邊走
        while (left<right&&a[left]<=a[key])
        {
            left++;
        }
        //交換
        Swap(&a[left], &a[right]);
    }
    //交換停下的位置的值把key換到此時(shí)左右相遇的位置
    Swap(&a[key], &a[left]);
    //此時(shí)key的左右都有序，由于right，left都指處于key的位置返回任意即可
    return right;
}
void QuickSort(int* a, int left,int right)
{
	//只剩下一個(gè)值了，說明已經(jīng)有序，不需要再排，遞歸結(jié)束
    if (left >= right)
        return;
   
    int key = PartSort1(a,left,right);
    //key已經(jīng)滿足左右都有序了不需要再排
    //排key的左邊
    QuickSort(a, left, key-1);
    //排key的右邊
    QuickSort(a, key+1, right);

}

三數(shù)去中優(yōu)化

• 我們知道，快速排序是先取一個(gè)key值然后讓左右兩邊有序來進(jìn)行排序的，因此key值的取值對我們快速排序的速度是有比較大的影響的，舉個(gè)最壞的例子，假設(shè)每次我們?nèi)〉降膋ey值都是此次所需排序數(shù)據(jù)中最小的，如下圖所示
  

• 此時(shí)的時(shí)間復(fù)雜度就是O(N^2)了，因此，我們需要對快速排序進(jìn)行優(yōu)化，盡量減少出現(xiàn)圖示的這種情況，就有了以下的代碼

int getMid(int* a, int left, int right)
{
    assert(a);
    int mid = (left + right) / 2;
    if (a[left] > a[mid])
    {
        if (a[mid] > a[right])
            return mid;
        else if(a[right]>a[left])
        {
            return left;
        }
        else
        {
            return right;
        }
    }
    else
    {
        if (a[mid] < a[right])
            return mid;
        else if (a[left] > a[right])
        {
            return left;
        }
        else
        {
            return right;
        }

    }
}

• 簡單的來說，上述這段代碼表示的是這樣的意思
  取最左，最右，中間三個(gè)數(shù)，分別對三個(gè)數(shù)進(jìn)行比較，最終取得的值就是處于三個(gè)值中中間的這個(gè)值。
• 通過上述這個(gè)優(yōu)化，此時(shí)所需排序的數(shù)據(jù)中總要比我們?nèi)〉玫膋ey值小以及比我們?nèi)〉玫膋ey值大的值存在，就能較大的提供我們的快排效率啦！

對遞歸次數(shù)的優(yōu)化

• 我們在使用遞歸版本的快速排序時(shí)，當(dāng)區(qū)間中的數(shù)比較少時(shí)，仍然使用遞歸的方式進(jìn)行是會消耗非常多不必要消耗的內(nèi)存的，還是舉個(gè)例子：假設(shè)此時(shí)區(qū)間中還有10個(gè)數(shù)需要排
  
• 我們遞歸返回的條件是left>=right,遞歸是棧中開辟空間進(jìn)行的，當(dāng)遞歸的層數(shù)過深，棧的大小又不是很大，就容易造成“爆?！保缟蠄D所示，為了排序這十個(gè)數(shù)，我們又遞歸了這么多層，是非常不明智的選擇，因此，我們在數(shù)據(jù)較少的情況出現(xiàn)時(shí)，可以使用插入排序等方法進(jìn)行排序，減少不必要的空間浪費(fèi)，也能提供我們快排的速度

void QuickSort1(int* a, int begin, int end)
{
	if (begin >= end)
		return;

	// 小區(qū)間優(yōu)化，小區(qū)間不再遞歸分割排序，降低遞歸次數(shù)
	if ((end - begin + 1) > 10)
	{
		int keyi = PartSort1(a, begin, end);

		// [begin, keyi-1] keyi [keyi+1, end]
		QuickSort1(a, begin, keyi - 1);
		QuickSort1(a, keyi + 1, end);
	}
	else
	{
		InsertSort(a + begin, end - begin + 1);
	}
}

• 好了，講完了上述對遞歸版本的快排優(yōu)化，接下來我們講講快速排序的非遞歸版本

非遞歸的快速排序

• 我們上面講了，遞歸是在?？臻g中進(jìn)行的，?？臻g又比較小，當(dāng)遞歸層數(shù)比較深時(shí)就會造成“爆?！?，因此對于快速排序這種我們常用的排序算法來說，掌握其非遞歸版本也是非常重要的
• 想要了解非遞歸，我們就必須從遞歸開始下手，我們再來看看遞歸的這段代碼

void QuickSort1(int* a, int begin, int end)
{
	if (begin >= end)
		return;

	// 小區(qū)間優(yōu)化，小區(qū)間不再遞歸分割排序，降低遞歸次數(shù)
	if ((end - begin + 1) > 10)
	{
		int keyi = PartSort1(a, begin, end);

		// [begin, keyi-1] keyi [keyi+1, end]
		QuickSort1(a, begin, keyi - 1);
		QuickSort1(a, keyi + 1, end);
	}
	else
	{
		InsertSort(a + begin, end - begin + 1);
	}
}

• 如果你學(xué)過數(shù)據(jù)結(jié)構(gòu)的話，會發(fā)現(xiàn)我們遞歸與棧是非常類似的，棧是后進(jìn)先出，最后再處理最先放入的，而遞歸也是先往深處走，再往回返，因此，我們在實(shí)現(xiàn)非遞歸的快速排序時(shí)，選用棧這種數(shù)據(jù)結(jié)構(gòu)來幫助我們進(jìn)行。

void QuickSortNonR(int* a, int left,int right)
{
    Stack st;
    StackInit(&st);//初始化棧
    StackPush(&st, left);//入棧
    StackPush(&st, right);
    while (!StackEmpty(&st))//判斷棧是否為空
    {
        int right = StackTop(&st);//后進(jìn)先出，取棧頂元素
        StackPop(&st);//此時(shí)的棧頂元素出棧
        int left = StackTop(&st);//此時(shí)的棧頂為left
        StackPop(&st);
        int key = PartSort1(a, left, right);//選key值
        if (key + 1 < right)//此時(shí)key+1小于right 把key+1作為下一次排序的左 right作為右入棧
        {
            StackPush(&st, key + 1);
            StackPush(&st, right);
        }
        if (left < key - 1)//key-1大于left key-1就為下一次循環(huán)的右，left為左
        {
            StackPush(&st, left);
            StackPush(&st, key - 1);
        }

    }
    //當(dāng)棧中沒有元素了，說明此時(shí)的左大于等于右，此時(shí)已經(jīng)沒有數(shù)據(jù)未進(jìn)行排序了
    StackDestroy(&st);//銷毀棧
}

• 和遞歸大致是一樣的，只不過我們是用棧的方式來模擬遞歸朝深度進(jìn)行，如果你能理解遞歸實(shí)現(xiàn)的快速排序，相信非遞歸實(shí)現(xiàn)的快速排序?qū)δ銇碚f也非常好理解
• 唯一需要注意的是入棧和出棧的順序，當(dāng)你開始先入右再入左的話，由于后進(jìn)先出的原因，先出的是左其中是右，這點(diǎn)在取棧頂元素作為排序的左右區(qū)間時(shí)一定要注意避免取錯(cuò)。

總結(jié)

• 好啦，我們總算把八大排序算法都講完了，算法這一塊光靠看代碼不是那么容易理解的，因此我花了大量的時(shí)間畫圖分析，希望能對你有所幫助
• 當(dāng)然，這篇文章創(chuàng)作的初衷是希望幫助初學(xué)者對排序算法有一個(gè)大致的了解，對已經(jīng)學(xué)過的人起到在需要使用的時(shí)候快速回憶的效果，因此可能還有一部分細(xì)節(jié)不全，之后我會挑出重點(diǎn)單獨(dú)出博客講解
• 有任何的問題和對文章內(nèi)容的疑惑歡迎在評論區(qū)中提出，當(dāng)然也可以私信我，我會在第一時(shí)間回復(fù)的??！

新人博主創(chuàng)作不易，如果感覺文章內(nèi)容對你有所幫助的話不妨三連一下再走唄。你們的支持就是我更新的動力?。?！

文章來源地址http://www.zghlxwxcb.cn/news/detail-720949.html

到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)與算法】如何對快速排序進(jìn)行細(xì)節(jié)優(yōu)化以及實(shí)現(xiàn)非遞歸版本的快速排序？的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！