冒泡、選擇、插入排序算法(c語言)實作

幾種常見排序算法的實作

一、冒泡排序

1.百度百科

冒泡排序（Bubble Sort），是一種計算機科學領域的較簡單的排序算法。它重複地走訪過要排序的元素列，依次比較兩個相鄰的元素，如果順序（如從大到小、首字母從Z到A）錯誤就把他們交換過來。走訪元素的工作是重複地進行直到沒有相鄰元素需要交換，也就是說該元素列已經排序完成。這個算法的名字由來是因為越小的元素會經由交換慢慢“浮”到數列的頂端（升序或降序排列），就如同碳酸飲料中二氧化碳的氣泡最終會上浮到頂端一樣，故名“冒泡排序”。

2.C語言實作

分别定義兩個函數(從小到大排序)

//冒泡(一輪冒泡之後，數組的最後一個為最大值)
void Bubble(int arr[], int n){
    for(int i = 0; i < n-1; i++){
        int temp;
        if(arr[i] > arr[i+1]){
            temp = arr[i];
            arr[i] = arr[i+1];
            arr[i+1] = temp;
        }
    }
}
//冒泡排序
void bubbleSorrt(int arr[], int n){
    for(int i = n; i > 0; i--){
        Bubble(arr, i);
    }
           

for循環嵌套實作

//冒泡排序
void bubbleSorrt(int arr[], int n){
    for(int i = 0; i < n-1; i++)//控制冒泡的輪數
    {
        for(int j = 0; j < n-1-i; j++)//控制每一輪冒泡數組元素交換的次數
        {
            int temp;
            if(arr[j] > arr[j+1]){
                temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}
           

示例

#include <stdio.h>

//冒泡(一輪冒泡之後，數組的最後一個為最大值)
void Bubble(int arr[], int n){
    for(int i = 0; i < n-1; i++){
        int temp;
        if(arr[i] > arr[i+1]){
            temp = arr[i];
            arr[i] = arr[i+1];
            arr[i+1] = temp;
        }
    }
}
//冒泡排序
void bubbleSorrt(int arr[], int n){
    // for(int i = n; i > 0; i--){
    //     Bubble(arr, i);
    // }
    for(int i = 0; i < n-1; i++)//控制冒泡的輪數
    {
        for(int j = 0; j < n-1-i; j++)//控制每一輪一輪冒泡的次數，每一輪減一次
        {
            int temp;
            if(arr[j] > arr[j+1]){
                temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}

int main(){
    int arr[7] = {6, 7, 5, 8, 4, 2, 9};
    bubbleSorrt(arr, 7);
    for(int i = 0; i < 7; i++){
        printf("%d ", arr[i]);
    }
    printf("\n");
}
           

二、選擇排序

1.百度百科

選擇排序（Selection sort）是一種簡單直覺的排序算法。它的工作原理是：第一次從待排序的資料元素中選出最小（或最大）的一個元素，存放在序列的起始位置，然後再從剩餘的未排序元素中尋找到最小（大）元素，然後放到已排序的序列的末尾。以此類推，直到全部待排序的資料元素的個數為零。選擇排序是不穩定的排序方法。

2.圖解

紅色表示目前最小值，黃色表示已排序序列，藍色表示目前位置。

3.C語言實作

定義兩個函數

//找到最大值的位置(從小到大排序)
int findMaxPos(int arr[], int n){
    int Max_pos = 0;
    int max = arr[Max_pos];
    for(int i = 0; i < n; i++){
        if(arr[i] > max){
            max = arr[i];
            Max_pos = i;
        }
    }
    return Max_pos;
}
//找到最小值的位置(從大到小排序)
int findMinPos(int arr[], int n){
    int Min_pos = 0;
    int min = arr[Min_pos];
    for(int i = 0; i < n; i++){
        if(arr[i] < min){
            min = arr[i];
            Min_pos = i;
        }
    }
    return Min_pos;
}

//選擇排序
void selectionSort(int arr[], int n){
    for(int i = n; i > 0; i--){
        int pos = findMinPos(arr, i);//i表示這個數組的大小
        int temp = arr[pos];
        arr[pos] = arr[i-1];
        arr[i-1] = temp;//将最大值與末項交換位置
    }
}
           

示例

#include <stdio.h>

//找到最小值的位置(從大到小排序)
int findMinPos(int arr[], int n){
    int Min_pos = 0;
    int min = arr[Min_pos];
    for(int i = 0; i < n; i++){
        if(arr[i] < min){
            min = arr[i];
            Min_pos = i;
        }
    }
    return Min_pos;
}

//選擇排序
void selectionSort(int arr[], int n){
    for(int i = n; i > 0; i--){
        int pos = findMinPos(arr, i);//改變排列順序隻需改變函數名
        int temp = arr[pos];
        arr[pos] = arr[i-1];
        arr[i-1] = temp;//将最大(小)值與末項交換位置
    }
}

int main(){
    int arr[8] = {6, 7, 10, 11, 4, 11, 9, 7};
    selectionSort(arr, 8);
    for(int i = 0; i < 8; i++){
        printf("%d ", arr[i]);
    }
    printf("\n");
}
           

三、插入排序

1.維基百科

插入排序（英語：Insertion Sort）是一種簡單直覺的排序算法。它的工作原理是通過建構有序序列，對于未排序資料，在已排序序列中從後向前掃描，找到相應位置并插入。插入排序在實作上，通常采用in-place排序（即隻需用到O(1)的額外空間的排序），因而在從後向前掃描過程中，需要反複把已排序元素逐漸向後挪位，為最新元素提供插入空間。

2.圖解

3.代碼實作

//插入排序
void insertionSort(int arr[], int len){
    for(int i = 1; i < len; i++){
        int pos = i;//pos表示要插入的元素的位置
        int key = arr[pos];//key表示要插入的元素,整個插入過程不會更改
        while(arr[pos-1] > key && pos > 0){
            arr[pos] = arr[pos-1];
            pos--;//位置向前移動一位繼續比較
        }
        arr[pos] = key;//将要插入的元素繼續儲存在pos位置上
    }
}
           

示例

#include <stdio.h>

//插入排序
void insertionSort(int arr[], int len){
    for(int i = 1; i < len; i++){
        int pos = i;//pos表示要插入的元素的位置
        int key = arr[pos];//key表示要插入的元素
        while(arr[pos-1] > key && pos > 0){
            arr[pos] = arr[pos-1];
            pos--;//位置向前移動一位繼續比較
        }
        arr[pos] = key;//将要插入的元素繼續儲存在pos位置上
    }
}

int main(){
    int arr[12] = {6, 7, 10, 11, 4, 11, 9, 7, 3, 1, 8, 0};
    insertionSort(arr, 12);
    for(int i = 0; i < 12; i++){
        printf("%d ", arr[i]);
    }
    printf("\n");
}