冒泡法排序C語言

一、冒泡排序基礎概念

冒泡排序是一種簡單的排序算法，通過重複比較相鄰的元素，依次將未排序的最大（或最小）元素放在已排序的末尾，一直到全部元素均排序完成。由於排序過程中元素位置的像泡泡一樣“冒”到頂部，因此得名為冒泡排序。它是一種穩定排序算法，時間複雜度最好為O(n)，最壞為O(n^2)。

二、冒泡排序步驟詳解

冒泡排序的基本原理是重複走訪要排序的數列，一次比較兩個元素，如果它們的順序錯誤就交換它們的位置。具體步驟如下：

Step 1：從數列的第一個元素開始，比較每一對相鄰元素，如果前一個元素大於後一個元素，交換位置。

Step 2：重複執行Step 1直到最後一個元素，這樣最後一個元素的位置就是數列中最大的元素。

Step 3：對除了已經排序的最後一個元素以外的所有元素執行Step 1和Step 2，直到整個數列排序完成。

三、基礎版冒泡排序代碼示例

#include <stdio.h>

int main()
{
    int array[100], n, i, j, temp;

    printf("Enter number of elements: ");
    scanf("%d", &n);

    printf("Enter %d elements:\n", n);
    for(i = 0; i < n; i++)
    {
        scanf("%d", &array[i]);
    }

    for(i = 0; i < n-1; i++)
    {
        for(j = 0; j  array[j+1])
            {
                temp = array[j];
                array[j] = array[j+1];
                array[j+1] = temp;
            }
        }
    }

    printf("Sorted list in ascending order:\n");
    for(i = 0; i < n; i++)
    {
        printf("%d\n", array[i]);
    }

    return 0;
}

以上是一個基礎版的冒泡排序C語言代碼示例，主體框架是使用兩個for循環來完成排序。外循環用來控制比較次數，內循環用來比較相鄰元素大小並按照順序交換位置。

四、優化版冒泡排序實現細節

冒泡排序在實現的過程中，存在一些可以優化的細節，可以提高排序的效率。

第一點：對於一個有序數列，可以提前結束冒泡排序。

因為已經排序完成，不需要再繼續執行比較和交換操作，直接退出冒泡排序。在優化版冒泡排序中，用一個標記來判斷數列是否有序，如果有序就直接結束排序。

第二點：對於大部分已經有序的數列，冒泡排序可以提前終止，避免不必要的比較和交換操作。

在優化版冒泡排序中，用一個變量記錄最後一次交換的位置，因為此位置後面的元素已經排好序，不需要再進行比較和交換操作。

五、優化版冒泡排序代碼示例

#include <stdio.h>

int main()
{
    int array[100], n, i, j, temp, flag = 1, k;

    printf("Enter number of elements: ");
    scanf("%d", &n);

    printf("Enter %d elements:\n", n);
    for(i = 0; i < n; i++)
    {
        scanf("%d", &array[i]);
    }

    for(i = 0; i < n-1 && flag == 1; i++)
    {
        flag = 0;
        for(j = 0; j  array[j+1])
            {
                temp = array[j];
                array[j] = array[j+1];
                array[j+1] = temp;
                flag = 1; // 標記有序性
                k = j; // 記錄最後一次交換的位置
            }
        }
        n = k + 1; // 優化：減少比較次數
    }

    printf("Sorted list in ascending order:\n");
    for(i = 0; i < n; i++)
    {
        printf("%d\n", array[i]);
    }

    return 0;
}

以上是一個優化版的冒泡排序C語言代碼示例，通過使用標記和記錄最後一次交換的位置來優化排序效率。同時，可以通過減少比較次數的方式進一步優化。

六、結語

冒泡排序是一種簡單但常用的排序算法，在實際開發中經常使用。通過本文的介紹，你可以更好地了解冒泡排序的基本概念和算法步驟，並掌握優化版冒泡排序的實現細節和優化方法。希望這篇文章能夠對你的學習和工作有所幫助。