=========================================================================

相關(guān)代碼gitee自取：

C語言學(xué)習(xí)日記: 加油努力 (gitee.com)

?=========================================================================

接上期：

【數(shù)據(jù)結(jié)構(gòu)初階】八、非線性表里的二叉樹（二叉樹的實現(xiàn) -- C語言鏈?zhǔn)浇Y(jié)構(gòu)）-CSDN博客

?=========================================================================

? ? ? ? ? ? ? ? ? ? ?

排序

排序的概念

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

穩(wěn)定性

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

? ? ? ? ? ? ? ? ?

內(nèi)部排序（內(nèi)排序）

數(shù)據(jù)元素全部放在內(nèi)存中的排序（在內(nèi)存中進行排序）

屬于內(nèi)排序的排序算法：

• 插入排序：
  直接插入排序 、希爾排序
  ? ? ? ? ? ? ? ?
• 選擇排序：
  直接選擇排序 、堆排序
  ? ? ? ? ? ? ? ??
• 交換排序：
  冒泡排序 、快速排序
  ? ? ? ? ? ? ? ?
• 并歸排序（即屬于內(nèi)排序又屬于外排序）

? ? ? ? ? ? ? ? ?

外部排序（外排序）

數(shù)據(jù)元素太多，不能同時放在內(nèi)存中，

根據(jù)排序過程的要求不能在內(nèi)外存之間移動數(shù)據(jù)的排序，

即在磁盤中（“順序?qū)戫樞蜃x”）進行排序

屬于外排序的排序算法：

• 并歸排序（即屬于內(nèi)排序又屬于外排序）

? ? ? ? ? ? ? ??

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

? ? ? ? ? ? ? ? ?

常見排序算法的實現(xiàn)

（詳細解釋在圖片的注釋中，代碼分文件放下一標(biāo)題處）

? ? ? ? ? ? ? ? ? ?

一、插入排序

? ? ? ? ? ? ? ? ? ? ? ??

插入排序 -- 直接插入排序

直接插入排序是一種簡單的插入排序法

? ? ? ? ? ? ? ? ?

該算法基本思想：

把待排序的記錄按其關(guān)鍵碼值的大小逐個插入到一個已經(jīng)排好序的有序序列中，

直到所有的記錄插入完為止，得到一個新的有序序列
（想象我們玩撲克牌時，給撲克牌大小排序就用了插入排序的思想）

? ? ? ? ? ? ? ? ? ? ??

實現(xiàn)思路：

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

直接插入排序的特性總結(jié)：

• 元素越接近有序，直接插入排序算法的時間效率越高 -- 最高可達O(N)
  ? ? ? ? ? ? ? ? ? ? ? ??
• 該算法時間復(fù)雜度：O(N^2) -- 最壞的情況下(逆序)
  ? ? ? ? ? ? ? ? ? ? ? ? ? ??
• 該算法空間復(fù)雜度：O(1)
  ? ? ? ? ? ? ? ? ? ? ??
• 該算法穩(wěn)定性：穩(wěn)定
  ? ? ? ? ? ? ? ? ??

---------------------------------------------------------------------------------------------

? ? ? ? ? ? ? ? ? ? ? ?

InsertSort函數(shù) -- 直接插入排序?qū)崿F(xiàn)函數(shù)

• 使用for循環(huán)進行循環(huán)插入排序，
  再設(shè)置 “前元素” 和 “后元素”
  ? ? ? ? ? ? ? ? ? ? ? ?
• for循環(huán)中：
  使用while循環(huán)為“后元素”尋找合適位置，
  找到后再將 “后元素” 插入，
  之后再次進行for循環(huán)讓下個“后元素”插入合適位置

圖示：

該函數(shù)執(zhí)行邏輯圖：

對應(yīng)函數(shù)測試：

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

? ? ? ? ? ??

---------------------------------------------------------------------------------------------

? ? ? ? ? ??

插入排序 -- 希爾排序（縮小增量排序）

希爾排序又稱縮小增量法。

? ? ? ? ? ? ?

該算法基本思想：

先選定一個整數(shù)gap值，把待排序文件中所有記錄分成gap個組，

所有距離為gap的記錄分在同一組內(nèi)，并對每一組內(nèi)的記錄進行直接插入排序，

然后換個整數(shù)gap值再取gap組，重復(fù)上述分組和排序的工作，

當(dāng) gap=1 時，所有記錄在同一組內(nèi)時已經(jīng)排好序了

? ? ? ? ? ? ? ?

希爾排序的特性總結(jié)：

• 希爾排序是對直接插入排序的優(yōu)化
  ? ? ? ? ? ? ??
• 當(dāng) gap>1 時都是在進行預(yù)排序，目的是讓數(shù)組更接近于有序，
  當(dāng) gap==1 時，數(shù)組已經(jīng)接近有序的了，這樣再進行直接插入排序就會很快，
  這樣整體而言，可以達到優(yōu)化的效果
  ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??
• 希爾排序的時間復(fù)雜度不好計算，因為gap的取值方法很多，導(dǎo)致很難去計算，
  因此在一些書中給出的希爾排序的時間復(fù)雜度也不固定，
  該函數(shù)大概的時間復(fù)雜度為：O(N^1.3)
  ? ? ? ? ? ? ? ? ? ? ? ?
• 該算法穩(wěn)定性：不穩(wěn)定
  ? ? ? ? ? ? ? ? ? ? ? ? ?

---------------------------------------------------------------------------------------------

? ? ? ? ? ? ? ? ? ? ? ?

ShellSort函數(shù) -- 希爾排序?qū)崿F(xiàn)函數(shù)

• 核心實現(xiàn)操作還是直接插入排序，
  但是在對所有值進行直接插入排序前先進行多次預(yù)排序操作，
  （預(yù)排序也是用直接插入排序完成）
  讓數(shù)組達到盡量有序的狀態(tài)
  ? ? ? ? ? ? ??
• 定義gap值變量，使用while循環(huán)控制多次預(yù)排序
  （當(dāng)gap==1時，就相當(dāng)于直接插入排序）
  ? ? ? ? ? ? ? ??
• while循環(huán)中內(nèi)嵌for循環(huán)完成“當(dāng)前gap組”的預(yù)排序
  ? ? ? ? ? ? ? ? ?
• 再內(nèi)嵌for循環(huán)完成“當(dāng)前gap組”其中一組的預(yù)排序
  （通過直接插入排序的方式實現(xiàn)）
  ? ? ? ? ? ? ? ??
  • 最后再內(nèi)嵌while循環(huán)配合完成直接插入排序

圖示：

該函數(shù)執(zhí)行邏輯圖：

對應(yīng)函數(shù)測試：

? ? ? ? ? ? ? ? ? ? ?

? ? ? ? ? ? ? ? ? ? ?

---

? ? ? ? ? ? ? ? ? ??

二、選擇排序

基本思想：

每一趟排序從待排序的數(shù)組元素中分別選擇出最小和最大的一個元素，
再分別存放在數(shù)組的起始位置和尾部位置，
直到全部待排序的數(shù)組元素排序完成

????????????????

????????????????

選擇排序 -- 直接選擇排序

? ? ? ? ? ? ? ? ? ??

該算法基本思想：

在元素集合 array[i] -- array[n-1] 中選擇獲取當(dāng)前最小值元素和當(dāng)前最大值元素，
將當(dāng)前最小值元素交換后放到當(dāng)前數(shù)組的起始位置，
將當(dāng)前最大值元素交換后放到當(dāng)前數(shù)組的尾部位置，

在剩余的 array[i+1] -- array[n-2] 集合中，重復(fù)上述操作，直到集合剩余1個元素
? ? ? ? ? ? ? ?

直接選擇排序的特性總結(jié)：

• 直接選擇排序比較好理解，但是效率不高，實際很少使用
  ? ? ? ? ? ? ? ? ??
• 該算法時間復(fù)雜度：O(N^2)
  ? ? ? ? ? ? ? ? ? ? ?
• 該算法空間復(fù)雜度：O(1)
  ? ? ? ? ? ? ? ? ? ?
• 該算法穩(wěn)定性：不穩(wěn)定
  ? ? ? ? ? ? ? ? ? ? ?

---------------------------------------------------------------------------------------------

? ? ? ? ? ? ? ? ? ? ? ?

SelectSort函數(shù) -- 直接選擇排序?qū)崿F(xiàn)函數(shù)

• 定義 數(shù)組開始(初始)位置下標(biāo)begin 和 數(shù)組尾部(結(jié)束)位置下標(biāo)end 變量，
  使用while循環(huán)控制多趟直接選擇排序
  ? ? ? ? ? ? ? ? ? ??
• （在while循環(huán)中：完成一趟直接選擇排序）
  定義 存放當(dāng)前最小值下標(biāo)mini 和 存放當(dāng)前最大值下標(biāo)maxi 變量，
  內(nèi)嵌for循環(huán)，遍歷一次當(dāng)前數(shù)組找到當(dāng)前最大值和當(dāng)前最小值
  ? ? ? ? ? ? ? ? ? ?
• （while循環(huán)中for循環(huán)外：）
  將找到的當(dāng)前數(shù)組最小值放入數(shù)組起始（左邊）位置，
  當(dāng)前數(shù)組最大值放入數(shù)組尾部（右邊）位置,
  完成兩值的排序后，調(diào)整 begin 和 end 變量，縮小數(shù)組范圍準(zhǔn)備下趟直接選擇排序

圖示：

該函數(shù)執(zhí)行邏輯圖：

對應(yīng)函數(shù)測試：

? ? ? ? ? ??

? ? ? ? ? ??

---------------------------------------------------------------------------------------------

? ? ? ? ? ??

選擇排序 -- 堆排序

堆是一種完全二叉樹，
可以使用堆中的向下調(diào)整操作對普通數(shù)組進行排序（升序或降序）

? ? ? ? ? ? ? ?

堆排序的特性總結(jié)：

• 堆排序使用堆進行選擇排序，效率就高了很多
  ? ? ? ? ? ? ? ? ??
• 該算法時間復(fù)雜度：O(N*logN)
  ? ? ? ? ? ? ? ? ? ? ?
• 該算法空間復(fù)雜度：O(1)
  ? ? ? ? ? ? ? ? ? ?
• 該算法穩(wěn)定性：不穩(wěn)定
  ? ? ? ? ? ? ? ? ? ? ?

---------------------------------------------------------------------------------------------

? ? ? ? ? ? ? ? ? ? ? ?

堆排序的實現(xiàn)往期博客中已有詳細描述：

【數(shù)據(jù)結(jié)構(gòu)初階】七、非線性表里的二叉樹（堆的實現(xiàn) -- C語言順序結(jié)構(gòu)）-CSDN博客

（包含堆排序的 實現(xiàn)函數(shù)、圖示、對應(yīng)函數(shù)執(zhí)行邏輯圖、函數(shù)測試、原代碼）

? ? ? ? ? ? ? ? ? ? ?

? ? ? ? ? ? ? ? ? ? ?

---

? ? ? ? ? ? ? ? ? ??

三、交換排序

基本思想：

所謂交換，就是根據(jù)序列中兩個記錄鍵值的比較結(jié)果來交換這兩個記錄在序列中的位置

? ? ? ? ? ? ?

交換排序的特點：

將鍵值較大的記錄向序列的尾部移動，鍵值較小的記錄向序列的前部移動

? ? ? ? ? ? ? ? ? ? ??

? ? ? ? ? ? ? ? ? ? ??

交換排序 -- 冒泡排序

? ? ? ? ? ? ? ? ? ? ?

該算法基本思想：

數(shù)組中的元素1和元素2進行比較，如果元素1大于元素2，則交換兩者位置；

再比較此時的元素2和元素3，如果元素2大于元素3，則交換兩者位置；

再比較此時的元素3和元素4……

一趟冒泡排序完成后，就能完成當(dāng)前數(shù)組中最大值的排序（排在尾部），
再進行下一趟冒泡排序前要縮小數(shù)組排序范圍（排除已經(jīng)排序好的最大值），

這樣多趟冒泡排序完成后就能完成數(shù)組的排序

? ? ? ? ? ? ? ? ? ? ?

冒泡排序的特性總結(jié)：

• 冒泡排序是一種非常容易理解的排序
  ? ? ? ? ? ? ? ? ??
• 該算法時間復(fù)雜度：O(N^2)
  ? ? ? ? ? ? ??
• 該算法空間復(fù)雜度：O(1)
  ? ? ? ? ? ? ? ? ? ? ??
• 該算法穩(wěn)定性：穩(wěn)定
  ? ? ? ? ? ? ? ? ? ? ? ?

---------------------------------------------------------------------------------------------

? ? ? ? ? ? ? ? ? ? ? ?

BubbleSort函數(shù) -- 冒泡排序?qū)崿F(xiàn)函數(shù)

• 定義嵌套for循環(huán)完成冒泡排序，
  外層for循環(huán)控制當(dāng)前數(shù)組范圍，數(shù)組范圍慢慢減小，
  減到變成1時排序完成（至少有兩個數(shù)才能比較）
  ? ? ? ? ? ? ? ? ? ? ? ??
• 內(nèi)層for循環(huán)循環(huán)一趟完成當(dāng)前數(shù)組范圍內(nèi)的最值的排序
  ? ? ? ? ? ? ? ? ? ??
• 在當(dāng)前冒泡排序過程中，
  設(shè)置一個變量exchange記錄當(dāng)前一趟冒泡排序過程中是否有發(fā)生元素的交換，
  一趟冒泡排序后，如果沒有任何元素發(fā)生交換，
  說明目前已經(jīng)排好序了，那就直接終止之后的冒泡排序

圖示：

該函數(shù)執(zhí)行邏輯圖：

對應(yīng)函數(shù)測試：

? ? ? ? ? ? ? ? ?

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

? ? ? ? ? ? ? ? ? ? ??

對應(yīng)代碼：

Sort.h -- 排序頭文件

#pragma once

//包含之后所需頭文件：
#include <stdio.h>

//打印數(shù)組函數(shù)：
void PrintArray(int* a, int n);


//直接插入排序函數(shù)：
//第一個參數(shù)：接收要排序的數(shù)組首元素地址（a）
//第二個參數(shù)：接收該數(shù)組的長度（n）
void InsertSort(int* a, int n);


//希爾排序函數(shù)：
//第一個參數(shù)：接收要排序的數(shù)組首元素地址（a）
//第二個參數(shù)：接收該數(shù)組的長度（n）
void ShellSort(int* a, int n);
//1、預(yù)排序：分組排，間隔為gap(間距間隔)分為一組
//				預(yù)排序意義：
// 讓大的數(shù)更快的到數(shù)組后面，小的數(shù)更快的到數(shù)組前面，
// gap值越大“跳”得越快，但是越不接近有序
// gap值越小“跳”得越慢，但是越接近有序
// 當(dāng)gap==1時，就相當(dāng)于直接插入排序
//2、直接插入排序


//冒泡排序函數(shù)：
//第一個參數(shù)：接收要排序的數(shù)組首元素地址（a）
//第二個參數(shù)：接收該數(shù)組的長度（n）
void BubbleSort(int* a, int n);	


//直接選擇排序函數(shù)：
//第一個參數(shù)：接收要排序的數(shù)組首元素地址（a）
//第二個參數(shù)：接收該數(shù)組的長度（n）
void SelectSort(int* a, int n);

? ? ? ? ? ??

? ? ? ? ? ??

---------------------------------------------------------------------------------------------

? ? ? ? ? ??

Sort.c -- 排序函數(shù)實現(xiàn)文件

#define _CRT_SECURE_NO_WARNINGS 1

//包含排序頭文件：
#include "Sort.h"

//打印數(shù)組函數(shù)：
void PrintArray(int* a, int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", a[i]);
	}

	printf("");
}



//直接插入排序函數(shù)（升序）：
//第一個參數(shù)：接收要排序的數(shù)組首元素地址（a）
//第二個參數(shù)：接收該數(shù)組的長度（n）
void InsertSort(int* a, int n)
{
	//使用for循環(huán)進行循環(huán)插入排序：
		/*
		要取“前后元素”，“后元素”要依次和“前面所有元素”進行比較，
		直到“后元素”找到合適位置并插入，而“后元素”下標(biāo)最大為[n-1]，
		所以“前元素”下標(biāo)最大為[n-2]
		*/
	for (int i = 0; i < n - 1; i++)
		//循環(huán)到 i = n-2  --  “前元素”下標(biāo)最大為[n-2]：
	{
		//遍歷下標(biāo)的起始位置從 0 開始，到 n-2 結(jié)束：
		int end = i; //“前元素”

		//保存end下標(biāo)元素的后一個元素：
		int tmp = a[end + 1]; //“后元素”

		//使用while循環(huán)為“后元素”尋找合適位置：
		//（“后元素”循環(huán)和其前面所有元素進行比較，直到找到合適位置）
		while (end >= 0)
			//“前面所有元素”：下標(biāo) >=0 時就還有 “前元素”，
			//那“后元素”就需要繼續(xù)進行比較：
		{
			if (tmp < a[end])
				//“后元素” 小于 “前元素”：
			{
				//那就將“前元素(較大)”往后插入（覆蓋）:
				a[end + 1] = a[end];
				//a[end + 1]，被覆蓋的元素還保留在tmp中，
				//所以不用擔(dān)心覆蓋后找不到“后元素”
			}
			else
				//"后元素" 大于等于 "前元素"：
			{
				//說明“后元素”的“前面較大元素”都已經(jīng)往后覆蓋完成了，
				//找到了"后元素"的恰當(dāng)位置，
				//break退出循環(huán)將“后元素”tmp插入該位置
				break;
			}

			end--;
			//當(dāng)前end--，下次循環(huán)判斷“前前元素”需不需要再往前覆蓋，
			//end減到-1退出while循環(huán)的話，說明“后元素”是數(shù)組中最小的元素，
			//導(dǎo)致其前面所有元素都需要往后覆蓋挪出位置
		}

		//注意，合適的位置是[end + 1]，
		//因為"后元素" 大于等于 "前元素"的話，
		//那“后元素”就理應(yīng)排在“前元素”后面，即[end + 1]，
		a[end + 1] = tmp;
		//如果是end減到-1退出的while循環(huán)，
		//那[end + 1]就等于0，即數(shù)組首元素位置，
		//讓“后元素”排在數(shù)組首元素位置
	}
}
//時間復(fù)雜度：
//O(N^2) -- 逆序（最壞情況）
//O(N) -- 順序有序
//冒泡排序和插入排序論時間復(fù)雜度它們是同一檔次，
//但在細節(jié)上，如局部有序，插入排序會更優(yōu)



//希爾排序函數(shù)：
//第一個參數(shù)：接收要排序的數(shù)組首元素地址（a）
//第二個參數(shù)：接收該數(shù)組的長度（n）·
void ShellSort(int* a, int n)
{
	//定義分組間隔和分組個數(shù)：
	int gap = n;
	
	//只要當(dāng)前預(yù)排序gap值還沒到1，
	//while循環(huán)就繼續(xù)循環(huán)進行預(yù)排序：
	while (gap > 1)
	{
		//變化gap值進行多次預(yù)排序，
		//讓數(shù)組越來越接近有序：
		gap = gap / 2;
		//當(dāng) gap > 1 時就是預(yù)排序
		//當(dāng) gap == 1 時就是插入排序

		//這個for循環(huán)控制 “當(dāng)前gap組” 的排序：
		//（一組“gap分”組排完再排另一組gap分組）
		for (int j = 0; j < gap; j++)
		/*
		* 假設(shè)gap取3，
		* 就在數(shù)組中以3(gap)為間隔取數(shù)為一組（gap分組）
		* 總共取3(gap)組
		*/
		{
			//這個for循環(huán)控制gap組中其中一組的排序：
			for (int i = 0; i < n - gap; i += gap)
			/*
			*					循環(huán)條件：n - gap  
			*控制“前元素end”范圍，保證“后元素tmp”通過end取值時不出界
			*					迭代條件：i += gap
			*i每次迭代時就+gap，實現(xiàn)以gap為間隔取數(shù)為一組（gap分組）
			*/
			{
				//保存當(dāng)前分組的“前元素”（記錄）：
				int end = i;

				//保存當(dāng)前分組的“后元素”（記錄）：
				int tmp = a[end + gap];

				//使用while循環(huán)為“后元素”尋找合適位置:
				//(“后元素”循環(huán)和其前面所有元素進行比較，直到找到合適位置)
				//(和直接插入類似，只是值與值間隔不同)
				while (end >= 0)
					//“前面所有元素”：下標(biāo) >=0 時就還有 “前元素”，
					//那“后元素”就需要繼續(xù)進行比較：
				{
					if (tmp < a[end])
						//“后元素” 小于 “前元素”：
					{
						//(gap分組中：)
						//那就將“前元素(較大)”往后插入（覆蓋）:
						a[end + gap] = a[end];
						//a[end + gap]，被覆蓋的元素還保留在tmp中，
						//所以不用擔(dān)心覆蓋后找不到“后元素”

						end -= gap;
						//(gap分組中：)
						//當(dāng)前end-=gap，下次循環(huán)判斷“前前元素”需不需要再往前覆蓋，
						//end減到<0時，退出while循環(huán)的話，說明“后元素”是數(shù)組中最小的元素，
						//導(dǎo)致其前面所有元素都需要往后覆蓋挪出位置
					}
					else
						//"后元素" 大于等于 "前元素"：
					{
						//說明“后元素”的“前面較大元素”都已經(jīng)往后覆蓋完成了，
						//找到了"后元素"的恰當(dāng)位置，
						//break退出循環(huán)將“后元素”tmp插入該位置
						break;
					}
				}

				//注意，合適的位置是[end + gap]，
				//因為"后元素" 大于等于 "前元素"的話，
				//那“后元素”就理應(yīng)排在“前元素”后面，即[end + gap]，
				a[end + gap] = tmp;
				//如果是 end減到<0 退出的while循環(huán)，
				//那[end + gap]就找到當(dāng)前gap組首元素位置，
				//讓“后元素”排在當(dāng)前gap組首元素位置
			}
		}
	}
}



//兩值交換函數(shù)：
void Swap(int* x, int* y)
{
	//創(chuàng)建中間值進行值的交換：
	int tmp = *x;
	*x = *y;
	*y = tmp;
}



//冒泡排序函數(shù)：
//第一個參數(shù)：接收要排序的數(shù)組首元素地址（a）
//第二個參數(shù)：接收該數(shù)組的長度（n）
void BubbleSort(int* a, int n)
{
	/*
	* 定義嵌套for循環(huán)完成冒泡排序：
	* 內(nèi)層for循環(huán)一趟完成當(dāng)前數(shù)組范圍內(nèi)的最值的排序
	* 外層for循環(huán)則控制當(dāng)前數(shù)組范圍
	* 數(shù)組范圍慢慢減小，減到變成1時排序完成
	* （至少有兩個數(shù)才能比較）
	*/

	//這個for循環(huán)控制內(nèi)嵌for循環(huán)的數(shù)組范圍：
	for (int j = 0; j < n; j++)
	{
		int exchange = 0; 
		//如果沒發(fā)生交換該變量就為0

		//內(nèi)嵌for循環(huán)進行循環(huán)比較交換：
		for (int i = 1; i < n-j; i++)
		/*
		*n-j ：通過判斷條件控制數(shù)組范圍
		*因為一趟下來就完成一個當(dāng)前最值的排序，
		*下次再排序的數(shù)組范圍就要排除這個已經(jīng)排好序的最值，
		*通過外部for循環(huán)的j來控制數(shù)組范圍：
		*/
		{
			if (a[i - 1] > a[i])
				//如果“前元素” 大于 “當(dāng)前元素”：
				//（ i 從1開始）
			{
				//進行交換：
				Swap(&a[i - 1], &a[i]);

				exchange = 1;
				//如果發(fā)生了變化該變量就為1
			}
		}
		/*
		* 內(nèi)嵌for循環(huán)整個執(zhí)行完就是一趟，
		* 當(dāng)遇到最大值后，因為最大所以會一直被交換
		* 直到被交換至數(shù)組尾部，
		* 這就完成了當(dāng)前數(shù)組最大值的排序
		*/

		if (exchange == 0)
			//一趟冒泡排序后，如果沒有發(fā)生交換：
		{
			//說明目前已經(jīng)排好序了，
			//就沒必要再進行之后的冒泡排序了：
			break;
		} 
	}
}



//直接選擇排序函數(shù)：
//第一個參數(shù)：接收要排序的數(shù)組首元素地址（a）
//第二個參數(shù)：接收該數(shù)組的長度（n）
void SelectSort(int* a, int n)
{
	/*
	* 思路：
	* 排序一趟選出當(dāng)前最小值下標(biāo)和當(dāng)前最大值下標(biāo),
	* 通過對應(yīng)下標(biāo)將最小值放“左邊”，最大值放“右邊”
	*/

	//數(shù)組開始位置下標(biāo) -- 0
	int begin = 0;
	
	//數(shù)組尾部（結(jié)束）位置下標(biāo) -- n-1
	int end = n - 1;

	//使用while循環(huán)控制多趟直接選擇排序：
	while (begin < end)
	/*
	* 只要 begin 還小于 end，左右下標(biāo)就還沒重合
	* begin 和 end 之間就還有元素要被排序
	*/
	{
		//對當(dāng)前數(shù)組范圍進行一趟直接選擇排序：

		//存放當(dāng)前最小值下標(biāo)：
		int mini = begin; //默認為下標(biāo)0

		//存放當(dāng)前最大值下標(biāo)：
		int maxi = begin; //默認為下標(biāo)0

		//使用for循環(huán)遍歷一次當(dāng)前數(shù)組，
		//找到當(dāng)前最大值和當(dāng)前最小值：
		for (int i = begin+1; i <= end; i++)
		/*
		* mini 和 maxi 默認下標(biāo)都是0
		* 所以循環(huán)時下標(biāo)從[begin+1]開始，等于[n-1]結(jié)束
		*/
		{
			//選出當(dāng)前最大值下標(biāo)：
			if (a[i] > a[maxi])
				//如果“i下標(biāo)元素”大于“maxi下標(biāo)元素”：
			{
				//將較大值下標(biāo)i賦給maxi下標(biāo)：
				maxi = i;
			}

			//選出當(dāng)前最小值下標(biāo)：
			if (a[i] < a[mini])
				//如果“i下標(biāo)元素”小于“mini下標(biāo)元素”：
			{
				//將較小值下標(biāo)i賦給mini下標(biāo)：
				mini = i;
			}

		} //(for循環(huán)中)

		//將找到的當(dāng)前數(shù)組最小值放入數(shù)組起始（左邊）位置：
		Swap(&a[begin], &a[mini]);
		/*
		* 注：如果begin下標(biāo)元素為最大值，
		* 那么maxi下標(biāo)也會指向該元素，即begin == maxi，
		* 當(dāng)begin元素和mini交換后（只是值交換），
		* begin 和 maxi下標(biāo)還是重疊在原位置，指向交換后的mini元素
		* 此時如果再執(zhí)行 Swap(&a[end], &a[maxi]);
		* 就反而會將最小值移到數(shù)組尾部去，
		* 所以要調(diào)整 begin==maxi 重疊的情況：
		*/
		if (maxi == begin)
			//排除maxi和begin下標(biāo)重疊的情況：
		{
			//maxi==begin等于當(dāng)前最大值下標(biāo)，上面交換后，
			//當(dāng)前最大值就在mini下標(biāo)處，
			//那就把maxi最大值下標(biāo)指向mini下標(biāo)處即可：
			maxi = mini;
		}

		//將找到的當(dāng)前數(shù)組最大值放入數(shù)組尾部（右邊）位置：
		Swap(&a[end], &a[maxi]);
	
		/*
		* 執(zhí)行到這就選出了兩個最值并放到了合適位置（一趟直接選擇排序），
		* 調(diào)整 begin 和 end 下標(biāo)（調(diào)整數(shù)組范圍），數(shù)組范圍往中間縮小，
		* 再開始新一趟直接選擇排序：
		*/
		++begin;
		--end;

	} //(while循環(huán)中)
}
//時間復(fù)雜度：O(N^2)

? ? ? ? ? ??

? ? ? ? ? ??

---------------------------------------------------------------------------------------------

? ? ? ? ? ??

Test.c -- 排序測試文件

#define _CRT_SECURE_NO_WARNINGS 1

//包含排序頭文件：
#include "Sort.h"

//插入排序測試：
void ISTest()
{
	//創(chuàng)建要進行插入排序的數(shù)組：
	int a[] = { 3,4,2,1,5 };

	//調(diào)用插入排序函數(shù)進行排序：
	InsertSort(a, 5);

	//循環(huán)打印排序后的數(shù)組：
	printf("使用直接插入排序后的數(shù)組:> ");
	for (int i = 0; i < 5; i++)
	{
		printf("%d ", a[i]);
	}
}


//希爾排序測試：
void SSTest()
{
	//創(chuàng)建要進行插入排序的數(shù)組：
	int a[] = { 9,1,2,5,7,4,8,6,3,5 };

	//調(diào)用希爾排序函數(shù)進行排序：
	ShellSort(a, sizeof(a) / sizeof(int));

	//使用自定義打印函數(shù)打印排序后數(shù)組：
	printf("使用希爾排序后的數(shù)組:> ");
	PrintArray(a, sizeof(a) / sizeof(int));
}


//冒泡排序測試：
void BSTest()
{
	//創(chuàng)建要進行插入排序的數(shù)組：
	int a[] = { 9,1,2,5,7,4,8,6,3,5 };

	//調(diào)用冒泡排序函數(shù)進行排序：
	BubbleSort(a, sizeof(a) / sizeof(int));

	//使用自定義打印函數(shù)打印排序后數(shù)組：
	printf("使用冒泡排序后的數(shù)組:> ");
	PrintArray(a, sizeof(a) / sizeof(int));
}


//直接選擇排序測試：
void SlSTest()
{
	//創(chuàng)建要進行插入排序的數(shù)組：
	int a[] = { 9,1,2,5,7,4,8,6,3,5 };

	//調(diào)用直接選擇排序函數(shù)進行排序：
	SelectSort(a, sizeof(a) / sizeof(int));

	//使用自定義打印函數(shù)打印排序后數(shù)組：
	printf("使用直接選擇排序后的數(shù)組:> ");
	PrintArray(a, sizeof(a) / sizeof(int));
}


int main()
{
	//ISTest();
	//SSTest();
	//BSTest();
	SlSTest();

	return 0;
}

到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)初階】九、五種比較排序的講解和實現(xiàn)（直接插入 \ 希爾 \ 直接選擇 \ 堆 \ 冒泡 -- C語言）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！