資料結構C++——選擇排序（簡單選擇排序和堆排序）

文章目錄

• 資料結構C++——選擇排序（簡單選擇排序和堆排序）
• • 一、待排序記錄的資料類型定義
  • 二、簡單選擇排序
  • 三、堆排序
  • 四、測試的完整代碼
  • 五、總結

一、待排序記錄的資料類型定義

待排序記錄的資料類型

/*------------待排序記錄的資料結構類型定義----------*/
#define MAXSIZE 1001//順序表的最大長度
typedef int KeyType;//定義關鍵字類型為整型
typedef int InfoType;
typedef struct {
	KeyType key;//關鍵字項
	InfoType otherinfo;//其他資料項
}RedType;//記錄類型
typedef struct {
	RedType r[MAXSIZE + 1];//r[0]閑置或用做哨兵單元
	int length;//順序表長度
}SqList;//順序表類型
           

二、簡單選擇排序

簡單選擇排序

選擇排序的基本思想是：每一趟從待排序的記錄中選出關鍵字最小的記錄，按順序放在已排序的記錄序列的最後，直到全部排完為止。簡單選擇排序也稱作直接選擇排序。

簡單選擇排序的算法思路：
1：從一号單元值開始，依次從以後的單元值中找到最小的單元值分别和1、2、3.....号單元值交換
2：排完最後一個單元值後，排序結束
           

/*-------------簡單選擇排序----------------*/
void SelectSort(SqList& L) {
	//對順序表L做簡單選擇排序
	for (int i = 1; i < L.length; i++) {
		//在L.r[i..L.length]中選擇關鍵字最小的記錄
		int k = i;
		for (int j = i + 1; j <= L.length; j++)
			if (L.r[j].key < L.r[k].key) k = j;
		if(k!=i)
		{//交換r[i]與r[k]
			RedType t = L.r[i];
			L.r[i] = L.r[k];
			L.r[k] = t;
		}
	}
}
           

三、堆排序

堆排序

堆排序是一種樹形選擇排序，在排序過程中，将待排序的記錄 r[l…n]看成是一棵完全二叉樹的順序存儲結構，利用完全二叉樹中雙親結點和孩子結點之間的内在關系，在目前無序的序列中選擇關鍵字最大（或最小）的記錄。

/*-------------篩選法調整堆-------------*/
void HeapAdjust(SqList& L, int s, int m) {
	//假設r[s+1...m]已經是堆，将r[s...m]調整為以r[s]為根的大根堆
	RedType rc = L.r[s];
	for (int j = s * 2; j <= m; j *= 2) {
		//沿key較大的孩子結點向下篩選
		if (j < m && L.r[j].key < L.r[j + 1].key) j++;//j為key較大的記錄的下标
		if (rc.key >= L.r[j].key) break;//rc應插入在位置s上
		L.r[s] = L.r[j]; s = j;
	}
	L.r[s] = rc;//插入
}
/*------------建初堆--------------*/
void CreatHeap(SqList& L) {
	//把無序序列L.r[1..n]建成大根堆
	int n = L.length;
	for (int i = n / 2; i > 0; i--)//反複調用HeapAdjust
		HeapAdjust(L, i, n);
}
/*------------堆排序------------*/
void HeapSort(SqList& L) {
	//對順序表L進行堆排序
	CreatHeap(L);//把無序序列L.r[1...L.length]建成大根堆
	for (int i = L.length; i > 1; i--) {
		RedType x = L.r[1];//将堆頂記錄和目前未經排序子序列L.r[1..i]中最後一個記錄互換
		L.r[1] = L.r[i];
		L.r[i] = x;
		HeapAdjust(L, 1, i - 1);//将L.r[1...i-1]重新調整為大根堆
	}
}
           

四、測試的完整代碼

内聯代碼片

// An highlighted block
var foo = 'bar';
           

五、總結

以上為筆者對于選擇排序的一些見解，希望初學者都能有所收獲，有技術不到位的地方，還望各位大佬指正。

同時，筆者的個人首頁還有資料結構其他部分的一些見解與分析，後續資料結構的相關知識還将陸續更新，歡迎大家通路且共同學習！