資料結構和演算法之排序總結-有解無憂

文章目錄

- - 一、排序的概念及應用
  - - 💦 排序的概念
    - 💦 排序的運用
    - 💦 常見的排序演算法
  - 二、常見排序演算法的實作
  - - 💦 插入排序
    - - 1、直接插入排序
      - 2、希爾排序
    - 💦 選擇排序
    - - 1、直接選擇排序
      - 2、堆排序
    - 💦 交換排序
    - - 1、冒泡排序
      - 2、快速排序
    - 💦 歸并排序
    - 💦 非比較排序
    - - 1、計數排序
      - 2、基數排序
    - 💦 檔案排序 (拓展)
    - 💦 性能測驗
  - 三、排序演算法復雜度及穩定性分析
  - 四、概念選擇題

一、排序的概念及應用

💦 排序的概念

排序：所謂排序，就是使一串記錄，按照其中的某個或某些關鍵字的大小，遞增或遞減的排列起來的操作，

穩定性：假定在待排序的記錄序列中，存在多個具有相同的關鍵字的記錄，若經過排序，這些記錄的相對次
序保持不變，即在原序列中，r[i]=r[j]，且 r[i] 在 r[j] 之前，而在排序后的序列中，r[i] 仍在 r[j] 之前，則稱這種排
序演算法是穩定的；否則稱為不穩定的，

內部排序：資料元素全部放在記憶體中的排序，

外部排序：資料元素太多不能同時放在記憶體中，根據排序程序的要求不能在內外存之間移動資料的排序，

資料結構和演算法動態可視化

💦 排序的運用

? 現實中排序的運用非常廣泛，無處不在 ?

好一個凡爾賽
在這里插入圖片描述

💦 常見的排序演算法

在這里插入圖片描述

二、常見排序演算法的實作

// 排序實作的介面
 
// 插入排序 void InsertSort(int* a, int n);
 
// 希爾排序
void ShellSort(int* a, int n);
 
// 選擇排序 
void SelectSort(int* a, int n);

// 堆排序 
void AdjustDwon(int* a, int n, int root); 
void HeapSort(int* a, int n);
 
// 冒泡排序 
void BubbleSort(int* a, int n)

// 快速排序遞回實作 
// 快速排序hoare版本 
int PartSort1(int* a, int left, int right); 
// 快速排序挖坑法 
int PartSort2(int* a, int left, int right); 
// 快速排序前后指標法 
int PartSort3(int* a, int left, int right); 
void QuickSort(int* a, int left, int right);

// 快速排序 非遞回實作 
void QuickSortNonR(int* a, int left, int right)

// 歸并排序遞回實作 
void MergeSort(int* a, int n) 

// 歸并排序非遞回實作
void MergeSortNonR(int* a, int n)
 
// 計數排序 void CountSort(int* a, int n);
}

💦 插入排序

1、直接插入排序

🔑 核心思想 🔑

??把待排序的記錄按關鍵碼的大小逐個插入到一個已經排好的序的有序序列中，直到所有的記錄插入完為止，得到一個新的有序序列

實際中我們玩撲克牌時，就用了插入排序的思想

在這里插入圖片描述
? 程序：?

當插入第 i(i>=1) 個元素時，前面的 array[0]， array[1]， … ， array[i-1] 已經排好序，此時用 array[i] 的排序碼與 array[i-1]， array[i-2]，… 的排序碼順序進行比較，找到插入位置即將 array[i] 插入，原來位置上的元素順序后移

? 直接插入排序的特性總結：?

??1?? 元素集合越接近有序，直接插入排序演算法的時間效率越高

??2?? 時間復雜度：O(N^2)

??3?? 空間復雜度：O(1)，它是一種穩定的排序演算法

??4?? 穩定性：穩定

? 動圖演示：?

請添加圖片描述
🧿 實作代碼：

void InserSort(int* a, int n)
{
	//多趟控制
	int i = 0;
	for (i = 0; i < n - 1; i++)
	{
		//單趟控制
		int end = i ;
		int temp = a[end + 1];
		while (end >= 0)
		{
			//目標數小于其它數時，其它數就往后挪；大于則插入
			if (temp < a[end])
			{
				a[end + 1] = a[end];
				end--;
			}
			else
			{
				break;
			}
		}
		a[end + 1] = temp;
	}
}

? 插入排序的時間復雜度 ?

??最壞的情況 - 逆序：O(N²)

??最好的情況 - 接近有序：O(N)

2、希爾排序

希爾排序 (縮小增量排序)

🔑 核心思想 🔑

??希爾排序法又稱縮小增量法，希爾排序法的基本思想是：先選定一個整數，把待排序檔案中所有記錄分成若干個組，所有距離為 gap 的記錄分在同一組內，并對每一組內的記錄進行排序，然后，取，重復上述分組和排序的工## 標題作，當到達 = 1 時，所有記錄在統一組內排好序，

??人話就是：

????1?? 預排序 (接近升序) - gap > 1

????2?? 直接插入排序 - gap == 1

在這里插入圖片描述
? 希爾排序特性總結 ?

??1?? 希爾排序是對直接插入排序的優化

??2?? 當 gap > 1 時都是預排序，目的是讓陣列更接近于有序，當 gap == 1 時，其實就是直接插入排序，且陣列已經接近有序的了，整體而言，可以達到優化的效果，我們實作后可以進行性能測驗的對比

??3?? 希爾排序的時間復雜度并不好計算，因為 gap 的取值方法很多，導致很難去計算，因此在好些數中給出的希爾排序的時間復雜度都不固定，官方給出的時間復雜度是 O(N^1.3)

??4?? 穩定性：不穩定

👁?🗨 知識擴展
在這里插入圖片描述
🧿 實作代碼：

代碼的核心并不是一組一組的排，而是多組并排

以下只是預排序代碼，還需要再呼叫 InsertSort 進行直接插入排序

void ShellSort(int* a, int n)
{
	int i = 0;
	int gap = 3;
	//多組并排
	for (i = 0; i < n - gap; i++)
	{
		int end = i;
		int temp = a[end + gap];
		while (end >= 0)
		{
			if (temp < a[end])
			{
				a[end + gap] = a[end];
				end -= gap;
			}
			else
			{
				break;
			}
		}
		a[end + gap] = temp;
	}
}

? 對于 gap 的值寫成固定的并不好 ?

??這里只是建議

void ShellSortPro(int* a, int n)
{
	//gap > 1 預排序
	//gap == 1 直接插入排序
	int i = 0;
	//gap的初始值為n
	int gap = n;
	while (gap > 1)
	{
		//每次回圈gap都在減少，直到gap變成1
		gap = gap / 3 + 1;
		//gap /= 2;
		
		for (i = 0; i < n - gap; i++)
		{
			int end = i;
			int temp = a[end + gap];
			while (end >= 0)
			{
				if (temp < a[end])
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			a[end + gap] = temp;
		}
	}
}

💦 選擇排序

1、直接選擇排序

🔑 核心思想 🔑

??每一次從待排序的資料元素中選出最小（或最大）的一個元素，存放在序列的起始位置，直到全部待排序的資料元素排完，

? 程序：?

??1?? 在元素集合 array[i] - array[n-1] 中選擇關鍵碼最大 (小) 的資料元素

??2?? 若它不是這組元素中的最后一個(第一個)元素，則將它與這組元素中的最后一個（第一個）元素交換

??3?? 在剩余的 array[i] - array[n-2] (array[i+1]–array[n-1]) 集合中，重復上述步驟，直到集合剩余 1 個元素

? 直接選擇排序的特性總結：?

??1?? 直接選擇排序思考非常好理解，但是效率不是很好，實際中很少使用

??2?? 時間復雜度：O(N^2) - 最好 / 最壞

??3?? 空間復雜度：O(1)

??4?? 穩定性：不穩定

? 動圖演示：?

請添加圖片描述
🧿 實作代碼：

void Swap(int* px, int* py)
{
	int temp = *px;
	*px = *py;
	*py = temp;
}
void SelectSort(int* a, int n)
{
	int i = 0;
	int begin = 0;
	while (begin < n)
	{
		int mini = begin;
		//選最小
		for (i = begin; i < n; i++)
		{
			if (a[i] < a[mini])
			{
				mini = i;
			}
		}
		//交換
		Swap(&a[begin], &a[mini]);
		//迭代
		begin++;
	}
}

🧿 實作 SelectSort 的優化代碼：

?? 遍厲一遍選出最小的和最大的，然后把最小的放在左邊，最大的放在右邊

void Swap(int* px, int* py)
{
	int temp = *px;
	*px = *py;
	*py = temp;
}
void SelectSortPro(int* a, int n)
{
	int i = 0;
	int begin = 0, end = n - 1;
	while (begin < end)
	{
		//選最大和最小
		int mini = begin, maxi = begin;
		for (i = begin; i <= end; i++)
		{
			if (a[i] > a[maxi])
			{
				maxi = i;
			}
			if (a[i] < a[mini])
			{
				mini = i;
			}
		}
		//交換
		Swap(&a[begin], &a[mini]);
		//當a陣列里第1個元素是最大值時，此時經過上面的Swap，最大值的位置已經更改了，所以需要修正最大值的位置，讓下一個Swap正確交換
		if (begin == maxi)
		{
			maxi = mini;
		}
		Swap(&a[end], &a[maxi]);
		//迭代
		++begin;
		--end;
	}
}

2、堆排序

🔑 核心思想 🔑

??堆排序 (Heapsort) 是指利用堆積樹 (堆) 這種資料結構所設計的一種排序演算法，它是選擇排序的一種，它是通過堆來進行選擇資料，需要注意的是排升序要建大堆，排降序建小堆，
??關于堆排序詳解請轉到 ? 僅不到五萬字輕松了解二叉樹和堆

? 堆排序的特性總結：?

??1?? 堆排序使用堆來選數，效率就高了很多，

??2?? 時間復雜度：O(N*logN)

??3?? 空間復雜度：O(1)

??4?? 穩定性：不穩定

? 動圖演示：?

請添加圖片描述

🧿 實作代碼：

void Swap(int* px, int* py)
{
	int temp = *px;
	*px = *py;
	*py = temp;
}
void AdjustDown(int* a, int n, int parent)
{
	int child = parent * 2 + 1;
	while (child < n)
	{
		if (a[child] < a[child + 1] && child + 1 < n)
		{  
			child++;
		}
		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
void HeapSort(int* a, int n)
{
	//建大堆
	int i = 0;
	for (i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(a, n, i);
	}
	int end = n - 1;
	//交換并調整
	while (end > 0)
	{
		Swap(&a[0], &a[end]);
		AdjustDown(a, end, 0);
		end--;
	}
}

💦 交換排序

1、冒泡排序

🔑 核心思想 🔑

??所謂交換，就是根據序列中兩個記錄鍵值的比較結果來對換這兩個記錄在序列中的位置，交換排序的特點是：將鍵值較大的記錄向序列的尾部移動，鍵值較小的記錄向序列的前部移動，

? 冒泡排序的特性總結：?

??1?? 冒泡排序是一種非常容易理解的排序

??2?? 時間復雜度：O(N^2)

??3?? 空間復雜度：O(1)

??4?? 穩定性：穩定

? 動圖演示：?

請添加圖片描述
🧿 實作代碼：

void Swap(int* px, int* py)
{
	int temp = *px;
	*px = *py;
	*py = temp;
}
void BubbleSort(int* a, int n)
{
	int i = 0;
	int j = 0;
	for (i = 0; i < n - 1; i++)
	{
		for (j = 0; j < n - 1 - i; j++)
		{
			if (a[j] > a[j + 1])
			{
				Swap(&a[j], &a[j + 1]);
			}
		}
	}
}

🧿 實作代碼 BubbleSort 的優化版本：

?? 當遍厲一遍后發現沒有 Swap 時，那么說陣列就是有序的

?? 時間復雜度：最壞 O(N²)

???????? 最好 O(N)

void Swap(int* px, int* py)
{
	int temp = *px;
	*px = *py;
	*py = temp;
}
void BubbleSortPro(int* a, int n)
{
	int i = 0;
	int j = 0;
	for (i = 0; i < n - 1; i++)
	{
		int flag = 1;
		for (j = 0; j < n - 1 - i; j++)
		{
			if (a[j] > a[j + 1])
			{
				flag = 0;
				Swap(&a[j], &a[j + 1]);
			}
		}
		//如果flag等于1說明此時陣列是升序
		if (flag == 1)
			break;
	}
}

2、快速排序

🔑 核心思想 🔑

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

? 程序：?

在這里插入圖片描述
??1?? 選出一個關鍵字 key，一般是頭或者尾

??2?? 經過一次單趟后，key 放到了正確的位置，key 左邊的值比 key 小，key 右邊的值比 key 大

??3?? 再讓 key 的左邊區間有序、key 的右邊區間有序

? 動圖演示：?

?一、首次單趟 (注意這三種方法首次單趟后不一定相同)

???💨 hoare 版本

請添加圖片描述
?? 如何保證相遇位置的值小于 key ?

???💨 挖坑版本
請添加圖片描述

???💨 前后指標法

請添加圖片描述

?二、非首次單趟

在這里插入圖片描述

🧿 實作代碼：首次 + 非首次 + 遞回版本

void Swap(int* px, int* py)
{
	int temp = *px;
	*px = *py;
	*py = temp;
}
void PartSortHoare(int* a, int left, int right)
{
	int keyi = left;
	while(left < right)
	{
		//左邊作key，右邊先走找小
		while(a[right] >= a[keyi] && left < right)
		{
			right--;
		}
		//右邊找到小，再找左邊的大
		while(a[left] <= a[keyi] && left < right)
		{
			left++;
		}
		//交換小大
		Swap(&a[right], &a[left]);
	}
	//交換key
	Swap(&a[keyi], &a[right]);
	//回傳分割大小的那個下標
	return left;
}
int PartSortHole(int* a, int left, int right)
{
	int key = a[left];
	int hole = left;
	while (left < right)
	{
		//右邊找小，填左坑
		while (left < right && a[right] >= key)
		{
			right--;
		}
		a[hole] = a[right];//填坑
		hole = right;//新的坑

		//左邊找大，填右坑
		while (left < right && a[left] <= key)
		{
			left++;
		}
		a[hole] = a[left];//填坑
		hole = left;//新的坑
	}

	//將key填最后一個坑
	a[hole] = key;
	return hole;
}
int PartSortPoint(int* a, int left, int right)
{
	int keyi = left;
	int prev = left;
	int cur = prev + 1;
	while (cur <= right)
	{
		//cur比keyi大時，prev不會++；且排除了自己交換自己
		if (a[cur] < a[keyi] && ++prev != cur)
		{
			Swap(&a[prev], &a[cur]);	
		}
		//兩種情況cur都要++
		cur++;
	}
	//交換keyi
	Swap(&a[keyi], &a[prev]);
	return prev;
}
void QuickSort(int* a, int left, int right)
{
	//遞回的結束條件
	if (left >= right)
	{
		return ;
	}
	//keyi拿到分割大小的下標 - [left, keyi - 1]; [keyi]; [keyi + 1, right]
	//int keyi = PartSortHoare(a, left, right);//版本1
	//int keyi = PartSortHole(a, left, right);//版本2
	int keyi = PartSortPoint(a, left, right);//版本3
	
	//遞回左
	QuickSort(a, left, keyi - 1);
	//遞回右
	QuickSort(a, keyi + 1, right);
}

? QuickSort 的時間復雜度 ?

在這里插入圖片描述
🧿 實作 QuickSort 的優化代碼 —— 優化有序的情況

??三數取中選 key —— left、mid、right 中不是最大也不是最小的數

//三數取中
int GetMidIndex(int* a, int left, int right)
{
	//int mid = (left + right) / 2;
	int mid = left + (right - left) / 2;//防止溢位版本
	if (a[left] < a[mid])
	{
		if (a[mid] < a[right])
		{
			return mid;
		}
		else if (a[left] < a[right])
		{
			return right;
		}
		else
		{
			return left;
		}
	}
	else //a[left] > a[mid]
	{
		if (a[mid] > a[right])
		{
			return mid;
		}
		else if(a[left] < a[right])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
}
int PartSortHoarePro(int* a, int left, int right)
{
	int midi = GetMidIndex(a, left, right);
	Swap(&a[left], &a[midi]);
	int keyi = left;
	while (left < right)
	{
		while (a[right] >= a[keyi] && left < right)
		{
			right--;
		}
		while (a[left] <= a[keyi] && left < right)
		{  
			left++;
		}
		Swap(&a[right], &a[left]);
	}
	Swap(&a[keyi], &a[right]);

	return left;
}
int PartSortHolePro(int* a, int left, int right)
{
	int midi = GetMidIndex(a, left, right);
	Swap(&a[left], &a[midi]);
	int key = a[left];
	int hole = left;
	while (left < right)
	{
		//右邊找小，填左坑
		while (left < right && a[right] >= key)
		{
			right--;
		}
		a[hole] = a[right];//填坑
		hole = right;//新的坑

		//左邊找大，填右坑
		while (left < right && a[left] <= key)
		{
			left++;
		}
		a[hole] = a[left];//填坑
		hole = left;//新的坑
	}

	//將key填最后一個坑
	a[hole] = key;
	return hole;
}
int PartSortPointPro(int* a, int left, int right)
{
	int midi = GetMidIndex(a, left, right);
	Swap(&a[left], &a[midi]);
	int keyi = left;
	int prev = left;
	int cur = prev + 1;
	while (cur <= right)
	{
		//cur比keyi大時，prev不會++；且排除了自己交換自己
		if (a[cur] < a[keyi] && ++prev != cur)
		{
			Swap(&a[prev], &a[cur]);
		}
		//兩種情況cur都要++
		cur++;
	}
	//交換keyi
	Swap(&a[keyi], &a[prev]);
	return prev;
}
void QuickSortPro(int* a, int left, int right)
{
	if (left >= right)
	{
		return;
	}
	//int keyi = PartSortHoarePro(a, left, right);//版本1
	//int keyi = PartSortHolePro(a, left, right);//版本2
	int keyi = PartSortPointPro(a, left, right);//版本3

	QuickSortPro(a, left, keyi - 1);
	QuickSortPro(a, keyi + 1, right);
}

? QuickSortHoarePro 的時間復雜度 ?

??這里就不會出現最壞的情況 —— 有序，因為有了三數取中演算法，

?
🧿 實作代碼：首次 + 非首次 + 非遞回版本

??任何一個遞回代碼，要改成非遞回

???1、回圈

???2、堆疊 (資料結構) 模擬

??顯然這里的快排不好直接改成回圈，還要借助堆疊，所以這里復用了之前 C 實作的堆疊，詳解請轉 ? 爆肝兩萬字，我爺爺都看的懂的《堆疊和佇列》，建議各位觀眾姥爺先收藏

🔑 核心思想 🔑
在這里插入圖片描述

void QuickSortNonR(int* a, int left, int right)
{
	ST st;
	StackInit(&st);
	//先入第一組區間
	StackPush(&st, right);
	StackPush(&st, left);
	//堆疊不為空
	while (!StackEmpty(&st))
	{
		//取堆疊頂left，并Pop
		int begin = StackTop(&st);
		StackPop(&st);

		//再取堆疊頂right，并Pop
		int end = StackTop(&st);
		StackPop(&st);

		//這里就用前后指標版本進行單趟排
		int keyi = PartSortPointPro(a, begin, end);
		
		//再入區間 [left, keyi - 1]; [keyi]; [keyi + 1, end]
			//右區間 —— 只有1個值不會入
		if (keyi + 1 < end)
		{
			StackPush(&st, end);
			StackPush(&st, keyi + 1);
		}
			//左區間 —— 只有1個值不會入
		if (begin < keyi - 1)
		{
			StackPush(&st, keyi - 1);
			StackPush(&st, begin);
		}
	}
	StackDestory(&st);
}

? 快速排序的特性總結：?

??1?? 快速排序整體的綜合性能和使用場景都是比較好的，所以才敢叫快速排序

??2?? 時間復雜度：O(N*logN)

??3?? 空間復雜度：O(logN)

??4?? 穩定性：不穩定

💦 歸并排序

🔑 核心思想 🔑

??歸并排序 (MERGE-SORT) 是建立在歸并操作上的一種有效的排序演算法，該演算法是采用分治法 (Divide and Conquer) 的一個非常典型的應用，將已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列有序，若將兩個有序表合并成一個有序表，稱為二路歸并，

??歸并排序核心步驟：
在這里插入圖片描述

? 動圖演示：?

請添加圖片描述
🧿 實作代碼 —— 遞回版：

void _MergeSort(int* a, int left, int right, int* temp)
{
	//只有一個值
	if (left >= right)
		return;

	//[left, mid][mid+1, right]
	int mid = (right + left) / 2;

	//遞回
	_MergeSort(a, left, mid, temp);
	_MergeSort(a, mid + 1, right, temp);

	//歸并到temp
	int begin1 = left, end1 = mid;
	int begin2 = mid + 1, end2 = right;
	
		//&&其中一段區間結束就結束了
	int index = left;
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (a[begin1] < a[begin2])
		{
			temp[index++] = a[begin1++];
		}
		else
		{
			temp[index++] = a[begin2++];
		}
	}
		//begin2結束了，拷貝剩下的begin1
	while (begin1 <= end1)
	{
		temp[index++] = a[begin1++];
	}
		//begin1結束了，拷貝剩下的begin2
	while (begin2 <= end2)
	{
		temp[index++] = a[begin2++];
	}
		//歸并后的結果，拷貝至原陣列
	int i = 0;
	for (i = left; i <= right; i++)
	{
		a[i] = temp[i];
	}
}
void MergeSort(int* a, int n)
{
	//臨時陣列 
	int* temp = (int*)malloc(sizeof(int) * n);
	//子函式遞回
	_MergeSort(a, 0, n - 1, temp);
	//釋放臨時陣列
	free(temp);
}

🧿 實作代碼 —— 非遞回版：

🔑 核心思想 🔑
在這里插入圖片描述

void MergeSortNonR(int* a, int n)
{
	//臨時陣列 
	int* temp = (int*)malloc(sizeof(int) * n);
	int groupNum = 1;
	int i = 0; 
	while (groupNum < n)
	{
		for (i = 0; i < n; i += 2 * groupNum)
		{
			//[begin1, end1][begin2, end2]
			int begin1 = i, end1 = i + groupNum - 1;
			int begin2 = i + groupNum, end2 = i + groupNum * 2 - 1;
			//歸并
			int index = begin1;
			//陣列的資料個數，并不一定是按整數倍，所以分組可能越界或不存在
				//1.[begin2,end2]不存在或越界，修正為一個不存在的區間
			if (begin2 >= n)
			{
				begin2 = n + 1;
				end2 = n;
			}
				//2.end1越界，修正后歸并
			if (end1 >= n)
			{
				end1 = n - 1;
			}
				//3.end2越界，修正后歸并
			if (end2 >= n)
			{
				end2 = n - 1;
			}
			while (begin1 <= end1 && begin2 <= end2)
			{
				if (a[begin1] < a[begin2])
				{
					temp[index++] = a[begin1++];
				}
				else
				{
					temp[index++] = a[begin2++];
				}
			}
			//begin2結束了，拷貝剩下的begin1
			while (begin1 <= end1)
			{
				temp[index++] = a[begin1++];
			}
			//begin1結束了，拷貝剩下的begin2
			while (begin2 <= end2)
			{
				temp[index++] = a[begin2++];
			}
		}
		//拷貝回原陣列
		for (i = 0; i < n; i++)
		{
			a[i] = temp[i];
		}
		//迭代
		groupNum *= 2;

		//輸出每層
		//PrintArray(a, n);

	}
	//釋放臨時陣列
	free(temp);
}

? 歸并排序的特性總結：?

??1?? 歸并的缺點在于需要O(N)的空間復雜度，歸并排序的思考更多的是解決在磁盤中的外排序問題

??2?? 時間復雜度：O(N*logN)

??3?? 空間復雜度：O(N)

??4?? 穩定性：穩定

💦 非比較排序

1、計數排序

🔑 核心思想 🔑

??計數排序又稱為鴿巢原理，是對哈希直接定址法的變形應用，

??計數排序核心步驟：

???1?? 統計相同元素出現次數

???2?? 根據統計的結果將序列回收到原來的序列中

在這里插入圖片描述

? 動圖演示：?
請添加圖片描述
🧿 實作代碼：

void CountSort(int* a, int n)
{
	//遍厲一遍找出最小值和最大值
	int min = a[0], max = a[0];
	int i = 0;
	for (i = 1; i < n; i++)
	{
		if (a[i] < min)
		{
			min = a[i];
		}
		if (a[i] > max)
		{
			max = a[i];
		}
	}
	//求出這個區間 
	int range = max - min + 1;
	//calloc空間，并初始化為0 
	int* count = (int*)calloc(range, sizeof(int));
	//統計  
	for (i = 0; i < n; i++)
	{
		//相對位置
		count[a[i] - min]++;
	}
	//根據count陣列排序
	i = 0; 
	int j = 0; 
	for (j = 0; j < range; j++)
	{
		while (count[j]--)  
		{
			a[i++] = j + min;
		}
	}
	free(count);
}

? 計數排序的特性總結：?

??1?? 計數排序在資料范圍集中時，效率很高，但是適用范圍及場景有限

??2?? 時間復雜度：O(MAX(N,范圍))

??3?? 空間復雜度：O(范圍)

??4?? 穩定性：穩定

??5?? 只適合整數排序，浮點數/字串不能排

2、基數排序

🔑 核心思想 🔑

??基數排序又稱桶排序，它分別按資料的個、十、百、千、萬 … 排序，當然也可以先萬、千、…

? 動圖演示：?

請添加圖片描述

? 這里就不實作了，為什么 ?

??因為這種排序實際在校招中和現實中已經很少使用了，各位碼友有興趣的也可以自己了解下

💦 檔案排序 (拓展)

? 注意

??小檔案排序是沒有意義的，當然我們這里只是模擬，所以給 100 個資料
在這里插入圖片描述

🔑 核心思想 🔑

??磁盤的讀取速度相比記憶體差距非常大，所以我們不可能像在記憶體中兩兩歸并，正確的歸并方法是大檔案平均分割成 N 份，保證每份大小都可以加載到記憶體，那么就可以把每個小檔案加載到記憶體中，使用快排排序，再寫回小檔案，這時就達到檔案中歸并的先決條件

在這里插入圖片描述

🧿 實作代碼：

void _MergeFile(const char* File1, const char* File2, const char* mFile)
{
	//讀檔案1
	FILE* fout1 = fopen(File1, "r");
	if (fout1 == NULL)
	{
		printf("打開檔案失敗\n");
		exit(-1);
	}
	//讀檔案2
	FILE* fout2 = fopen(File2, "r");
	if (fout2 == NULL)
	{
		printf("打開檔案失敗\n");
		exit(-1);
	}
	//寫檔案3,把檔案1和檔案2寫到檔案3里
	FILE* fin = fopen(mFile, "w");
	if (fin == NULL)
	{
		printf("打開檔案失敗\n");
		exit(-1);
	}
	int num1, num2;
	//對于記憶體中沒有問題，但是磁盤就有問題了，不管num1和num2誰小誰大，只要讀了fout1和fout2它們都會往后走
	/*while (fscanf(fout1, "%d\n", &num1) != EOF 
		&& fscanf(fout2, "%d\n", &num2) != EOF)
	{
		if (num1 < num2)
			fprintf(fin, "%d\n", num1);
		else
			fprintf(fin, "%d\n", num2);
	}*/
	int ret1 = fscanf(fout1, "%d\n", &num1);
	int ret2 = fscanf(fout2, "%d\n", &num2);
	//下面保證了誰讀誰走；fout1和fout2都不為空再比較
	while (ret1 != EOF && ret2 != EOF)
	{
		if (num1 < num2)
		{
			fprintf(fin, "%d\n", num1);
			ret1 = fscanf(fout1, "%d\n", &num1);//更新字符
		}
		else
		{
			fprintf(fin, "%d\n", num2);
			ret2 = fscanf(fout2, "%d\n", &num2); //更新字符
		}
	}
	/*注意這樣會導致少寫一個資料
		//fout2完了，寫剩下的fout1
	while (fscanf(fout1, "%d\n", &num1) != EOF)
	{
		fprintf(fin, "%d\n", num1);
	}
		//fout1完了，寫剩下的fout2
	while (fscanf(fout2, "%d\n", &num2) != EOF)
	{
		fprintf(fin, "%d\n", num2);
	}*/

	//fout2完了，寫剩下的fout1
	while (ret1 != EOF)
	{
		fprintf(fin, "%d\n", num1);
		ret1 = fscanf(fout1, "%d\n", &num1);//更新字符
	}
	//fout1完了，寫剩下的fout2
	while (ret2 != EOF)
	{
		fprintf(fin, "%d\n", num2);
		ret2 = fscanf(fout2, "%d\n", &num2); //更新字符
	}
	//關閉檔案 
	fclose(fout1);
	fclose(fout2);
	fclose(fin);
}
void MergeSortFile(const char* file)
{
	FILE* fout = fopen(file, "r");
	if (fout == NULL)
	{
		printf("打開檔案失敗\n");
		exit(-1);
	}
	int n = 10;
	int a[10];
	int i = 0;
	int num = 0;
	char subfile[20];
	int filei = 1;
	memset(a, 0, sizeof(int) * n);
	//從fout檔案流里讀，直至EOF
	while (fscanf(fout, "%d\n", &num) != EOF)
	{
		//每次回圈讀10個資料放在記憶體中(if里先放9個，else再放最后一個)
		if (i < n - 1)
		{
			a[i++] = num;
		}
		else
		{
			a[i] = num;
			//快排10個資料
			QuickSort(a, 0, n - 1);
			//生成檔案名sub_sort1/2/3...
			sprintf(subfile, "%d", filei++);
			//寫檔案，subfile里存盤生成的檔案名
			FILE* fin = fopen(subfile, "w");
			if (fin == NULL)
			{
				printf("打開檔案失敗\n");
				exit(-1);
			}
			//寫回小檔案
			for (int i = 0; i < n; i++)
			{
				fprintf(fin, "%d\n", a[i]);
			}
			//關閉檔案
			fclose(fin);
			//重置i
			i = 0;
			memset(a, 0, sizeof(int) * n);
		}
	}
	//互相歸并到檔案，實作整體有序
	char mFile[100] = "12";
	char File1[100] = "1";
	char File2[100] = "2";
	for (i = 2; i <= n; i++)
	{
		//讀取File1和File2，歸并出mFile
		_MergeFile(File1, File2, mFile);
		//拷貝迭代File1的檔案名12/123/1234...
		strcpy(File1, mFile);
		//回圈迭代File2的檔案名3/4/5...
		sprintf(File2, "%d", i + 1);
		//回圈迭代mFile的檔案名123/1234/12345...
		sprintf(mFile, "%s%d",mFile, i + 1);
	}
	//關閉檔案
	fclose(fout);
}

💦 性能測驗

? 測驗所有排序 && 怎么保證它是公平的 ?

??陣列里放的資料都是一樣的

//測驗排序的性能對比
void TestOP()
{
	srand(time(0));
	const int N = 100000;
	int* a1 = (int*)malloc(sizeof(int) * N);
	int* a2 = (int*)malloc(sizeof(int) * N);
	int* a3 = (int*)malloc(sizeof(int) * N);
	int* a4 = (int*)malloc(sizeof(int) * N);
	int* a5 = (int*)malloc(sizeof(int) * N);
	int* a6 = (int*)malloc(sizeof(int) * N);
	int* a7 = (int*)malloc(sizeof(int) * N);
	int* a8 = (int*)malloc(sizeof(int) * N);
	int* a9 = (int*)malloc(sizeof(int) * N);
	int* a10 = (int*)malloc(sizeof(int) * N);
	int* a11 = (int*)malloc(sizeof(int) * N);
	int* a12 = (int*)malloc(sizeof(int) * N);

	for (int i = 0; i < N; i++)
	{
		a1[i] = rand();
		a2[i] = a1[i];
		a3[i] = a1[i];
		a4[i] = a1[i]; 
		a5[i] = a1[i];
		a6[i] = a1[i];
		a7[i] = a1[i];
		a8[i] = a1[i];
		a9[i] = a1[i];
		a10[i] = a1[i];
		a11[i] = a1[i];
		a12[i] = a1[i];
	}

	int begin1 = clock();
	InsertSort(a1, N);
	int end1 = clock();

	int begin2 = clock();
	ShellSort(a2, N);
	int end2 = clock();

	int begin2_1 = clock();
	ShellSortPro(a3, N);
	int end2_1 = clock();

	int begin3 = clock();
	SelectSort(a4, N);
	int end3 = clock();

	int begin3_1 = clock();
	SelectSortPro(a5, N);
	int end3_1 = clock();

	int begin4 = clock();
	HeapSort(a6, N);
	int end4 = clock();

	int begin5 = clock();
	BubbleSort(a6, N);
	int end5 = clock();

	int begin5_1 = clock();
	BubbleSortPro(a7, N);
	int end5_1 = clock();

	int begin6 = clock();
	QuickSort(a8, 0, N - 1);
	int end6 = clock();

	int begin6_1 = clock();
	QuickSortPro(a9, 0, N - 1);
	int end6_1 = clock();

	int begin6_2 = clock();
	QuickSortNonR(a10, 0, N - 1);
	int end6_2 = clock();

	int begin7 = clock();
	MergeSort(a11, N);
	int end7 = clock();

	int begin7_1 = clock();
	MergeSortNonR(a12, N);
	int end7_1 = clock();

	printf("InsertSort:%d\n", end1 - begin1);
	printf("ShellSort:%d\n", end2 - begin2);
	printf("ShellSortPro:%d\n", end2_1 - begin2_1);
	printf("SelectSort:%d\n", end3 - begin3);
	printf("SelectSortPro:%d\n", end3_1 - begin3_1);
	printf("HeapSort:%d\n", end4 - begin4);
	printf("BubbleSort:%d\n", end5 - begin5);
	printf("BubbleSortPro:%d\n", end5_1 - begin5_1);
	printf("QuickSort:%d\n", end6 - begin6);
	printf("QuickSortPro:%d\n", end6_1 - begin6_1);
	printf("QuickSortNonR:%d\n", end6_2 - begin6_2);
	printf("MergeSort:%d\n", end7 - begin7);
	printf("MergeSortNonR:%d\n", end7_1 - begin7_1);


	free(a1);
	free(a2);
	free(a3);
	free(a4);
	free(a5);
	free(a6);
	free(a7);
	free(a8);
	free(a9);
	free(a10);
	free(a11);
	free(a12);
}

💨 輸出結果 (這里使用 Release 版本 && 10 萬個資料)

??這里測驗 3 次

在這里插入圖片描述

三、排序演算法復雜度及穩定性分析

請添加圖片描述
在這里插入圖片描述

? 穩定性 (比較重要，注意不要死記，要結合思想來看) ?

??假定在待排序的記錄序列中，存在多個具有相同的關鍵字的記錄，若經過排序，這些記錄的相對次
序保持不變，即在原序列中，r[i]=r[j]，且 r[i] 在 r[j] 之前，而在排序后的序列中，r[i] 仍在 r[j] 之前，則稱這種排
序演算法是穩定的；否則稱為不穩定的，

在這里插入圖片描述

? 穩定性的意義 ?

??假設有一考試，并規定前 6 名發獎狀，如果分數相同，則按交卷時間的先后計算名次，此時排序穩定性的意義就有所體現了

四、概念選擇題

1、快速排序演算法是基于 ( ) 的一個排序演算法

A. 分治法

B. 貪心法

C. 遞回法

D. 動態規劃法

📝 分析：快速排序是一種分治的演算法，其次遞回不是一種演算法

2、對記錄（54, 38, 96, 23, 15, 72, 60, 45, 83）進行從小到大的直接插入排序時，當把第8個記錄45插入到有序表時，為找到插入位置需比較 ( ) 次？（采用從后往前比較）

A. 3

B. 4

C. 5

D. 6

📝 分析：

15?23?38?54?60?72?96?45

所以需要比較 5 次

3、以下排序方式中占用 O(n) 輔助存盤空間的是 ( )

A. 簡單排序

B. 快速排序

C. 堆排序

D. 歸并排序

📝 分析：注意沒有簡單排序；歸并排序的空間復雜度是 O(N)

4、下列排序演算法中穩定且時間復雜度為 O(n²) 的是 ( )

A. 快速排序

B. 冒泡排序

C. 直接選擇排序

D. 歸并排序

📝 分析：

冒泡排序是穩定的演算法，且時間復雜度是 O(N²)

直接選擇排序是不穩定的，例如：

5?5?1

1?5?5?

5、關于排序，下面說法不正確的是 ( )

A. 快排時間復雜度為 O(N*logN)，空間復雜度為 O(logN)

B. 歸并排序是一種穩定的排序，堆排序和快排均不穩定

C. 序列基本有序時，快排退化成冒泡排序，直接插入排序最快

D. 歸并排序空間復雜度為 O(N)，堆排序空間復雜度的為 O(logN)

📝 分析：堆排序沒使用遞回，沒有輔助空間，所以它的空間復雜度為 O(1)

6、下列排序法中，最壞情況下時間復雜度最小的是 ( )

A. 堆排序

B. 快速排序

C. 希爾排序

D. 冒泡排序

📝 分析：堆排序 (歸并) 最壞情況下和最好情況下時間復雜度最小的 —— O(N*lonN)

7、設一組初始記錄關鍵字序列為 (65,56,72,99,86,25,34,66)，則以第一個關鍵字 65 為基準而得到的第一趟快速排序結果是 ( )

A. 34，56，25，65，86，99，72，66

B. 25，34，56，65，99，86，72，66

C. 34，56，25，65，66，99，86，72

D. 34，56，25，65，99，86，72，66

📝 分析：

我們前面已經了解到快速排序首次單趟的三種方法 —— hoare版本、挖坑版本、前后指標版本，注意在某些情況下需要都考慮到，因為三種版本得到的結果不一定都一樣

在這里插入圖片描述

結合情況此題選擇 A 選項

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

標籤：其他

上一篇：與好友游濕地記往事二三

下一篇：WordPress搭建個人博客完整教程