国产 无码 综合区,色欲AV无码国产永久播放,无码天堂亚洲国产AV,国产日韩欧美女同一区二区

  1. Toy模板網(wǎng)首頁(yè)
  2. >Toy博客

【C語(yǔ)言】解析C語(yǔ)言實(shí)現(xiàn)排序的算法（冒泡排序、插入排序、選擇排序、快速排序、歸并排序）

2年前作者：嵌入式小白—小黑分類：Toy博客閱讀(22)違法舉報(bào)

這篇具有很好參考價(jià)值的文章主要介紹了【C語(yǔ)言】解析C語(yǔ)言實(shí)現(xiàn)排序的算法（冒泡排序、插入排序、選擇排序、快速排序、歸并排序）。希望對(duì)大家有所幫助。如果存在錯(cuò)誤或未考慮完全的地方，請(qǐng)大家不吝賜教，您也可以點(diǎn)擊"舉報(bào)違法"按鈕提交疑問(wèn)。

本博客主要圍繞五種常見的排序算法展開討論，包括選擇排序、快速排序、歸并排序、冒泡排序和插入排序。針對(duì)每種算法，我對(duì)其思想、特點(diǎn)、時(shí)間復(fù)雜度、穩(wěn)定性以及優(yōu)缺點(diǎn)進(jìn)行了詳細(xì)解釋和比較。

1.冒泡排序

冒泡排序算法是一種簡(jiǎn)單且常用的排序算法。它通過(guò)重復(fù)地交換相鄰的元素，將較大的元素逐漸"浮"到數(shù)列的末尾。

1.1 算法思想:

冒泡排序的核心思想是在每一輪遍歷中，比較相鄰的兩個(gè)元素，如果順序有誤則進(jìn)行交換。通過(guò)多輪的遍歷，將最大（或最小）的元素逐漸“冒泡”到數(shù)組的最后（或最前），從而實(shí)現(xiàn)排序。

1.2 代碼實(shí)現(xiàn):

#include <stdio.h>

// 冒泡排序函數(shù)
void bubbleSort(int arr[], int n) {
    int i, j;
    for (i = 0; i < n - 1; i++) {
        // 每一輪遍歷
        for (j = 0; j < n - i - 1; j++) {
            // 比較相鄰的兩個(gè)元素
            if (arr[j] > arr[j + 1]) {
                // 交換元素
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]);

    bubbleSort(arr, n);

    printf("排序后的數(shù)組：\n");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

1.3 解析代碼:

  1. 首先，我們?cè)陬^文件中引入了<stdio.h>，以便使用printf函數(shù)。
  2. 接著，在bubbleSort函數(shù)中，使用兩個(gè)嵌套的循環(huán)進(jìn)行遍歷。外部循環(huán)i控制遍歷的輪數(shù)，內(nèi)部循環(huán)j用于比較相鄰元素并進(jìn)行交換。
  3. 內(nèi)部循環(huán)中，我們通過(guò)arr[j]和arr[j + 1]的比較來(lái)判斷是否需要交換元素。
  4. 如果arr[j]大于arr[j + 1]，則交換兩個(gè)元素的值。通過(guò)使用一個(gè)臨時(shí)變量temp，我們可以完成交換操作。
  5. 在main函數(shù)中，我們定義一個(gè)待排序的整數(shù)數(shù)組arr，并計(jì)算數(shù)組的長(zhǎng)度n。
  6. 使用bubbleSort函數(shù)對(duì)數(shù)組進(jìn)行排序。
  7. 最后，我們通過(guò)printf函數(shù)輸出排序后的數(shù)組。

1.4 示例輸出:

排序后的數(shù)組：
11 12 22 25 34 64 90

1.5總結(jié):

冒泡排序是一種簡(jiǎn)單但效率較低的排序算法，在處理小型數(shù)據(jù)集時(shí)比較適用。通過(guò)重復(fù)交換相鄰元素實(shí)現(xiàn)排序，冒泡排序的時(shí)間復(fù)雜度為O(n^2)。

2. 插入排序

插入排序是一種簡(jiǎn)單且直觀的排序算法，它通過(guò)構(gòu)建有序序列來(lái)逐步插入元素，最終完成整個(gè)數(shù)組的排序。下面是插入排序的解析、代碼和解釋：

2.1 算法思想：

插入排序的核心思想是，將數(shù)組分為已排序和未排序兩部分。初始時(shí)，將第一個(gè)元素視為已排序部分，然后逐個(gè)遍歷未排序部分的元素，將每個(gè)元素插入到已排序部分的正確位置。插入過(guò)程中，需要不斷地向前比較已排序部分的元素，找到插入位置以保持已排序部分的有序性。

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

#include <stdio.h>

void insertionSort(int arr[], int n) {
    int i, j, key;
    for (i = 1; i < n; i++) {
        key = arr[i];
        j = i - 1;

        // 將arr[0...i-1]中大于key的元素向后移動(dòng)
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }

        arr[j + 1] = key;
    }
}

int main() {
    int arr[] = {12, 11, 13, 5, 6};
    int n = sizeof(arr) / sizeof(arr[0]);

    insertionSort(arr, n);

    printf("排序后的數(shù)組：\n");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

2.3 解析代碼：

  1. 在插入排序的insertionSort函數(shù)中，我們使用一個(gè)循環(huán)從第二個(gè)元素開始遍歷整個(gè)數(shù)組。
  2. 對(duì)于每個(gè)元素，我們將其賦值給key變量，并且使用一個(gè)變量j來(lái)追蹤插入位置。
  3. 然后，在內(nèi)部循環(huán)中，我們將已排序部分大于key的元素向后移動(dòng)一位，為插入key創(chuàng)造空間。
  4. 這里使用了一個(gè)自減的while循環(huán)來(lái)將元素向后移動(dòng)，直到找到插入位置。
  5. 最后，將key插入到arr[j+1]的位置，保證已排序部分仍然有序。
  6. 在main函數(shù)中，我們定義了一個(gè)待排序的整數(shù)數(shù)組arr，并計(jì)算數(shù)組的長(zhǎng)度n。
  7. 使用insertionSort函數(shù)對(duì)數(shù)組進(jìn)行排序。
  8. 最后，通過(guò)printf函數(shù)輸出排序后的數(shù)組。

2.4 示例輸出：

排序后的數(shù)組：
5 6 11 12 13

2.5 總結(jié)：

插入排序是一種簡(jiǎn)單但有效的排序算法，適用于小規(guī)模數(shù)組或部分有序的情況。它的時(shí)間復(fù)雜度為O(n^2)，可以穩(wěn)定地將數(shù)組排序。

3. 選擇排序

選擇排序是一種簡(jiǎn)單直觀的排序算法，它每次在未排序的部分中選擇最?。ɑ蜃畲螅┑脑?，并將其放置在已排序部分的末尾。下面是選擇排序的解析、代碼和解釋：

3.1 算法思想：

選擇排序的核心思想是將數(shù)組分為已排序和未排序兩部分。初始狀態(tài)下，整個(gè)數(shù)組都是未排序的。每一次循環(huán)中，從未排序部分中選擇最?。ɑ蜃畲螅┑脑?，然后將其放置到已排序部分的末尾，直到所有元素都被放置到正確的位置上。

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

#include <stdio.h>

void selectionSort(int arr[], int n) {
    int i, j, minIndex, temp;
    for (i = 0; i < n - 1; i++) {
        minIndex = i;
        // 在未排序部分中找到最小元素的索引
        for (j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        // 將最小元素與未排序部分的第一個(gè)元素交換位置
        temp = arr[minIndex];
        arr[minIndex] = arr[i];
        arr[i] = temp;
    }
}

int main() {
    int arr[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr) / sizeof(arr[0]);

    selectionSort(arr, n);

    printf("排序后的數(shù)組：\n");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

3.3 解析代碼：

  1. 在選擇排序的selectionSort函數(shù)中，通過(guò)兩層循環(huán)實(shí)現(xiàn)排序。
  2. 外層循環(huán)從數(shù)組的第一個(gè)元素開始，到倒數(shù)第二個(gè)元素結(jié)束。表示已排序部分的范圍。
  3. 內(nèi)層循環(huán)從外層循環(huán)的下一個(gè)元素開始，到最后一個(gè)元素結(jié)束。用于在未排序的部分中找到最小元素的索引。
  4. 在內(nèi)層循環(huán)中，通過(guò)比較找到未排序部分的最小元素的索引，并將其賦值給minIndex。
  5. 然后，在外層循環(huán)中，將最小元素與未排序部分的第一個(gè)元素進(jìn)行交換。
  6. 通過(guò)使用一個(gè)臨時(shí)變量temp來(lái)實(shí)現(xiàn)元素交換的過(guò)程。
  7. 循環(huán)繼續(xù)，直到已排序部分包含所有元素。
  8. 在main函數(shù)中，定義待排序的整數(shù)數(shù)組arr，并計(jì)算數(shù)組的長(zhǎng)度n。
  9. 使用selectionSort函數(shù)對(duì)數(shù)組進(jìn)行排序。
  10. 最后，通過(guò)printf函數(shù)輸出排序后的數(shù)組。

3.4 示例輸出：

排序后的數(shù)組：
11 12 22 25 64

3.5 總結(jié)：

選擇排序是一種簡(jiǎn)單但效率較低的排序算法，適用于數(shù)據(jù)量較小的情況。它的時(shí)間復(fù)雜度為O(n^2)，可以穩(wěn)定地將數(shù)組排序。

4 快速排序

快速排序是一種基于分治思想的高效排序算法，通過(guò)選擇一個(gè)基準(zhǔn)元素，將數(shù)組分成左右兩部分，并遞歸地對(duì)這兩部分進(jìn)行排序，最終完成整個(gè)數(shù)組的排序。下面是快速排序的解析、代碼和解釋：

4.1 算法思想：

快速排序的核心思想是選取一個(gè)基準(zhǔn)元素，將數(shù)組分為兩個(gè)子數(shù)組，左邊的子數(shù)組中的元素都小于等于基準(zhǔn)元素，右邊的子數(shù)組中的元素都大于等于基準(zhǔn)元素。然后，對(duì)左右兩個(gè)子數(shù)組分別遞歸地進(jìn)行快速排序，直到子數(shù)組的長(zhǎng)度為1或0，即可完成排序。

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

#include <stdio.h>

void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

int partition(int arr[], int low, int high) {
    int pivot = arr[high];  // 選擇最后一個(gè)元素作為基準(zhǔn)
    int i = (low - 1);

    for (int j = low; j <= high - 1; j++) {
        // 將小于等于基準(zhǔn)的元素交換到左邊子數(shù)組
        if (arr[j] <= pivot) {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    // 將基準(zhǔn)元素放置到正確的位置
    swap(&arr[i + 1], &arr[high]);
    return (i + 1);
}

void quickSort(int arr[], int low, int high) {
    if (low < high) {
        // 劃分?jǐn)?shù)組并獲取基準(zhǔn)元素的位置
        int pivotIndex = partition(arr, low, high);

        // 分別對(duì)左右兩個(gè)子數(shù)組進(jìn)行快速排序
        quickSort(arr, low, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, high);
    }
}

int main() {
    int arr[] = {10, 7, 8, 9, 1, 5};
    int n = sizeof(arr) / sizeof(arr[0]);

    quickSort(arr, 0, n - 1);

    printf("排序后的數(shù)組：\n");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

4.3 解析代碼：

  1. 借助swap函數(shù)實(shí)現(xiàn)元素交換操作。
  2. 在partition函數(shù)中，選擇數(shù)組的最后一個(gè)元素作為基準(zhǔn)pivot。
  3. 使用變量i來(lái)追蹤小于等于基準(zhǔn)的元素位置。
  4. 使用循環(huán)逐個(gè)遍歷當(dāng)前數(shù)組，并將小于等于基準(zhǔn)的元素交換到左邊子數(shù)組。
  5. 最后，將基準(zhǔn)元素放置到正確的位置上，并返回其位置作為劃分點(diǎn)。
  6. 在quickSort函數(shù)中，通過(guò)遞歸調(diào)用快速排序來(lái)分別對(duì)左右兩個(gè)子數(shù)組進(jìn)行排序。
  7. 遞歸基準(zhǔn)為子數(shù)組長(zhǎng)度為1或0的情況，這時(shí)子數(shù)組已經(jīng)是有序的。
  8. 在main函數(shù)中，定義待排序的整數(shù)數(shù)組arr，并計(jì)算數(shù)組的長(zhǎng)度n。
  9. 使用quickSort函數(shù)對(duì)數(shù)組進(jìn)行排序。
  10. 最后，通過(guò)printf函數(shù)輸出排序后的數(shù)組。

4.4 示例輸出：

排序后的數(shù)組：
1 5 7 8 9 10

4.5 總結(jié)：

快速排序是一種高效且常用的排序算法，它的平均時(shí)間復(fù)雜度為O(nlogn)，在大多數(shù)情況下可以快速地將數(shù)組排序。

5 歸并排序

歸并排序是一種基于分治思想的排序算法，它將數(shù)組遞歸地分為兩個(gè)子數(shù)組，然后將這兩個(gè)子數(shù)組排序，并將它們合并成一個(gè)有序數(shù)組。下面是歸并排序的解析、代碼和解釋：

5.1 算法思想：

歸并排序的核心思想是將數(shù)組遞歸地分成兩個(gè)子數(shù)組，直到每個(gè)子數(shù)組只包含一個(gè)元素。然后，通過(guò)將兩個(gè)有序的子數(shù)組合并，再逐層返回最終有序的數(shù)組。

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

#include <stdio.h>

void merge(int arr[], int left, int mid, int right) {
    int i, j, k;
    int n1 = mid - left + 1;   // 左子數(shù)組長(zhǎng)度
    int n2 = right - mid;      // 右子數(shù)組長(zhǎng)度

    // 創(chuàng)建臨時(shí)數(shù)組用于存儲(chǔ)左右子數(shù)組
    int L[n1], R[n2];

    // 將數(shù)據(jù)復(fù)制到臨時(shí)數(shù)組
    for (i = 0; i < n1; i++)
        L[i] = arr[left + i];
    for (j = 0; j < n2; j++)
        R[j] = arr[mid + 1 + j];

    // 將臨時(shí)數(shù)組中的元素按照順序合并到原數(shù)組中
    i = 0;   // 左子數(shù)組的下標(biāo)
    j = 0;   // 右子數(shù)組的下標(biāo)
    k = left;   // 合并后數(shù)組的下標(biāo)

    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    // 將剩余的元素復(fù)制到原數(shù)組中
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

void mergeSort(int arr[], int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;

        // 遞歸地對(duì)左右兩個(gè)子數(shù)組進(jìn)行歸并排序
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);

        // 合并排序后的子數(shù)組
        merge(arr, left, mid, right);
    }
}

int main() {
    int arr[] = {12, 11, 13, 5, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);

    mergeSort(arr, 0, n - 1);

    printf("排序后的數(shù)組：\n");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

5.3 解析代碼：

  1. 定義了一個(gè)merge函數(shù)，用于將兩個(gè)有序的子數(shù)組合并到原始數(shù)組中。
  2. 在merge函數(shù)中，使用兩個(gè)臨時(shí)數(shù)組L和R來(lái)分別存儲(chǔ)左子數(shù)組和右子數(shù)組的元素。
  3. 將左子數(shù)組和右子數(shù)組的元素按照順序合并到原數(shù)組中。
  4. 在mergeSort函數(shù)中，判斷左下標(biāo)left是否小于右下標(biāo)right，如果滿足條件，則進(jìn)行以下操作：
  5. 計(jì)算中間下標(biāo)mid，將數(shù)組劃分成兩個(gè)子數(shù)組。
  6. 分別遞歸地對(duì)左子數(shù)組和右子數(shù)組進(jìn)行歸并排序。
  7. 最后，調(diào)用merge函數(shù)將排序后的子數(shù)組合并。
  8. 在main函數(shù)中，定義待排序的整數(shù)數(shù)組arr，并計(jì)算數(shù)組的長(zhǎng)度n。
  9. 使用mergeSort函數(shù)對(duì)數(shù)組進(jìn)行排序。
  10. 最后，通過(guò)printf函數(shù)輸出排序后的數(shù)組。

5.4 示例輸出：

排序后的數(shù)組：
5 6 7 11 12 13

5.5 總結(jié)：

歸并排序是一種高效且穩(wěn)定的排序算法，它的時(shí)間復(fù)雜度為O(nlogn)，適用于各種規(guī)模的數(shù)組。歸并排序通過(guò)分治的思想，將排序問(wèn)題劃分為小問(wèn)題，并最終合并結(jié)果。

歸納比較

下面是對(duì)選擇排序、快速排序、歸并排序、冒泡排序和插入排序進(jìn)行歸納和比較，包括它們各自的優(yōu)點(diǎn)和缺點(diǎn)：

算法 優(yōu)點(diǎn) 缺點(diǎn)
冒泡排序 簡(jiǎn)單，容易實(shí)現(xiàn)穩(wěn)定，相同元素的相對(duì)順序不會(huì)改變。 時(shí)間復(fù)雜度較高，為O(n^2)，效率較低。不適用于大規(guī)模數(shù)據(jù)排序。
插入排序 對(duì)小規(guī)模或部分有序的數(shù)組具有較好的性能。原地排序，不需要額外的空間。 平均時(shí)間復(fù)雜度為O(n^2)，效率較低。對(duì)于大規(guī)模數(shù)據(jù)排序，性能較差。
選擇排序 簡(jiǎn)單、容易實(shí)現(xiàn)，對(duì)于小數(shù)據(jù)集，排序性能還可以接受。 時(shí)間復(fù)雜度較高，為O(n^2)，效率較低。不穩(wěn)定，相同元素可能發(fā)生位置交換。
快速排序 平均情況下具有較好的時(shí)間復(fù)雜度，為O(nlogn)。原地排序，不需要額外的空間。在大多數(shù)情況下表現(xiàn)良好，是最常用的排序算法之一。 最壞情況下的時(shí)間復(fù)雜度為O(n^2)。不穩(wěn)定，相同元素可能發(fā)生位置交換。
歸并排序 始終具有O(nlogn)的時(shí)間復(fù)雜度，穩(wěn)定且高效。技術(shù)復(fù)雜度低，易于理解和實(shí)現(xiàn)。穩(wěn)定，相同元素的相對(duì)順序不會(huì)改變。 需要額外的空間來(lái)存儲(chǔ)臨時(shí)數(shù)組，非原地排序。

總結(jié)：文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-646929.html

  • 選擇排序和冒泡排序簡(jiǎn)單易實(shí)現(xiàn)，但時(shí)間復(fù)雜度較高，適用于小規(guī)模數(shù)據(jù)。
  • 快速排序和歸并排序具有較好的平均時(shí)間復(fù)雜度，適用于各種規(guī)模的數(shù)據(jù)。
  • 歸并排序是穩(wěn)定的，快速排序和選擇排序是不穩(wěn)定的。
  • 插入排序?qū)π∫?guī)?；虿糠钟行虻臄?shù)據(jù)具有較好的性能。
  • 冒泡排序和插入排序都是原地排序算法，不需要額外的空間。

到了這里，關(guān)于【C語(yǔ)言】解析C語(yǔ)言實(shí)現(xiàn)排序的算法（冒泡排序、插入排序、選擇排序、快速排序、歸并排序）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！

本文來(lái)自互聯(lián)網(wǎng)用戶投稿，該文觀點(diǎn)僅代表作者本人，不代表本站立場(chǎng)。本站僅提供信息存儲(chǔ)空間服務(wù)，不擁有所有權(quán)，不承擔(dān)相關(guān)法律責(zé)任。如若轉(zhuǎn)載，請(qǐng)注明出處： 如若內(nèi)容造成侵權(quán)/違法違規(guī)/事實(shí)不符，請(qǐng)點(diǎn)擊違法舉報(bào)進(jìn)行投訴反饋，一經(jīng)查實(shí)，立即刪除！

領(lǐng)支付寶紅包贊助服務(wù)器費(fèi)用

相關(guān)文章

覺得文章有用就打賞一下文章作者

支付寶掃一掃打賞

博客贊助

微信掃一掃打賞

請(qǐng)作者喝杯咖啡吧~博客贊助

支付寶掃一掃領(lǐng)取紅包，優(yōu)惠每天領(lǐng)

二維碼1

領(lǐng)取紅包

二維碼2

領(lǐng)紅包