国产 无码 综合区,色欲AV无码国产永久播放,无码天堂亚洲国产AV,国产日韩欧美女同一区二区

  1. Toy模板網(wǎng)首頁
  2. >Toy博客

【數(shù)據(jù)結(jié)構(gòu)與算法】：選擇排序與快速排序

2年前作者：QuiteCoder分類：Toy博客閱讀(24)違法舉報

這篇具有很好參考價值的文章主要介紹了【數(shù)據(jù)結(jié)構(gòu)與算法】：選擇排序與快速排序。希望對大家有所幫助。如果存在錯誤或未考慮完全的地方，請大家不吝賜教，您也可以點擊"舉報違法"按鈕提交疑問。

【數(shù)據(jù)結(jié)構(gòu)與算法】：選擇排序與快速排序,數(shù)據(jù)結(jié)構(gòu)與算法,排序算法,算法,數(shù)據(jù)結(jié)構(gòu)

??個人主頁： Quitecoder

??專欄：數(shù)據(jù)結(jié)構(gòu)與算法

我的博客即將同步至騰訊云開發(fā)者社區(qū)，邀請大家一同入駐：騰訊云

歡迎來到排序的第二個部分：選擇排序與快速排序！

【數(shù)據(jù)結(jié)構(gòu)與算法】：選擇排序與快速排序,數(shù)據(jù)結(jié)構(gòu)與算法,排序算法,算法,數(shù)據(jù)結(jié)構(gòu)

1.選擇排序

選擇排序是一種簡單直觀的比較排序算法。該算法的基本思想是在每一輪中選出當前未排序部分的最?。ɑ蜃畲螅┰兀缓髮⑵浞胖玫轿磁判蛐蛄械钠鹗嘉恢?，這個過程一直重復直至整個數(shù)組被排序。

選擇排序的具體步驟如下：

  1. 從數(shù)組的當前未排序部分選擇最?。ɑ蜃畲螅┑囊粋€元素
  2. 將這個最小（或最大）元素與未排序序列的第一個元素交換位置
  3. 然后從剩余未排序的元素中繼續(xù)這個過程，將每一次找到的最?。ɑ蜃畲螅┰胤诺轿磁判蛐蛄械拈_始
  4. 這個過程一直進行到整個數(shù)組的所有元素都被排為有序狀態(tài)

【數(shù)據(jù)結(jié)構(gòu)與算法】：選擇排序與快速排序,數(shù)據(jù)結(jié)構(gòu)與算法,排序算法,算法,數(shù)據(jù)結(jié)構(gòu)

在這里我們可以遍歷一次同時找到最小元素和最大元素，對應放到相應的位置，
基本代碼如下：

void SelectSort(int* a, int n)
{
	int begin = 0;
	int end = n - 1;
	while (begin < end)
	{
		int minn = begin;
		int maxn = begin;
		for (int i = begin + 1; i <= end; i++)
		{
			if (a[i] < a[minn])
			{
				minn = i;
			}

			if (a[i] > a[maxn])
			{
				maxn = i;
			}
		}
		Swap(&a[begin], &a[minn]);
		Swap(&a[end], &a[maxn]);
		begin++;
		end--;
	}
}
  1. 首先初始化兩個索引begin和end，分別代表當前未排序序列的開始和結(jié)束位置
  2. 進入一個循環(huán)，條件是begin < end，確保在數(shù)組中還有未排序的元素
  3. 遍歷一遍序列，找到最大元素和最小元素的下標
  4. 將最小元素與序列的始端交換，最大元素與序列的尾端交換
  5. 更新begin與end

Swap函數(shù)如下：

void Swap(int* a, int* b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

思考一下，這里我是首先進行最小元素與首位置更換，再進行最大元素與末尾更換，那如果我的最大元素就在首位置呢？

我們進行解釋：
【數(shù)據(jù)結(jié)構(gòu)與算法】：選擇排序與快速排序,數(shù)據(jù)結(jié)構(gòu)與算法,排序算法,算法,數(shù)據(jù)結(jié)構(gòu)
6f71.png)
在這組數(shù)組

  1. 我們首先找到0的下標8
  2. 再找到9的下標0
  3. 下標8與begin（0）交換
  4. 下標0與end交換

【數(shù)據(jù)結(jié)構(gòu)與算法】：選擇排序與快速排序,數(shù)據(jù)結(jié)構(gòu)與算法,排序算法,算法,數(shù)據(jù)結(jié)構(gòu)

這里由于最大元素9在起始位置，所以第一次交換后，9的索引不在是0，我們需要更新索引：

void SelectSort(int* a, int n)
{
	int begin = 0;
	int end = n - 1;
	while (begin < end)
	{
		int minn = begin;
		int maxn = begin;
		for (int i = begin + 1; i <= end; i++)
		{
			if (a[i] < a[minn])
			{
				minn = i;
			}

			if (a[i] > a[maxn])
			{
				maxn = i;
			}
		}
		Swap(&a[begin], &a[minn]);
		if (minn == begin)
		{
			maxn = minn;
		}
		Swap(&a[end], &a[maxn]);
		begin++;
		end--;
	}
	
}

if (minn == begin)
		{
			maxn = minn;
		}

改變最大值的索引，再進行交換，這就是選擇排序的完整過程

1.1復雜度分析

時間復雜度

最好、平均、最壞情況下的時間復雜度都是 O(n^2)
原因在于，不管數(shù)組的初始順序如何，選擇排序都需要比較所有未排序的元素來找到最?。ɑ蜃畲螅┑脑?，并執(zhí)行這個過程 n-1 次（對于 n 個元素的數(shù)組）。每次選擇操作需要比較的次數(shù)從 n-1 次減少到 1 次，總共的比較次數(shù)是 (n-1) + (n-2) + … + 1 = n(n-1)/2，這是一個二次函數(shù)，因此時間復雜度為 O(n2)

空間復雜度

選擇排序是一種原地排序算法，除了輸入數(shù)組外，它只需要有限的幾個變量（比如，用于存儲最小元素下標的變量和循環(huán)計數(shù)器）。因此，它的空間復雜度為常數(shù)空間，O(1)

其他特點

選擇排序是不穩(wěn)定的排序算法，因為它會因為選擇最?。ɑ蜃畲螅┰氐倪^程中交換距離較遠的元素，從而可能改變相同元素的原始順序

2.快速排序的層層實現(xiàn)

快速排序是Hoare于1962年提出的一種二叉樹結(jié)構(gòu)的交換排序方法，其基本思想為：任取待排序元素序列中的某元素作為基準值，按照該排序碼將待排序集合分割成兩子序列，左子序列中所有元素均小于基準值，右子序列中所有元素均大于基準值，然后最左右子序列重復該過程，直到所有元素都排列在相應位置上為止。

快速排序是一種高效的排序算法，**采用了分治法（Divide and Conquer）**的策略。它的基本思路可以概括為以下幾個步驟：

  1. 選擇樞軸（Pivot）： 快速排序首先從數(shù)組中選擇一個元素作為樞軸，樞軸的選擇可以有多種方式，比如總是選擇第一個元素、最后一個元素、中間的元素，或者采用更復雜的策略如三數(shù)中值法

  2. 分區(qū)（Partitioning）： 一旦樞軸被選擇，數(shù)組會被重新排列，所有比樞軸小的元素移動到樞軸的左邊，所有比樞軸大的元素移動到右邊。這個過程結(jié)束時，樞軸元素處于其最終排序后的正確位置。

  3. 遞歸排序： 接下來，快速排序算法遞歸地將左邊和右邊的子數(shù)組進行排序。遞歸的基準條件是子數(shù)組的大小為0或1，這意味著它們已經(jīng)被排序了

我們不妨舉個例子

假設(shè)我們有以下數(shù)組：

[3, 6, 8, 10, 1, 2, 4]

我們將用快速排序來對這個數(shù)組進行排序。為了簡單起見，我們選擇數(shù)組的第一個元素作為樞軸。實際應用中可能會使用更復雜的選擇方法，如隨機選擇或三數(shù)中值法，以避免最壞情況的性能下降?，F(xiàn)在，讓我們開始排序：

  1. 初始數(shù)組:

    [3, 6, 8, 10, 1, 2, 4]

    樞軸是 3。

  2. 分區(qū)操作:
    將數(shù)組中小于3的元素移動到左邊，大于3的元素移動到右邊。這一步結(jié)束后，樞軸3位于其最終位置。

    [2, 1, 3, 10, 8, 6, 4]

    此時，3位于索引2，是其最終位置。

  3. 遞歸排序左邊 [2, 1] 和右邊 [10, 8, 6, 4] 的子數(shù)組。

    • 對于左邊的 [2, 1]，選擇2作為樞軸。
      • 分區(qū)操作后，得到 [1, 2]。
    • 對于右邊的 [10, 8, 6, 4]，選擇10作為樞軸。
      • 分區(qū)操作后，得到 [4, 8, 6, 10]。

  4. 現(xiàn)在，對 [4, 8, 6] 進行快速排序。

    • 選擇4作為樞軸。
    • 分區(qū)操作后，得到 [4, 8, 6]。

  5. 最后，對 [8, 6] 進行快速排序。

    • 選擇8作為樞軸。
    • 分區(qū)操作后，得到 [6, 8]。

合并所有排好序的部分，最終排序結(jié)果是：

[1, 2, 3, 4, 6, 8, 10]

每次分區(qū)操作都確保樞軸元素被放置在其最終位置。通過遞歸地處理樞軸左側(cè)和右側(cè)的子數(shù)組，最終整個數(shù)組變得有序

2.1分區(qū)操作

分區(qū)操作是快速排序算法中的核心步驟。它的目標是根據(jù)樞軸元素重新排列數(shù)組的部分區(qū)間，使得所有比樞軸小的元素都移到它的左邊，而所有比樞軸大的元素都移到它的右邊。在這個過程中，樞軸元素自身也找到了其在數(shù)組中的正確位置。這個步驟是遞歸進行排序的前提。下面詳細解釋這個過程：

  1. 設(shè)置指針：
    設(shè)置兩個指針，left指向數(shù)組的開始（或樞軸的下一個元素，取決于樞軸的選擇），right指向數(shù)組的末尾。

  2. 指針移動和交換：
    向右移動left指針：從left開始向右移動，直到找到一個大于或等于樞軸值的元素，向左移動right指針：從right開始向左移動，直到找到一個小于或等于樞軸值的元素

  3. 檢查和交換：如果left指針仍在right指針的左側(cè)（即left < right），則交換left和right指向的元素，并繼續(xù)移動指針。

  4. 遞歸的終止條件：
    當left指針超過right指針，即left >= right時，分區(qū)操作結(jié)束。此時，所有比樞軸小的元素都在它的左邊，而所有比樞軸大的元素都在它的右邊

單趟排序代碼實現(xiàn)如下：

int left = begin;
int right = end;
int key = begin;
while (left < right)
{
	while (left < right && a[right] >= a[key])
	{
		right--;
	}
	while (left < right && a[left] <= a[key])
	{
		left++;
	}
	Swap(&a[right], &a[left]);
}
Swap(&a[left], &a[key]);
key = left;

  1. 初始化指針和樞軸：

    • left初始化為begin，這是當前考慮的數(shù)組段的起始位置
    • right初始化為end，這是當前考慮的數(shù)組段的結(jié)束位置
    • key用于記錄樞軸的位置，這里選擇的是數(shù)組段的第一個元素作為樞軸，因此key初始化為begin

  2. 分區(qū)過程：

    • 外層循環(huán)：while (left < right)確保當左右指針相遇或交錯時，循環(huán)停止。這意味著分區(qū)過程完成。

    • 右側(cè)掃描：第一個內(nèi)層循環(huán)while (left < right && a[right] >= a[key])從右向左移動right指針，尋找第一個小于樞軸值a[key]的元素。

    • 左側(cè)掃描：第二個內(nèi)層循環(huán)while (left < right && a[left] <= a[key])從左向右移動left指針，尋找第一個大于樞軸值a[key]的元素。

    • 交換：Swap(&a[right], &a[left])交換左右指針所指向的元素。這次交換是為了把小于樞軸值的元素移動到樞軸的左側(cè)，大于樞軸值的元素移動到樞軸的右側(cè)

  3. 樞軸歸位：

    • 循環(huán)結(jié)束時，left和right指針相遇。此時，left指針的位置就是樞軸元素應該所在的最終位置。（這里下面再做解釋）
    • Swap(&a[left], &a[key])交換樞軸元素與left指針所指的元素。這步確保了樞軸元素被放置在其正確的位置，即所有左側(cè)元素都不大于它，所有右側(cè)元素都不小于它
    • 最后，將key更新為left，盡管在這個代碼片段中，這個賦值操作對于后續(xù)流程并不是必需的，因為key的值在這之后沒有再被使用。如果這是分區(qū)函數(shù)的一部分，key（或者這里應該是left）的新值可能會被用來指示下一步遞歸操作的分界點。

2.2相遇位置小于樞軸元素

這里我們就可以分多種情況進行討論：

  • right遇到left：注意，代碼中我們是先讓right移動的，意味著left所指向的是上一此交換后小于樞軸元素的數(shù)，所以當相遇后，key與left交換，left指向的元素一定小于key指向的元素
  • left遇到right：由于right先動，意味著right已經(jīng)找到了一個比key小的元素，當left遇到right使，此時right，left指向的元素一定小于key指向的元素。

2.3遞歸實現(xiàn)整個函數(shù)

一旦樞軸元素被放置在其正確位置上，數(shù)組就被分成了兩部分。左邊的子數(shù)組包含了所有小于樞軸的元素，而右邊的子數(shù)組包含了所有大于樞軸的元素。這時，獨立地對左右兩個子數(shù)組應用同樣的快速排序過程。這就是遞歸的步驟，因為同一個過程被用來排序較小的數(shù)組

遞歸終止條件：遞歸的終止條件是子數(shù)組的大小減到0或1，這時不需要做任何操作：

  • 大小為0的子數(shù)組意味著在分區(qū)過程中，沒有元素被劃分到某一側(cè)。例如，如果樞軸是最?。ɑ蜃畲螅┰兀⑶宜衅渌囟急粍澐值搅藰休S的另一側(cè)，那么這一側(cè)實際上就沒有元素，子數(shù)組的長度為0

  • 大小為1的子數(shù)組意味著在分區(qū)過程結(jié)束后，某一側(cè)只有一個元素。由于任何單一元素的集合自然是已排序的（因為沒有其他元素可以與之比較大小），這意味著不需要對這樣的子數(shù)組進行進一步的排序操作

代碼實現(xiàn)如下：

void Quicksort(int* a, int begin, int end)
{

	if (begin >= end)
	{
		return;
	}
	int left = begin;
	int right = end;
	int key = begin;
	while (left < right)
	{
		while (left < right && a[right] >= a[key])
		{
			right--;
		}
		while (left < right && a[left] <= a[key])
		{
			left++;
		}
		Swap(&a[right], &a[left]);
	}
	Swap(&a[left], &a[key]);
	key = left;
	Quicksort(a, begin, key - 1);
	Quicksort(a, key + 1, end);
}

  • 遞歸的終止條件：if (begin >= end)檢查當前的子數(shù)組是否已經(jīng)是不可分割的，即長度為0或1。如果滿足這個條件，函數(shù)就會直接返回，不再繼續(xù)執(zhí)行后續(xù)的排序操作

  • 初始化變量：變量left和right被初始化為子數(shù)組的起始和結(jié)束索引。變量key作為樞軸的索引也被初始化為begin，即子數(shù)組的第一個元素

2.4復雜度分析

每一層的時間復雜度：每一層的時間復雜度在快速排序中的推導基于對數(shù)組的分區(qū)操作。對于一個包含(n)個元素的數(shù)組，分區(qū)操作的時間復雜度是(O(n))。這是因為在分區(qū)過程中，每個元素都會被檢查一次以確定它們是應該放在樞軸的左邊還是右邊。

最好情況、平均情況和最壞情況：

  1. 最好情況：當每次分區(qū)操作都能將數(shù)組均等分成兩部分，快速排序的性能接近其理論最優(yōu)。這種情況下，遞歸樹的深度是 log n ，其中每一層的處理時間總和是( O(n) )）。因此，最好情況下的時間復雜度是( O(n log n) )。

  2. 平均情況：在隨機選擇的數(shù)組中，快速排序的平均時間復雜度也是( O(n \log n) )。雖然每次分區(qū)可能不會完全平等，但平均而言，遞歸樹的深度依然保持在( \log n )的數(shù)量級，每一層的處理時間總和為( O(n) )

  3. 最壞情況：最壞情況發(fā)生在每次分區(qū)操作時，都將數(shù)組分成大小極度不平衡的兩部分，如一個元素和其余元素，即在有序的情況下。這種情況下，遞歸樹的深度增長到( n )，每次分區(qū)操作依然需要( O(n) )的時間，因此最壞情況下的時間復雜度是( O(n^2) )

【數(shù)據(jù)結(jié)構(gòu)與算法】：選擇排序與快速排序,數(shù)據(jù)結(jié)構(gòu)與算法,排序算法,算法,數(shù)據(jù)結(jié)構(gòu)

空間復雜度：快速排序的空間復雜度主要由遞歸調(diào)用棧的深度決定。在最好情況下，遞歸樹的深度是( log n )，因此空間復雜度是( O(log n) )。在最壞情況下，遞歸樹的深度可以達到( n )，此時空間復雜度為( O(n) )。這是因為每一層遞歸調(diào)用都需要一定的空間，而遞歸樹的深度直接影響調(diào)用棧的大小

2.5 代碼優(yōu)化：三數(shù)取中法選key

三數(shù)取中法是在實現(xiàn)快速排序時用來提高性能并降低遇到最壞情況概率的一種技術(shù)。該方法通過選擇一個較為接近中值的樞軸元素來分區(qū)數(shù)組，以避免每次都產(chǎn)生不平衡的分區(qū)，從而增加算法的效率

在三數(shù)取中法中，我們通常取數(shù)組中以下三個值：

  1. 起始值（通常是數(shù)組的第一個元素）
  2. 結(jié)束值（通常是數(shù)組的最后一個元素）
  3. 中間值（數(shù)組中間位置的元素，可以通過(begin + end) / 2計算得出）

然后，比較這三個元素的大小，并選擇處于中間大小的元素作為樞軸元素。這樣做的目的是盡量避免選擇最小或最大的元素作為樞軸，因為這會產(chǎn)生不平衡的分區(qū)。這個選取樞軸的過程實際上是一個非常簡單的大小比較和交換操作

三數(shù)取中法選取key的具體實現(xiàn)可能如下：

int Getmidi(int* a, int begin, int end)
{
	int midi = (begin + end) / 2;
	if (a[begin] < a[midi])
	{
		if (a[midi] < a[end])
			return midi;
		else if (a[begin] > a[end])
			return begin;
		else
			return end;
	}
	else
	{
		if (a[midi] > a[end])
			return midi;
		else if (a[end] < a[begin])
			return end;
		else
			return begin;
	}
}
void Quicksort(int* a, int begin,int end)
{

	if (begin >= end)
	{
		return;
	}
	int midi = Getmidi(a, begin, end);
	Swap(&a[midi], &a[begin]);
	int left = begin;
	int right = end;
	int key = begin;
	while (left < right)
	{
		while (left<right && a[right]>=a[key])
		{
			right--;
		}
		while (left < right && a[left] <= a[key])
		{
			left++;
		}
		Swap(&a[right], &a[left]);
	}
	Swap(&a[left], &a[key]);
	key = left;
	Quicksort(a, begin, key - 1);
	Quicksort(a, key+1, end);
}

函數(shù)Getmidi嘗試從數(shù)組的begin、end和midi（中間）位置選取一個"中間值"（不是數(shù)值上的中位數(shù)，而是在三個數(shù)中大小排在中間的數(shù)）。然后，Quicksort1函數(shù)利用三數(shù)取中的方法來選擇樞軸元素(key)并執(zhí)行快速排序過程。

Getmidi 函數(shù)詳解：

Getmidi函數(shù)通過比較三個位置（起始位置、中間位置和結(jié)束位置）的元素大小來返回中間值的索引。這里的中間值是指這三個元素中不是最大也不是最小的那個。判斷條件覆蓋了所有可能的大小順序，來確保正確選取中間值。

Quicksort1 函數(shù)詳解：

  1. Quicksort1首先檢查遞歸調(diào)用的終止條件if (begin >= end)。當當前子數(shù)組長度為0或1時，函數(shù)返回

  2. 接下來，函數(shù)調(diào)用Getmidi來獲取中間值的索引并將該位置的元素與起始位置的元素交換，這樣樞軸（pivot）選取就是三數(shù)取中法選出的元素

  3. left和right分別初始化為子數(shù)組的起始和結(jié)束索引，此時始終將begin位置的元素視為樞軸元素

  4. 剩余部分執(zhí)行的是典型的快速排序分區(qū)操作，此時key是樞軸索引，最后將樞軸位置的元素放到正確位置上

  5. 在分區(qū)完成后，樞軸左側(cè)和右側(cè)的子數(shù)組通過遞歸調(diào)用Quicksort1函數(shù)來進行排序

在進行這些更改后，Quicksort1函數(shù)應該能夠正確地使用三數(shù)取中法對數(shù)組進行排序，通常能夠避免最壞情況的(O(n^2))時間復雜度，同時保持期望的平均時間復雜度(O(n log n))
【數(shù)據(jù)結(jié)構(gòu)與算法】：選擇排序與快速排序,數(shù)據(jù)結(jié)構(gòu)與算法,排序算法,算法,數(shù)據(jù)結(jié)構(gòu)

2.6挖坑法實現(xiàn)快排

挖坑法是實現(xiàn)快速排序的一種方法，它簡化了元素交換的步驟，通過"挖坑填數(shù)"來完成元素的位置調(diào)整。這個方法的基本思想是選定一個樞軸值（pivot），然后將小于樞軸值的元素移動到樞軸的左邊，將大于樞軸值的元素移動到樞軸的右邊，最終將樞軸值放入正確的位置。下面是使用挖坑法實現(xiàn)快速排序的示例代碼：

void QuickSortHole(int* arr, int begin, int end) {
	if (begin >= end) {
		return; // 遞歸結(jié)束條件
	}

	int key = arr[begin]; // 選取第一個元素作為樞軸
	int left = begin;
	int right = end;

	while (left < right) {
		// 從右向左找到第一個小于樞軸的元素，填入左邊的坑
		while (left < right && arr[right] >= key) {
			right--;
		}
		arr[left] = arr[right]; // 將找到的較小元素填到左邊的坑里，此時右邊形成一個新的坑

		while (left < right && arr[left] <= key) {
			left++;
		}
		arr[right] = arr[left]; 
	}

	
	arr[left] = key;
	QuickSortHole(arr, begin, left - 1);
	QuickSortHole(arr, left + 1, end);
}

先將第一個數(shù)據(jù)存放在臨時變量key中形成一個坑位

讓我們通過一個具體的例子來解釋挖坑法如何在快速排序中工作。假設(shè)我們有以下數(shù)組：

[6, 1, 2, 7, 9, 3, 4, 5, 10, 8]

我們要對這個數(shù)組進行快速排序。選擇第一個元素作為樞軸值（pivot），這里是6。我們現(xiàn)在開始挖坑法的過程：

  1. 初始化：樞軸值為6，因此數(shù)組的第一個位置成了一個“坑”，我們用這個“坑”來存放接下來找到的符合條件的元素。此時數(shù)組狀態(tài)和指針位置如下：

    [6*, 1, 2, 7, 9, 3, 4, 5, 10, 8]  // *表示坑位
left                            right

  2. 從右向左掃描：找到第一個小于6的元素，這里是5。我們將5放入左邊的“坑”中，并將5的位置變成新的“坑”。數(shù)組現(xiàn)在看起來是這樣：

    [5, 1, 2, 7, 9, 3, 4, 6*, 10, 8]  // 將5移動到左邊的坑位，6的位置成為新的坑位
     left                     right

  3. 從左向右掃描：找到第一個大于6的元素，這里是7。我們將7放入右邊的“坑”中，并將7的位置變成新的“坑”。數(shù)組更新為：

    [5, 1, 2, 6*, 9, 3, 4, 7, 10, 8]  // 將7移動到右邊的坑位，6的位置再次成為新的坑位
        left              right

  4. 重復這個過程，直到left和right指針相遇。在這個例子中，當兩個指針相遇時，我們發(fā)現(xiàn)它們都指向了索引3的位置（現(xiàn)在是一個“坑”），這個位置正是樞軸值6最終應該放置的位置。所以，我們把樞軸值放回這個“坑”里。數(shù)組現(xiàn)在是：

    [5, 1, 2, 6, 9, 3, 4, 7, 10, 8]

  5. 此時，樞軸值6已經(jīng)放到了它最終的位置上，所有在它左邊的元素都比它小，所有在它右邊的元素都比它大?，F(xiàn)在，我們對6左邊和右邊的子數(shù)組遞歸執(zhí)行相同的排序過程。

這種方法減少了元素的直接交換，通過移動“坑”位置來調(diào)整元素的位置

當然我們也可以繼續(xù)使用三數(shù)取中法選key對代碼再次優(yōu)化：

void QuickSortHole(int* arr, int begin, int end) {
	if (begin >= end) {
		return;
	}
	int midi = Getmidi(arr, begin, end);
	Swap(&arr[midi], &arr[begin]);

	int key = arr[begin]; 
	int left = begin;
	int right = end;

	while (left < right) {
		while (left < right && arr[right] >= key) {
			right--;
		}
		arr[left] = arr[right];

		while (left < right && arr[left] <= key) {
			left++;
		}
		arr[right] = arr[left];
	}

	arr[left] = key; 
	QuickSortHole(arr, begin, left - 1);
	QuickSortHole(arr, left + 1, end);
}

2.7前后指針實現(xiàn)快排

void QuickSort3(int* arr, int begin, int end) {
	if (begin >= end) {
			return;
	}
	int keyi = Getmidi(arr, begin, end);  
	Swap(&arr[keyi], &arr[begin]);

	int key = arr[begin];  
	int cur = begin + 1;     
	int pre = begin;        

	for (; cur <= end; ++cur) {
			if (arr[cur] < key) {
				++pre;  
				Swap(&arr[pre], &arr[cur]);
			}
	}

	Swap(&arr[begin], &arr[pre]);
	QuickSort3(arr, begin, pre - 1);
	QuickSort3(arr, pre + 1, end);
}

設(shè)置指針

  • 設(shè)置兩個指針cur（當前指針）和pre（前指針）。cur從樞軸元素的下一個位置開始，即begin + 1，而pre從樞軸元素的位置開始，即begin。這樣設(shè)置是為了準備遍歷數(shù)組進行分區(qū)。

遍歷與交換

  • 遍歷數(shù)組從cur到end的所有元素。對于每個元素，比較其與樞軸元素的大?。?
    • 如果當前cur指向的元素小于樞軸元素，則表示這個元素應該位于樞軸的左側(cè)。
    • 為了將其移動到正確位置，首先將pre指針向右移動一個位置（即++pre），然后交換pre和cur指向的元素的位置。這一步確保了pre左側(cè)的所有元素（包括pre指向的元素）都不大于樞軸元素。

樞軸歸位

  • 遍歷結(jié)束后，pre指向的是最后一個小于樞軸的元素的位置。由于初始時樞軸元素被置于數(shù)組的起始位置（即begin），現(xiàn)在需要將樞軸元素與pre指向的元素進行交換。
  • 這樣做的結(jié)果是，樞軸元素被放置到了其最終的正確位置上。至此，樞軸元素的左側(cè)都是不大于它的元素，右側(cè)都是不小于它的元素。

讓我們通過一個具體的例子來演示快速排序的分區(qū)過程，假設(shè)我們有以下數(shù)組：

arr = [3, 6, 8, 10, 1, 2, 1]

我們選擇數(shù)組的第一個元素作為樞軸（pivot），即3。

  1. 樞軸選擇
    這一步已經(jīng)完成，樞軸3已經(jīng)在數(shù)組的起始位置。

  2. 設(shè)置指針
    設(shè)置兩個指針cur和pre。初始時，cur = begin + 1 = 1，pre = begin = 0。

  3. 遍歷與交換
    我們開始遍歷數(shù)組，從索引1到數(shù)組的結(jié)束，比較每個元素與樞軸3的大小。

  • cur = 1, arr[cur] = 6，因為6 > 3，pre和cur都不動。
  • cur = 2, arr[cur] = 8，因為8 > 3，pre和cur都不動。
  • cur = 3, arr[cur] = 10，同樣，10 > 3，pre和cur都不動。
  • cur = 4, arr[cur] = 1，因為1 < 3，此時pre向右移動一位變?yōu)?code>1，然后交換arr[pre]和arr[cur]，即6和1交換位置?，F(xiàn)在數(shù)組變?yōu)?code>[3, 1, 8, 10, 6, 2, 1]。
  • cur = 5, arr[cur] = 2，因為2 < 3，pre再次向右移動一位變?yōu)?code>2，然后交換arr[pre]和arr[cur]，即8和2交換。數(shù)組變?yōu)?code>[3, 1, 2, 10, 6, 8, 1]。
  • cur = 6, arr[cur] = 1，同樣，1 < 3，pre移動到3，然后10和1交換。數(shù)組現(xiàn)在看起來是[3, 1, 2, 1, 6, 8, 10]。

  1. 樞軸歸位
    遍歷完成后，pre = 3，指向最后一個小于3的元素?，F(xiàn)在，我們將樞軸元素3與pre所在位置的元素1交換。交換后的數(shù)組是[1, 1, 2, 3, 6, 8, 10]。

  2. 遞歸分區(qū)
    現(xiàn)在，樞軸3已經(jīng)處于其正確的位置，我們對樞軸左側(cè)的[1, 1, 2]和右側(cè)的[6, 8, 10]分別遞歸執(zhí)行上述步驟，直到子數(shù)組長度為1或者為空，這意味著整個數(shù)組已經(jīng)排序完成。

本節(jié)內(nèi)容到此結(jié)束，感謝大家閱讀?。?！文章來源地址http://www.zghlxwxcb.cn/news/detail-840947.html

到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)與算法】：選擇排序與快速排序的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！

本文來自互聯(lián)網(wǎng)用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權(quán)，不承擔相關(guān)法律責任。如若轉(zhuǎn)載，請注明出處： 如若內(nèi)容造成侵權(quán)/違法違規(guī)/事實不符，請點擊違法舉報進行投訴反饋，一經(jīng)查實，立即刪除！

領(lǐng)支付寶紅包贊助服務器費用

相關(guān)文章

覺得文章有用就打賞一下文章作者

支付寶掃一掃打賞

博客贊助

微信掃一掃打賞

請作者喝杯咖啡吧~博客贊助

支付寶掃一掃領(lǐng)取紅包，優(yōu)惠每天領(lǐng)

二維碼1

領(lǐng)取紅包

二維碼2

領(lǐng)紅包