選擇排序和冒泡排序是我們初學(xué)C語言必學(xué)的兩種簡單的排序算法，也是我們以后學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法課程中更復(fù)雜的排序算法的基礎(chǔ)。本文用由淺入深的邏輯條理，試圖將這兩種排序算法講解清楚。

本文所有的排序均是針對一維數(shù)組的，全文所用的一維數(shù)組的例子如下：

#include <stdio.h>
int main () {
    int N=5,A[N] = {2,4,1,5,3};
    return 0;
}

一、選擇排序

1.1 一次選擇

一次選擇所要完成的任務(wù)是：從數(shù)組元素A[i]開始，到最后一個元素，即A[N-1]，選擇其中的最小值；然后經(jīng)過一些數(shù)組元素之間的交換，將這個最小值放在A[i]中，最小值以外的其它數(shù)組元素的值仍要分布在A[i+1]到A[N-1]之中，次序不作要求。

思路1：要完成這個任務(wù)，我們可以遍從A[i+1]開始，到A[N-1]為止的所有元素，如果某個A[j] < A[i]，我們就將A[j]和A[i]中的值進(jìn)行交換。完成這個遍歷的后果就只，此時A[i]的值就是原來A[i]到A[N-1]中的最小值，原來除最小值以外的其他值，仍分布在A[i+1]到A[N-1]之中，次序在所不論。

代碼1：

#include <stdio.h>
int main () {
	int N=5,A[5] = {2,4,3,5,1},i,j,tmp;
	i = 2;
	for (j = i+1; j < N; j++) {
		if (A[j] < A[i]) {
			tmp = A[i];
			A[i] = A[j];
			A[j] = tmp;
		}
	}
	for (i = 0; i < N; i++) printf("%d ", A[i]);
    return 0;
}

輸出：

2 4 1 5 3

在上面的代碼中，我們選擇從下標(biāo)為i=2，即A[2]開始到A[N-1]為止的所有元素中的最小值，將其賦值給A[2]，其他原有的數(shù)組元素值任然分布在A[3]到A[4]之中。

1.2 選擇排序 -- 對"一次選擇"的多次迭代。

設(shè)想一下，如果我們第一次選擇i=0的位置為起始位置，進(jìn)行"一次選擇"的任務(wù)，那么整個數(shù)組中的最小值將會賦值給A[0]，其他元素仍然會分布在A[1]到A[N-1]之中。第二次我們再選擇i=1的位置為起始位置，再進(jìn)行一次"一次選擇"的任務(wù)，那么A[1]到A[N-1]中最小的值將會被賦值給A[1]，其他值仍然分布A[2]到A[N-1]之中。這樣A[0]，A[1]元素其實(shí)分別就已經(jīng)是原來數(shù)組元素的最小值和次最小值了。依此類推可知，對當(dāng)我們將"一次選擇"任務(wù)中選擇的起始下標(biāo)i從0開遍歷到N-2，這樣我們恰好就能完成對原數(shù)組的從小到大的排序了。根據(jù)上面的想法，我們就有了如下的選擇排序算法。

代碼2：

#include <stdio.h>
int main () {
	int N=5,A[5] = {2,4,3,5,1},i,j,tmp;
	for (i = 0; i < N-1; i++) {
		for (j = i+1; j < N; j++) {
			if (A[j] < A[i]) {
				tmp = A[i];
				A[i] = A[j];
				A[j] = tmp;
			}
		}
	}
	for (i = 0; i < N; i++) printf("%d ", A[i]);
    return 0;
}

1.3?優(yōu)化后的選擇排序

思路：在"一次選擇"的算法中，也就是上述代碼2的內(nèi)循環(huán)中，我們可以有這樣的優(yōu)化辦法，就是不要每次找到一個比A[i]小的A[j]就進(jìn)行交換，可先把目前找到的最小值的下標(biāo)緩存起來，等到遍歷完以后，進(jìn)行一次交換就行了。根據(jù)這個思路，我們就有了優(yōu)化后的選擇排序算法。

代碼3：

#include <stdio.h>
int main () {
	int N=5,A[5] = {2,4,3,5,1},i,j,min,tmp;
	for (i = 0; i < N-1; i++) {
		min = i;
		for (j = i+1; j < N; j++) {
			if (A[j] < A[min]) {
				min = j;
			}
		}
		if (min > i) {
			tmp = A[i];
			A[i] = A[min];
			A[min] = tmp;
		}
	}
	for (i = 0; i < N; i++) printf("%d ", A[i]);
    return 0;
}

二、冒泡排序

2.1 一次冒泡

先看一次"冒泡"，它的思路比較固定，就是讓j從0開始直到N-2，比較A[j]和它后面緊鄰的元素A[j+1]的大小，如果A[j]>A[j+1]，就交換A[j]和A[j+1]的值；否則就讓j繼續(xù)遍歷。這樣當(dāng)遍歷完以后，原本A[0]到A[N-1]中最大的元素，就被交換賦值給A[N-1]。

代碼4：

#include <stdio.h>
int main () {
    int N=5,A[N] = {2,4,1,5,3},i,j,tmp;
    for (j = 0; j < N-1; j++) {
        if (A[j] > A[j+1]) {
            tmp = A[j];
            A[j] = A[j+1];
            A[j+1] = tmp;
        }
    }
    for (i = 0; i < N; i++) printf("%d ", A[i]);
    return 0; 
}

輸出：

2 1 4 3 5

2.2 冒泡排序?-- 對一次"冒泡"的多次迭代

設(shè)想一下，當(dāng)我們完成第1次"冒泡"任務(wù)，那么數(shù)組元素A[0]到A[N-1]中最大的就被交換到A[N-1]中了，當(dāng)我們完成第2次"冒泡"任務(wù)，那么數(shù)組元素A[0]到A[N-2]中的最大的就被交換到A[N-2]中了。這里要注意，元素A[0]到A[N-2]中的最大的一定比A[N-1]中的元素小，所以沒有優(yōu)化過的"冒泡"任務(wù)會把元素A[0]到A[N-2]中的最大的和A[N-1]進(jìn)行比較，但是比較的結(jié)果一定是A[N-1]大，所以不會進(jìn)行交換。于是，當(dāng)我們進(jìn)行了N-1次"冒泡"任務(wù)后，整個數(shù)組就按從小到大的次序排好了。根據(jù)上面的想法，我們就有了如下的冒泡排序算法。

代碼5：

#include <stdio.h>
int main () {
    int N=5,A[N] = {2,4,1,5,3},i,j,tmp;
    for (i = 0; i < N-1; i++) {
        for (j = 0; j < N-1; j++) {
            if (A[j] > A[j+1]) {
                tmp = A[j];
                A[j] = A[j+1];
                A[j+1] = tmp;
            }
        }
    }
    for (i = 0; i < N; i++) printf("%d ", A[i]);
}

在上面的代碼里，外層循環(huán)的環(huán)變量i，只是用來控制了里層"冒泡"的迭代次數(shù)。并沒有參與里層"冒泡"。

2.3 對冒泡排序的優(yōu)化

對上面的冒泡排序的代碼，我們可以從兩個方面進(jìn)行優(yōu)化。

（1）首先對里層循環(huán)，我們知道第1次"冒泡"完成后，數(shù)組最大的元素就已經(jīng)被拍到最后一位了，那么第2次"冒泡"時，就沒有必要在比較A[N-1]和A[N-2]了。一次類推，容易驗(yàn)證當(dāng)外層循環(huán)為i時，里層循環(huán)只需要進(jìn)行到j(luò)=N-1-i就可以了。根據(jù)上述想法，我們就有了對里層循環(huán)優(yōu)化后的冒泡排序算法。

代碼6：

#include <stdio.h>
int main () {
    int N=5,A[N] = {2,4,1,5,3},i,j,tmp;
    for (i = 0; i < N-1; i++) {
        for (j = 0; j < N-1-i; j++) {
            if (A[j] > A[j+1]) {
                tmp = A[j];
                A[j] = A[j+1];
                A[j+1] = tmp;
            }
        }
    }
    for (i = 0; i < N; i++) printf("%d ", A[i]);
}

（2）對外層循環(huán)的優(yōu)化，上面的代碼我們可以看到，外層循環(huán)的i總會遍歷從0開始到N-1的所有整數(shù)；換句話說，里層循環(huán)作為外層循環(huán)的循環(huán)體，總會被執(zhí)行N-1次。是否有這個必要呢？我們假設(shè)，當(dāng)有一次執(zhí)行里層循環(huán)時，里層循環(huán)遍歷的每一個A[j]和A[j+1]都不發(fā)生交換，這時整個數(shù)組必然是已經(jīng)按照從小到大的次序排好了，否側(cè)不可能不發(fā)生交換。于是，我們可以增加一個變量flag，來記錄里層循環(huán)是否發(fā)生了交換。如果有一次里層循環(huán)沒有發(fā)生交換，那么這次里層循環(huán)執(zhí)行完畢后，就沒有比較再進(jìn)行接下來的里層循環(huán)了；也就是說，這時外層循環(huán)可以直接跳出。根據(jù)上述想法，我們就有了對里層循環(huán)優(yōu)化后的冒泡排序算法。

代碼7：

#include <stdio.h>
int main () {
    int N=5,A[N] = {2,4,1,5,3},i,j,tmp,flag=1;
    for (i = 0; i < N-1; i++) {
        for (j = 0; j < N-1-i; j++) {
            if (A[j] > A[j+1]) {
                tmp = A[j];
                A[j] = A[j+1];
                A[j+1] = tmp;
                flag = 0;
            }
        }
        if (flag) break;
    }
    for (i = 0; i < N; i++) printf("%d ", A[i]);
}

三、封裝成函數(shù)

最后，如果我們對函數(shù)運(yùn)用的足夠熟練，我們可以把上面講的兩種排序算法封裝成函數(shù)，方便調(diào)用。

代碼8：文章來源地址http://www.zghlxwxcb.cn/news/detail-742127.html

#include <stdio.h>
void sort_c (int A[], int N) {    // 選擇排序
	int i,j,min,tmp;
	for (i = 0; i < N-1; i++) {
		min = i;
		for (j = i+1; j < N; j++) {
			if (A[j] < A[min]) min = j;
		}
		if (min > i) {
			tmp = A[i];
			A[i] = A[min];
			A[min] = tmp;
		}
	}
}
void sort_b (int A[], int N) {    // 冒泡排序
	int i,j,tmp,flag = 1;
    for (i = 0; i < N-1; i++) {
        for (j = 0; j < N-1-i; j++) {
            if (A[j] > A[j+1]) {
                tmp = A[j];
                A[j] = A[j+1];
                A[j+1] = tmp;
                flag = 0;
            }
        }
        if (flag) break;
    }
}
int main () {
	int N=5,A[N] = {2,4,3,5,1},i;
	sort_b(A,N);   // 調(diào)用冒泡排序
	// sort_c(A,N);   // 調(diào)用選擇排序
	for (i = 0; i < N; i++) printf("%d ", A[i]);
	return 0;
}

到了這里，關(guān)于排序算法（一） -- 選擇排序和冒泡排序的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！