快捷導(dǎo)航

C語言排序算法的幾種實(shí)現(xiàn)過程

更新時間：2026年04月16日 10:53:36 作者：0302huang

本文介紹了四種排序算法的思想：冒泡排序通過相鄰比較交換實(shí)現(xiàn),選擇排序通過每次選出最小值實(shí)現(xiàn),插入排序通過將當(dāng)前元素插入到有序序列實(shí)現(xiàn),快速排序通過挖坑填數(shù)遞歸實(shí)現(xiàn),每種算法都有其適用場景和優(yōu)缺點(diǎn)

一、冒泡排序

思想：

相鄰的兩個數(shù)比較，若不符合關(guān)鍵字排序順序，則交換，外層循環(huán)n-1輪，內(nèi)層循環(huán)如果從0開始向右比較，則外層循環(huán)每輪得到一個最大的數(shù)，（內(nèi)層循環(huán)若從下標(biāo)n-1開始向左比較，則外層循環(huán)每輪得到一個最小的數(shù)）循環(huán)n-1輪則排序完成。

void bubblesort(int *a,int n){
	int i,j;
	for(i=0;i<n-1;i++){//N-1輪循環(huán) 
		for(j=0;j<n-1-i;j++){//j<n-1-i 小優(yōu)化 
			if(a[j]>a[j+1]){
				swap(&a[j],&a[j+1]);
			}
		}
	}
}

//雙向冒泡排序
void bidbubblesort(int *a,int n){
	int i,j;
	int left,right;
	left=0;right=n-1;
	while(left<right){
		for(i=left;i<right;i++){
			if(a[i]>a[i+1]){
				swap(&a[i],&a[i+1]);
			}
		} //從左向右比較，會出現(xiàn)一個最大的數(shù)在最右邊 
		right--;
		for(i=right;i>left;i--){
			if(a[i]<a[i-1]){
				swap(&a[i],&a[i-1]);
			}
		} //從右向左比較，會出現(xiàn)一個最小的數(shù)在最左邊 
		left++;
	}
}

二、選擇排序

思想：

每次進(jìn)入外層循環(huán)，都要先設(shè)置最小值（或最大值）下標(biāo)min_pos為當(dāng)前i的值，讓內(nèi)層循環(huán)的循環(huán)變量從i的下一個開始遍歷，與a[min_pos]進(jìn)行比較，如果a[i]<a[min_pos],則要讓min_pos=i；內(nèi)層循環(huán)就是為了找到一個最小值的下標(biāo)賦值給min_pos，出了內(nèi)循環(huán)，則交換a[i]和a[min_pos]。

i ++；循環(huán)下去最終循環(huán)n-1次，得到n-1個最小值，則排序完畢

void selectsort(int *a,int n){
	int i,j,min_pos;
	//每一次從新進(jìn)入循環(huán)都要先設(shè)置最小值的下標(biāo)min_pos是當(dāng)前i的值 
	for(i=0;i<n-1;i++){
		min_pos=i;
		for(j=i+1;j<n;j++){//從min_pos的下一個開始遍歷數(shù)組，與a[min_pos]比較，記錄最小值的下標(biāo) 
			if(a[j]<a[min_pos]) {
				min_pos=j;
			}
		}
		if(min_pos!=i){
			swap(&a[i],&a[min_pos]);
		}
	}
}

//逆向選擇排序
void selectsort(int *a,int n){
	int i,j,max_pos;
	for(i=n-1;i>0;i--){ //每一次從新進(jìn)入循環(huán)都要先設(shè)置最大值的下標(biāo)max_pos是當(dāng)前i的值
		max_pos=i; //設(shè)置假設(shè)最大值下標(biāo)  
		for(j=i-1;j>=0;j--){ //j從最大值下標(biāo)的前一個開始，與最大值比較直到j(luò)=0 
			if(a[j]>a[max_pos]){
				max_pos=j;
			}
		}
		if(max_pos!=i){
			swap(&a[max_pos],&a[i]);
		}
	}
}
//雙向選擇排序
void bidselectsort(int *a,int n){
	int i,j;
	int left,right;
	int min_pos,max_pos;
	left=0;
	right=n-1;
	while(left<right){
		max_pos=right;
		min_pos=left;
		for(i=left+1;i<=right;i++){
			if(a[i]<a[min_pos]){
				min_pos=i;
			}
		}
		if(min_pos!=left){
			swap(&a[min_pos],&a[left]);
		}
		left++;
		for(i=right-1;i>=left;i--){
			if(a[i]>a[max_pos]){
				max_pos=i;
			}
		}
		if(max_pos!=right){
			swap(&a[max_pos],&a[right]);	
		}
        right--;	
	}
}

三、插入排序

思路：

核心是從0--0天然有序，到0--1有序，......再到0--n-1有序,因此外層循環(huán)從i=1開始代表先做0--1有序，當(dāng)i循環(huán)到n-1時，則0--n-1有序了，排序完畢，外層到內(nèi)層的連接處，需要設(shè)置當(dāng)前的a[i]=temp，方便后續(xù)的操作（比較大小和插入）。

內(nèi)層循環(huán)，遵循“往前看”的原則，j=i-1開始一直到j(luò)>=0，其實(shí)意思是比較temp與前面元素的相對大小，如果前面某個元素比temp小，則可以break，因?yàn)榍懊娑际怯行虻?，一定也會比temp更小。

若前面的某個元素比temp大，則應(yīng)將它后移一位故a[j+1]=a[j];

void insertsort(int *a,int n){
	int temp;
	int i,j;
	for(i=1;i<n;i++){//從0-1有序到0-n-1有序 
		temp=a[i];
		for(j=i-1;j>=0;j--){//往前看 
			if(a[j]<temp) break;		
			else{
				a[j+1]=a[j];//將現(xiàn)在這個下標(biāo)j的數(shù)后移一位，那應(yīng)該就是移到下標(biāo)為j+1的位置 
			}
		}//出循環(huán)的條件是break或者j=-1; 此時應(yīng)該將a[j+1]=temp; 
		a[j+1]=temp;
	}
}

四、快速排序

思想：

挖坑填數(shù)+遞歸定義一個基準(zhǔn)數(shù)std=a[0]，定義左右下標(biāo)left right，定義一個決策變量（決定哪個下標(biāo)移動）moving。

若moving==2，則應(yīng)該移動右下標(biāo)right，從std的右邊希望去找到一個比std要小的數(shù)，放到左下標(biāo)的位置上，（因?yàn)榘補(bǔ)[0]取出來當(dāng)做std，a[0]一開始是一個坑）；如果沒找到就right--，繼續(xù)找；若找到了，需要三步操作，填數(shù) 改決策變量移動下標(biāo)。

循環(huán)下去當(dāng)left==right時，則把a(bǔ)[left]=std;最后核心是遞歸，需要注意參數(shù)，傳入數(shù)組的首地址和數(shù)組std左邊和右邊的元素個數(shù)。

void quicksort(int *a,int n)
{
	if(n<2){//數(shù)組的元素少于兩個就不用排序了 
		return;
	}
	//遞歸調(diào)用時，std、left，right都是相應(yīng)的參數(shù)，這樣寫是沒問題的
	int std=a[0];	//選取數(shù)組第一個數(shù)作為中心軸 （基準(zhǔn)數(shù)） 
	int left=0;		//左下標(biāo)  
	int right=n-1;	//右下標(biāo) 
	int moving=2;	//判斷當(dāng)前應(yīng)當(dāng)移動哪個下標(biāo)，1-左下標(biāo)，2-右下標(biāo) 
	while(left<right)
	{
		if(moving==2)//移動右下標(biāo)的情況 
	//此時應(yīng)當(dāng)找出一個數(shù) 比基準(zhǔn)數(shù)std 小的數(shù) 放到左邊多出來的坑位 
		{
			if(std<a[right])
	//如果右下標(biāo)位置元素的值大于等于基準(zhǔn)數(shù)，則右下標(biāo)繼續(xù)向左移動 
			{
				right--; 
			}
			else
			//如果右下標(biāo)位置元素的值小于基準(zhǔn)數(shù)，那么把右下標(biāo)的元素填到左下標(biāo)的坑中 
			{ 	//三步操作：填數(shù)，改決策變量，移動下標(biāo) 
				a[left]=a[right];
				left++;		//讓左下標(biāo)向右移動
				moving=1;	//改變 決定移動哪個下標(biāo)的變量moving，使得下次循環(huán)將移動左下標(biāo) 
				continue;
			}	
		} 
		if(moving==1)//移動左下標(biāo)的情況 
//此時應(yīng)當(dāng)找出一個比基準(zhǔn)數(shù)std要大的數(shù) 放到此時右下標(biāo)多出來的坑位 
		{
			if(a[left]<std)//如果左下標(biāo)位置元素的值小于std基準(zhǔn)數(shù)，則左下標(biāo)繼續(xù)向右移動 
			{
				left++;
			} 
			else//如果左下標(biāo)位置元素的值大于std基準(zhǔn)數(shù)，將該值填到右下標(biāo)的坑位 
			{
				a[right]=a[left];
				right--;	//讓右下標(biāo)向左移動 
				moving=2;	//改變 決定移動哪個下標(biāo)的變量moving，使得下次循環(huán)將移動右下標(biāo) 
			} 
		} 
	}
	//此時一輪循環(huán)結(jié)束，left應(yīng)該等于right，將此時的坑位填入std基準(zhǔn)數(shù) 
	a[left]=std;//此時基準(zhǔn)數(shù)的位置是在left這里 
	//這樣基準(zhǔn)數(shù)的左邊是有 0-left-1，即left個元素 
	//這樣基準(zhǔn)數(shù)的右邊是有 n-left-1 個元素 （右邊就等于全部減去左邊再減去中間一個元素） 
	//遞歸調(diào)用該函數(shù)，只是傳進(jìn)去的參數(shù)需要調(diào)整使得，每次調(diào)用函數(shù)的范圍合理 
	quicksort(a,left);//對上一次基準(zhǔn)數(shù)的左邊進(jìn)行排序   
	quicksort(a+left+1,n-left-1);//對上一次的基準(zhǔn)數(shù)的右邊進(jìn)行排序 
	//注意傳入的參數(shù)是 數(shù)組和數(shù)組元素個數(shù),這個仔細(xì)分析一下就行，傳入數(shù)組的首地址
}