基礎資料結構——簡單選擇排序和堆排序——筆記自用

選擇排序和堆排序

• 選擇排序
• • 原理
  • 圖示
  • C語言代碼
  • 評價
• 堆排序
• • 堆的概念
  • 原理
  • • 疑問
    • 為什麼要調成大頂堆？
    • 怎樣調節成大頂堆？
    • 步驟一： 調節成大頂堆
    • 二：将最後一個結點的值和根節點的值交換
    • 三：再次調整為大頂堆
    • 四：重複二三步驟，直至完全有序
  • C語言代碼
  • 評價

選擇排序

原理

選擇排序：每次從待排序序列中找到最小值和待排序序列的第一個值交換。

圖示

(紅線右邊為待排序序列)

C語言代碼

注意：

在每次交換的時候，儲存的是最小值的下标。

void SelectSort(int* arr, int len)
{
	assert(arr != NULL);

	int minindex = 0; //1

	for (int i = 0; i < len - 1; i++) //2
	{
		minindex = i; //3
		
		for (int j = i + 1; j < len; j++) //4
		{
			if (arr[j] < arr[minindex]) //5
			{
				minindex = j;
			}
		}
		//6

		//進行交換
		if (i != minindex)
		{
			int tmp = arr[i]; //7
			arr[i] = arr[minindex];
			arr[minindex] = tmp;
		}
	}
}
           

1. minindex 儲存的是最小值的下标
2. 趟數 總數少一趟
3. 每趟循環一進來 ，待排序序列的第一個值是最小值 是以minindex先指派為i
4. 從待排序序列的第二個值開始和arr[minindex]比較
5. 如果找到更小的數 則minindex重新指派為新的最小值的下标
6. 此時for循環執行結束 代表着minindex儲存的就是最小值的下标
7. 因為i儲存的是待排序序列第一個值

評價

每一次将待排序序列中最小值和待排序序列中第一個值進行交換，直到完全有序即可。

• 時間複雜度：O(n^2)
• 空間複雜度：O(1)
• 穩定性：不穩定(存在跳躍交換)

堆排序

堆的概念

什麼是堆？

以完全二叉樹的結構來管理的一維數組。

什麼是大頂堆？

父節點的值大于子節點

什麼是小頂堆？

父節點的值小于子節點

原理

把一維數組臆想成完全二叉樹

示例：

如何通過父節點的下标推出子節點的下标？

如圖:紅色為下标

左孩子下标 ： 2 * i + 1;

右孩子下标 ： 2 * i + 2

子節點怎麼推出父節點？

父節點：(i - 1) / 2

疑問

為什麼要調成大頂堆？

因為每次調整之後根節點的值就是最大值，将其放到最後，實作從小到大排序。若需要從大到小排序，将其調整為小頂堆。

怎樣調節成大頂堆？

1. 從最後一個非葉子結點從後向前開始調整。
2. 從上向下開始調整。

1圖示：

最後一個非葉子結點為紅圈所示

将其調整為：

在調整前一個非葉子結點：

調整為：

步驟一： 調節成大頂堆

這樣依次調整，最後調整為大頂堆：

二：将最後一個結點的值和根節點的值交換

并且交換後的尾部節點不參與下一次調整，因為它是最大值，已經找到自己的位置。

三：再次調整為大頂堆

根據上一步驟可以得出：不需要再從最後一個非葉子結點進行調整，隻需要以根節點為基準調整一次。

四：重複二三步驟，直至完全有序

C語言代碼

void HeapAdjust(int* arr, int start, int end)
{
	int tmp = arr[start];

	for (int i = start * 2 + 1; i <= end; i = start * 2 + 1)//語句3是 時間複雜度O（nlogn）的原因
	{
		if (i < end && arr[i] < arr[i + 1])//有右孩子 并且右孩子比左孩子大 
		{
			i++;
		}
		//如果if為假   代表要麼右孩子不存在  要麼右孩子存在 但是小于左孩子
		//此時 i儲存的是左右孩子中較大的值的下标
		//接着讓父子比較

		if (arr[i] > tmp)
		{
			arr[start] = arr[i];
			start = i;
		}
		else
		{
			break;
		}
	}
	//此時for循環推出了，要麼此時觸底  要莫if(arr[i]>tmp)為假  break跳出循環
	arr[start] = tmp;
}

void HeapSort(int* arr, int len)
{
	//1.先調整成大頂堆  從最後一個非葉子節點開始
	for (int i = (len - 1 - 1) / 2; i >= 0; i--)//O（n）
	{
		HeapAdjust(arr, i, len - 1);//（logn）    
	}//   則時間複雜度O（nlogn）

	//根節點和尾節點交換
	for (int i = 0; i < len - 1; i++)//O（n）
	{
		int tmp = arr[0];
		arr[0] = arr[len - 1 - i];//9 8 7 6 5 4 3 2 1
		arr[len - 1 - i] = tmp;

		HeapAdjust(arr, 0, (len - 1 - i) - 1);//(len-1-i)相當于最後一個節點的下标  然後最後一個節點不參與計算 則再-1
	}
}
           

評價

• 時間複雜度：O(n log2n)
• 空間複雜度：O(1)
• 穩定性：不穩定（存在跳躍交換）