快捷導(dǎo)航

C語言中的5種簡單排序算法(適合小白)

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

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

基本概要：

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

1.冒泡排序（Bubble Sort）

基本思想：

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

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

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

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

代碼實現(xiàn)：

#include<stdio.h>
 
int main() {
	int n, m, i, j, temp;
	int arr[100];
 
	scanf_s("%d", &n);    //scnaf_s是更為安全的輸入方式；n為元素的個數(shù)；
	for (i = 0; i < n; i++) {
		scanf_s("%d", &arr[i]);    //輸入數(shù)據(jù)；
	}
 
	m = n;            //因為每進行一次第一輪循環(huán)，需要排序的數(shù)據(jù)都要“--”，因此定義變量m=n；
	for (i = 0; i < n; i++) {
		int exchange = 0;           //記錄這一輪會不會有數(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)的排序算法，其中運用了分治的思想，并且調(diào)用了遞歸函數(shù)，因此也是這五類中最難的一個。

基本思想：

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

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

2.如此不斷的細分遞歸，達到排序的目的

代碼實現(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è)找一個大于基準(zhǔn)值的數(shù)，在右側(cè)找一個小于基準(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ù)分為兩組——一組是有序的，一組是無序的，將無序數(shù)據(jù)中的元素依次插入到有序數(shù)據(jù)中，從而將整個數(shù)據(jù)變?yōu)橛行虻模ㄟ@里的分組是潛意識的，實際上并不會用兩個數(shù)組來分）

1.初始時，將第一個元素分為有序組（因為只有一個元素，所以認為它是排好序的），其余元素分為無序組

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

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

代碼實現(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++)                                //從無序組的第一個元素開始 
        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.簡單選擇排序（Simple Selection Sort）

基本思想：

設(shè)一個數(shù)據(jù)集有n個元素，選擇這n個元素中最小的一個與第一個元素交換位置，再在剩下的n-1個元素中選擇最小的一個與第二個元素交換位置，直到在最后兩個元素中選擇最小的一個放在倒數(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++) {       //找到剩下元素中最小的那一個
            if (arr[p] > arr[j])
                p = j;
        }
        temp = arr[i];                        //temp是交換兩數(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)化，它先將待排序列進行預(yù)排序，然后對次序列進行一次插入排序，不一樣的是經(jīng)過預(yù)處理之后的插入排序時間復(fù)雜度為

基本思想：

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

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

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

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

代碼實現(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;
}