快捷導(dǎo)航

C語(yǔ)言深入探究選擇排序與基數(shù)排序使用案例講解

更新時(shí)間：2022年05月23日 08:53:11 作者：Mi?ronin

算法中排序是十分重要的,而每一個(gè)學(xué)習(xí)計(jì)算機(jī)的都會(huì)在初期的時(shí)候接觸到這種排序,下面這篇文章主要給大家介紹了關(guān)于c語(yǔ)言選擇排序與基數(shù)排序使用的相關(guān)資料,需要的朋友可以參考下

一.選擇排序

1.1 選擇排序引入

就像炒股一樣，有的人愛(ài)炒短線，不斷的買(mǎi)進(jìn)賣(mài)出通過(guò)差價(jià)來(lái)盈利，但是頻繁的買(mǎi)進(jìn)賣(mài)出，也會(huì)因?yàn)轭l繁的手續(xù)費(fèi)和一系列費(fèi)用獲益較少；有的人，不斷的進(jìn)行觀察和判斷，等到時(shí)機(jī)一到，果斷買(mǎi)進(jìn)或賣(mài)出，這種人交易次數(shù)少，而最終收獲頗豐；正如我們所說(shuō)的第一種人就類(lèi)似排序里的冒泡排序，而第二種人就在排序中可以理解為：在排序時(shí)找到合適的關(guān)鍵字再做交換，并且只交換一次完成相應(yīng)關(guān)鍵字的排序；這就是我們要說(shuō)的選擇排序。

1.2 選擇排序的基本思想與算法分析

基本思想：從頭至尾掃描序列，找出最小的一個(gè)元素，和第一個(gè)元素交換，接著從剩下的元素中繼續(xù)這種選擇和交換方式，最終得到一個(gè)有序序列

算法分析：

第1步:在未排序的n個(gè)數(shù)(a [0] ~a [n- 1])中找到最小數(shù)，將它與a [0]交換;
第2步:在剩下未排序的n- 1個(gè)數(shù)(a [1] ~a [n- 1])中找到最小數(shù)，將它與a[1]交換;
第n-1步:在剩下未排序的2個(gè)數(shù)(a [n-2] ~a [n- 1] )中找到最小數(shù)，將它與a [n-2]交換；
得到一個(gè)排好序的序列。

1.3 實(shí)例說(shuō)明

以12，32，2，60，42，98為例，排序過(guò)程如下：

數(shù)字底下有橫線的為已排好序的
n個(gè)值排n-1次即可
每一次都找一個(gè)最小值放到前面

1.4 代碼實(shí)現(xiàn)

代碼如下：

void SelectSort(int arr[], int len)
{
	for (int i = 0; i < len - 1; i++)//趟數(shù)
	{
		int min_index = i;
		for (int j = i + 1; j < len; j++)//控制找最小值
		{
			if (arr[j] < arr[min_index])
			{
				min_index = j;
			}
		}
		//當(dāng)內(nèi)層for循環(huán)跑完，此時(shí)min_index保存是就是當(dāng)前待排序序列中最小值的下標(biāo)
		if (min_index != i)//如果找到的最小值下標(biāo)  不等于 待排序序列的第一個(gè)值的下標(biāo)  則才有交換的必要性
		{
			int tmp = arr[i];
			arr[i] = arr[min_index];
			arr[min_index] = tmp;
		}
	}
}

1.5 性能分析

時(shí)間復(fù)雜度：O（n^2）。
空間復(fù)雜度：O（1）。
穩(wěn)定性：不穩(wěn)定。

盡管與冒泡排序的時(shí)間復(fù)雜度同為O（n^2），但選擇排序的性能還是略優(yōu)于冒泡排序的。

二.基數(shù)排序

2.1 基數(shù)排序基本思想與算法步驟

基本思想：將整數(shù)按位數(shù)切割成不同的數(shù)字，然后按每個(gè)位數(shù)分別比較，最后合并結(jié)果。

算法步驟：

將所有待比較數(shù)值統(tǒng)一為同樣的數(shù)位長(zhǎng)度，數(shù)位較短的數(shù)前面補(bǔ)零；
從最低位開(kāi)始，依次進(jìn)行一次排序；
從最低位排序一直到最高位排序完成以后, 整合后數(shù)列就變成一個(gè)有序序列。

2.2 實(shí)例說(shuō)明

以12，32，2，620，42，98，122，289，987，37，56，90為例，排序過(guò)程如下：

1.以個(gè)位數(shù)跑一趟：

個(gè)位排序的最終結(jié)果：

620，90，12，32，2，42，122，56，987，27，98，289

（這些數(shù)據(jù)只看個(gè)位的話為有序）

2.以十位跑一趟：

十位排序的最終結(jié)果：

2，12，620，122，27，32，43，56，987，289，90，98

（這些數(shù)據(jù)只看十位的話為有序）

3.以百位跑一趟：

百位排序的最終結(jié)果：

2，12，27，32，43，56，90，98，122，289，620，987

（數(shù)據(jù)已完全有序）

2.3 代碼實(shí)現(xiàn)

代碼如下：

//獲取數(shù)組中最大值的位數(shù)
int Get_figure(int* arr, int len)
{
	int max = 0;
	for (int i = 0; i < len; i++)
	{
		if (arr[i] > max)
		{
			max = arr[i];
		}
	}
	int count = 0;
	while (max != 0)
	{
		count++;
		max /= 10;
	}
	return count;
}
//這個(gè)函數(shù)告訴我傳進(jìn)來(lái)的參數(shù)n的，對(duì)應(yīng)fin位是多少
//1234,2 -> 2    345,1 ->4    0078,3 -> 0     56789,4 -> 5
int Get_Num(int n, int fin)
{
	for (int i = 0; i < fin; i++)//這里代表需要n 先丟幾位最低位
	{
		//n = n/10;
		n /= 10;
	}
	return n % 10;//此時(shí)獲取剩余屬于的最低位即可
}
//一趟桶排序    fin代表這一趟是根據(jù)哪個(gè)位進(jìn)行排序（個(gè)，十，百......）   0->個(gè)位  1->十位...
void Radix(int* arr, int len, int fin)//時(shí)間復(fù)雜度O(n)
{
	//先將10個(gè)桶申請(qǐng)好
	int bucket[10][100] = { 0 };
	int num[10] = { 0 };  //num[1] 代表1號(hào)桶中有多少個(gè)有效值
	//將所有數(shù)據(jù)從左向右向?qū)?yīng)的桶中存放
	for (int i = 0; i < len; i++)
	{
		int index = Get_Num(arr[i], fin);
		bucket[index][num[index]] = arr[i];
		num[index]++;
	}
	//按照0->9號(hào)桶的順序，依次遵循先進(jìn)先出的規(guī)則將所有值取出來(lái)
	int k = 0;
	for (int i = 0; i <= 9; i++)//0->9號(hào)桶依次取
	{
		for (int j = 0; j < num[i]; j++)//對(duì)應(yīng)的桶內(nèi)，從上到下依次取值
		{
			arr[k++] = bucket[i][j];//取出來(lái)的值 從前向后放到arr中
		}
	}
}
//基數(shù)排序（桶排序）  時(shí)間復(fù)雜度(d*n)（假設(shè)最大值的位數(shù)是d） 空間復(fù)雜度O（d*n） 穩(wěn)定性：穩(wěn)定
void RadixSort(int* arr, int len)
{
	//assert
	//1.首先需要知道 數(shù)據(jù)中最大值有多少位
	int count = Get_figure(arr, len);

	for (int i = 0; i < count; i++) //D
	{
		Radix(arr, len, i);
	}
}