快捷導(dǎo)航

C語(yǔ)言中的5種簡(jiǎn)單排序算法(適合小白)

更新時(shí)間：2023年03月30日 12:08:43 作者：Finecsr

在編程練習(xí)時(shí)我們經(jīng)常會(huì)遇到一些將一串亂序的數(shù)字排列成有序的數(shù)列(遞增,遞減)的問題,以此起到解決問題的效果,下面這篇文章主要給大家介紹了關(guān)于C語(yǔ)言中的5種簡(jiǎn)單排序算法的相關(guān)資料,需要的朋友可以參考下

基本概要：

本文主要介紹五種簡(jiǎn)單常用的排序算法：冒泡排序，快速排序，插入排序，選擇排序，希爾排序。包括它們的基本思想和代碼實(shí)現(xiàn)。值得一說的是：插入排序，冒泡排序，選擇排序平均情況下的時(shí)間復(fù)雜度為，因此在排序數(shù)據(jù)較少的情況下較好；而希爾排序和快速排序的平均時(shí)間復(fù)雜度為，因此在排序數(shù)據(jù)較多的情況下較好，但是對(duì)于快速排序而言，數(shù)據(jù)基本有序時(shí)反而不好，接下來(lái)會(huì)詳細(xì)闡述。（皆以從小到大的順序排列）

1.冒泡排序（Bubble Sort）

基本思想：

冒泡排序是一個(gè)非常好理解的排序，顧名思義——冒泡，此時(shí)將要排序的數(shù)據(jù)從上至下排列，從最上面的數(shù)（第一個(gè)數(shù)據(jù)）開始對(duì)相鄰的兩個(gè)數(shù)據(jù)進(jìn)行比較，較小的數(shù)據(jù)往上浮，較大的數(shù)據(jù)往下沉，達(dá)到排序的效果。

（1）對(duì)每一對(duì)相鄰的元素進(jìn)行比較，若第一個(gè)比第二個(gè)大，則調(diào)換這兩個(gè)元素的位置，依次兩兩比較直到數(shù)據(jù)的最后一對(duì)，此為一輪操作。

（2）重復(fù)n輪此操作（n為元素的個(gè)數(shù)），不過每輪結(jié)束后的最后一個(gè)元素不用參與下一輪的比較，因?yàn)榻?jīng)歷一輪排序后，最后一個(gè)元素一定比前面所有的元素都要大。

（3）因此每一輪需要比較的元素都在減少，一直到?jīng)]有數(shù)可比較為止。（不過為了減少比較次數(shù)，可以記錄每輪是否有數(shù)據(jù)的交換，如果沒有交換，表明當(dāng)前數(shù)據(jù)已經(jīng)按從小到大的順序拍好了，可直接跳出循環(huán)）

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

#include<stdio.h>
 
int main() {
	int n, m, i, j, temp;
	int arr[100];
 
	scanf_s("%d", &n);    //scnaf_s是更為安全的輸入方式；n為元素的個(gè)數(shù)；
	for (i = 0; i < n; i++) {
		scanf_s("%d", &arr[i]);    //輸入數(shù)據(jù)；
	}
 
	m = n;            //因?yàn)槊窟M(jìn)行一次第一輪循環(huán)，需要排序的數(shù)據(jù)都要“--”，因此定義變量m=n；
	for (i = 0; i < n; i++) {
		int exchange = 0;           //記錄這一輪會(huì)不會(huì)有數(shù)據(jù)的交換；
		for (j = 0; j < m-1; j++) {
			if (arr[j] > arr[j + 1]) {
				temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;
				exchange = 1;
			}
		}
		m--;
		if (!exchange)  //若沒有數(shù)據(jù)的交換，則數(shù)據(jù)已經(jīng)排列完畢，跳出循環(huán)；
			break;
	}
	for (i = 0; i < n; i++) {
		printf("%d ", arr[i]);        //輸出
	}
 
	return 0;
 
}

2.快速排序（Quick Sort）

快速排序是這五類中平均性能最優(yōu)的排序算法，其中運(yùn)用了分治的思想，并且調(diào)用了遞歸函數(shù)，因此也是這五類中最難的一個(gè)。

基本思想：

快速排序的重點(diǎn)在于找一個(gè)基準(zhǔn)值，將數(shù)列分為兩部分——大于基準(zhǔn)值的放在右邊，小于基準(zhǔn)值的放在左邊。然后分別對(duì)這兩部分重復(fù)次操作，一分為二，二分為四······直到每個(gè)元素自成一部分。

1.將數(shù)據(jù)的中間元素設(shè)為基準(zhǔn)值，初始化令指向最左邊個(gè)元素，令指向最右邊個(gè)元素，通過從左往右找一個(gè)大于基準(zhǔn)數(shù)的數(shù)，通過從右往左找一個(gè)小于基準(zhǔn)數(shù)的數(shù)，交換兩數(shù)的位置，直到。

2.如此不斷的細(xì)分遞歸，達(dá)到排序的目的

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

#include<stdio.h>
 
void Quicksort(int a[], int left, int right) {   //快排函數(shù)
    int temp;
    int mid = a[(left + right) / 2];            //找基準(zhǔn)值
    int i = left;
    int j = right;
//在左側(cè)找一個(gè)大于基準(zhǔn)值的數(shù)，在右側(cè)找一個(gè)小于基準(zhǔn)數(shù)的數(shù)，然后交換位置
    while (i <= j) {   
        while (a[i] < mid) i++;
        while (a[j] > mid) j--;
        if (i <= j) {
            temp = a[i];
            a[i] = a[j];
            a[j] = temp;
            i++;
            j--;
        }
    }
    if (i < right) Quicksort(a, i, right);        //遞歸
    if (j > left) Quicksort(a, left, j);           //遞歸
}
 
int main() {
    int n, m, i;
    int arr[100];
    scanf_s("%d", &n);
    for (i = 0; i < n; i++) {
        scanf_s("%d", &arr[i]);                        //輸入
    }
 
    Quicksort(arr, 0, n - 1);                        //調(diào)用函數(shù)
 
    for (i = 0; i < n; i++) {
        printf("%d ", arr[i]);                        //輸出
    }
    return 0;
}

3.插入排序（Insertion Sort）

基本思想：

將數(shù)據(jù)分為兩組——一組是有序的，一組是無(wú)序的，將無(wú)序數(shù)據(jù)中的元素依次插入到有序數(shù)據(jù)中，從而將整個(gè)數(shù)據(jù)變?yōu)橛行虻模ㄟ@里的分組是潛意識(shí)的，實(shí)際上并不會(huì)用兩個(gè)數(shù)組來(lái)分）

1.初始時(shí)，將第一個(gè)元素分為有序組（因?yàn)橹挥幸粋€(gè)元素，所以認(rèn)為它是排好序的），其余元素分為無(wú)序組

2.因此只需從第二個(gè)元素開始，依次在有序組中找到自己的位置，插入即可，直到最后一個(gè)元素。

3.但這并不意味著只需要一次循環(huán)，因?yàn)樵?ldquo;找自己的位置”的過程中，需要將自己與前面的元素相比較，若是自己較小，則將那個(gè)元素后移一位；若是自己較大，則將自己插入到上一次比較的位置

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

#include<stdio.h>
 
int main() {
    int n, m, i, j, temp;
    int arr[100];
 
    scanf_s("%d", &n);
    for (i = 0; i < n; i++) {
        scanf_s("%d", &arr[i]);                        //輸入 
    }
    for(i=1; i<n; i++)                                //從無(wú)序組的第一個(gè)元素開始 
        if(arr[i] < arr[i-1])                           // 判斷是否要向前尋找插入的位置 
        {
            int temp = arr[i];                       
            for(j=i-1; j>=0 && arr[j]>temp; j--)    //將大于自己的數(shù)依次向后挪位 
                arr[j+1] = arr[j];                    
            arr[j+1] = temp;                       //插入 
        }
    for (i = 0; i < n; i++) {
        printf("%d ", arr[i]);                        //輸出 
    }
    return 0;
}

4.簡(jiǎn)單選擇排序（Simple Selection Sort）

基本思想：

設(shè)一個(gè)數(shù)據(jù)集有n個(gè)元素，選擇這n個(gè)元素中最小的一個(gè)與第一個(gè)元素交換位置，再在剩下的n-1個(gè)元素中選擇最小的一個(gè)與第二個(gè)元素交換位置，直到在最后兩個(gè)元素中選擇最小的一個(gè)放在倒數(shù)第二的位置上，排序完成。

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

#include<stdio.h>
 
int main() {
    int n, m, i, j, p, temp;
    int arr[100];
 
    scanf_s("%d", &n);
    for (i = 0; i < n; i++) {
        scanf_s("%d", &arr[i]);                        //輸入 
    }
 
    for (i = 0; i < n - 1; i++) {
        p = i;                            //p用于記錄最小元素的下標(biāo)
        for (j = i + 1; j < n; j++) {       //找到剩下元素中最小的那一個(gè)
            if (arr[p] > arr[j])
                p = j;
        }
        temp = arr[i];                        //temp是交換兩數(shù)時(shí)的中間變量
        arr[i] = arr[p];
        arr[p] = temp;
    }
    for (i = 0; i < n; i++) {
        printf("%d ", arr[i]);                        //輸出 
    }
    return 0;
}

5.希爾排序（Shell Sort）

希爾排序是插入排序的優(yōu)化，它先將待排序列進(jìn)行預(yù)排序，然后對(duì)次序列進(jìn)行一次插入排序，不一樣的是經(jīng)過預(yù)處理之后的插入排序時(shí)間復(fù)雜度為

基本思想：

定義一個(gè)間隔gap，在一組數(shù)據(jù)中，將相隔為gap的元素作為一個(gè)組，對(duì)組內(nèi)元素執(zhí)行簡(jiǎn)單的插入排序，然后不斷縮小gap重復(fù)此操作，完成數(shù)據(jù)的預(yù)處理，直到gap=1，表示對(duì)所有數(shù)進(jìn)行插入排序，算法終止。

1.初始化（n為元素個(gè)數(shù)），將數(shù)據(jù)中所有距離為gap的元素分在一組（此時(shí)這組數(shù)據(jù)會(huì)被分成個(gè)組，每組有兩個(gè)元素，對(duì)每個(gè)組進(jìn)行排序）

2.接著縮小gap至，將數(shù)據(jù)中所有距離為gap的元素分在一組（此時(shí)這組數(shù)據(jù)會(huì)被分成個(gè)組，每組有四個(gè)元素，對(duì)每個(gè)組進(jìn)行排序）

3.重復(fù)直到gap=1，此時(shí)數(shù)據(jù)為一組，有n個(gè)元素，簡(jiǎn)單插入排序即可。

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

#include<stdio.h>
 
int main() {
    int n, m, i, j, temp,gap;
    int arr[100];
 
    scanf("%d", &n);
    for (i = 0; i < n; i++) {
        scanf("%d", &arr[i]);                        //輸入
    }
 
    for(gap=n/2; gap>0; gap/=2)
        for(i=gap; i<n; i++)
            for(j=i-gap; j>=0 && arr[j]>arr[j+gap]; j-=gap){
                temp=arr[j];
                arr[j]=arr[j+gap];
                arr[j+gap]=temp;
            }
    for (i = 0; i < n; i++) {
        printf("%d ", arr[i]);                        //輸出
    }
    return 0;
}