基礎資料結構及算法：簡單排序算法，包括選擇排序、插入排序、冒泡排序

文章目錄

- 1. 測試架構
- 2. 選擇排序
- 3. 插入排序
- 4. 冒泡排序

1. 測試架構

完成功能：

輸入數字 n，生成 n 個 0～n 的随機數
使用 qsort 升序排序
如果資料為升序則輸出 1，否則為 0

#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#include <stdbool.h>

void Random(int* arr,int n){
        srand(time(NULL));
        for(int i=0;i<n;++i){
                arr[i] = rand()%n;
        }
}

void PrintArr(int* arr,int n){
        for(int i=0;i<n;++i){
                printf("%d ",arr[i]);
        }
        printf("\n");
}

bool Ordered(int* arr,int n,bool asc){    // asc = true 表示為升序
        if(NULL == arr || n < 1) return false;
        if(1 == n) return true;
        for(int i=0;i<n-1;++i){
                if(asc){
                        if(arr[i] > arr[i+1]) return false;
                }else{
                        if(arr[i] < arr[i+1]) return false;
                }
        }
        return true;
}

int cmp(const void* a,const void* b){
        return *(int*)a - *(int*)b;
}

int main(){
        int n;
        scanf("%d",&n);
        int arr[n];
        Random(arr,n);
        PrintArr(arr,n);
        printf("%d\n",Ordered(arr,n,true));
        qsort(arr,n,sizeof(int),cmp);
        PrintArr(arr,n);
        printf("%d\n",Ordered(arr,n,true));
}

結果為：

30
18 8 7 9 23 18 20 29 13 16 27 9 29 23 27 10 0 12 23 15 9 12 1 25 3 15 29 0 19 19 
0
0 0 1 3 7 8 9 9 9 10 12 12 13 15 15 16 18 18 19 19 20 23 23 23 25 27 27 29 29 29 
1

2. 選擇排序

選擇排序排序思路：

找到數組中資料最大的數
把找到的最大的數和最後一個沒排好序的數交換位置
除了後面排好的數，剩下的數繼續完成上述操作

#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#include <stdbool.h>

void Random(int* arr,int n){
        srand(time(NULL));
        for(int i=0;i<n;++i){
                arr[i] = rand()%n;
        }
}

void PrintArr(int* arr,int n){
        for(int i=0;i<n;++i){
                printf("%d ",arr[i]);
        }
        printf("\n");
}

bool Ordered(int* arr,int n,bool asc){    // asc = true 表示為升序
        if(NULL == arr || n < 1) return false;
        if(1 == n) return true;
        for(int i=0;i<n-1;++i){
                if(asc){
                        if(arr[i] > arr[i+1]) return false;
                }else{
                        if(arr[i] < arr[i+1]) return false;
                }
        }
        return true;
}

/******************選擇排序******************/

//交換
void swap(int* p,int* q){
        int t = *p;
        *p = *q;
        *q = t;
}

//找到數組中最大的數
int FindMax(int* arr,int n){
        int index = 0;
        for(int i=0;i<n;++i){
                if(arr[index] < arr[i]){
                        index = i;
                }
        }
        return index;
}

/*
//把最大數和最後一個沒排好序的數交換（遞歸）
void SelectionSort(int* arr,int n){
        if(0 == n) return;
        int index = FindMax(arr,n);
        swap(arr+index,arr+n-1);
        SelectionSort(arr,n-1);   //遞歸
}
*/

//把最大數和最後一個沒排好序的數交換（疊代）
void SelectionSort(int* arr,int n){
        for(int i=0;i<n;++i){
                int index = FindMax(arr,n-i);   // 要判斷n-i次
                swap(arr+index,arr+n-1-i);     //要與第n-1-i個數交換
        }
}

int main(){
        int n;
        scanf("%d",&n);
        int arr[n];
        Random(arr,n);
        PrintArr(arr,n);
        printf("%d\n",Ordered(arr,n,true));
        SelectionSort(arr,n);  // 選擇排序
        PrintArr(arr,n);
        printf("%d\n",Ordered(arr,n,true));
}

結果為：

30
0 12 22 27 29 16 1 10 1 6 4 17 27 12 2 4 25 1 11 8 28 8 27 29 4 18 2 22 23 6 
0
0 1 1 1 2 2 4 4 4 6 6 8 8 10 11 12 12 16 17 18 22 22 23 25 27 27 27 28 29 29 
1

3. 插入排序

插入排序排序思路：

從前往後抽牌，抽到的數要往前面排好序的數字中插
插，有兩種方法：

第一種是從前往後，用抽到的數和數組中的數一一比較，找到第一個比抽到的這個數大的數，然後把包括這個數後面的數都向後移，把抽到的數放在這個位置上

第二種是從後往前，用抽到的數和數組中的數一一比較，如果比抽到的這個數大，則直接向後移一位，如果小于或等于抽到的這個數，則把抽到的這個數放在數組數後面一位

#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#include <stdbool.h>

void Random(int* arr,int n){
        srand(time(NULL));
        for(int i=0;i<n;++i){
                arr[i] = rand()%n;
        }
}

void PrintArr(int* arr,int n){
        for(int i=0;i<n;++i){
                printf("%d ",arr[i]);
        }
        printf("\n");
}

bool Ordered(int* arr,int n,bool asc){    // asc = true 表示為升序
        if(NULL == arr || n < 1) return false;
        if(1 == n) return true;
        for(int i=0;i<n-1;++i){
                if(asc){
                        if(arr[i] > arr[i+1]) return false;
                }else{
                        if(arr[i] < arr[i+1]) return false;
                }
        }
        return true;
}

/*****************插入排序********************/

/*
//從前往後找到數組中第一個大于摸到數，插到該位置上
void Insert(int* arr,int n){
        for(int i=0;i<n-1;++i){
                if(arr[n-1] < arr[i]){    //從前往後找第一個大于arr[n-1]的數
                        int last = arr[n-1];       //存下最後的數
                        for(int j=n-1;j>i;--j){      //後面的數往後一個一個移開
                                arr[j] = arr[j-1];     
                        }
                        arr[i] = last;         //把存下的數放在i位置上
                        break;
                }
        }
}
*/

//從後往前找小于等于摸到數的數，邊找邊移動，找到就放緊跟的位置
void Insert(int* arr,int n){
        int last = arr[n-1];
        for(int i=n-2;i>=0;--i){     //從後往前找一個小于等于arr[n-1]的數
                if(arr[i] > last){
                        arr[i+1] = arr[i];
                }else{
                        arr[i+1] = last;
                        return;
                }
        }
        arr[0] = last;  //如果整個數組沒有比last小的數，要做頭插操作
}

//從前往後摸牌操作
void InsertionSort(int* arr,int n){
        for(int i=1;i<=n;++i){
                Insert(arr,i);
        }
}

int main(){
        int n;
        scanf("%d",&n);
        int arr[n];
        Random(arr,n);
        PrintArr(arr,n);
        printf("%d\n",Ordered(arr,n,true));
        InsertionSort(arr,n);  // 插入排序
        PrintArr(arr,n);
        printf("%d\n",Ordered(arr,n,true));
}

結果為：

30
1 13 25 29 21 9 9 27 3 26 22 13 26 26 15 1 5 15 7 29 6 8 2 14 20 24 29 16 0 17 
0
0 1 1 2 3 5 6 7 8 9 9 13 13 14 15 15 16 17 20 21 22 24 25 26 26 26 27 29 29 29 
1

穩定性：兩個相等資料在排序前後是否改變原來的順序

選擇排序–不穩定

插入排序–穩定

冒泡排序–穩定

4. 冒泡排序

冒泡排序排序思路：

從前往後相鄰數字依次比較，前面的數比後面的數大則兩數交換，否則兩數位置不變，這樣就可以把最大的數慢慢移到最後
每一輪比較的次數比前一輪的次數少1

#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#include <stdbool.h>

void Random(int* arr,int n){
        srand(time(NULL));
        for(int i=0;i<n;++i){
                arr[i] = rand()%n;
        }
}

void PrintArr(int* arr,int n){
        for(int i=0;i<n;++i){
                printf("%d ",arr[i]);
        }
        printf("\n");
}

bool Ordered(int* arr,int n,bool asc){    // asc = true 表示為升序
        if(NULL == arr || n < 1) return false;
        if(1 == n) return true;
        for(int i=0;i<n-1;++i){
                if(asc){
                        if(arr[i] > arr[i+1]) return false;
                }else{
                        if(arr[i] < arr[i+1]) return false;
                }
        }
        return true;
}

/*****************冒泡排序********************/

//交換
void swap(int* p,int* q){
        int t = *p;
        *p = *q;
        *q = t;
}

//相鄰值比較，前大于後，則交換
void Bubble(int* arr,int n){
        for(int i=0;i<n-1;++i){
                if(arr[i] > arr[i+1]){        //前一個值大于後一個值，就交換
                        swap(arr+i,arr+i+1);
                }
        }
}

/*
//每一輪比較次數減1（遞歸）
void BubbleSort(int* arr,int n){
        if(0 == n) return;
        Bubble(arr,n);
        BubbleSort(arr,n-1);
}
*/

//每一輪比較次數減1（疊代）
void BubbleSort(int* arr,int n){
        for(int i=n;i>0;--i){
                Bubble(arr,i);
        }
}

int main(){
        int n;
        scanf("%d",&n);
        int arr[n];
        Random(arr,n);
        PrintArr(arr,n);
        printf("%d\n",Ordered(arr,n,true));
        BubbleSort(arr,n);  // 冒泡排序
        PrintArr(arr,n);
        printf("%d\n",Ordered(arr,n,true));
}

結果為：

30
8 6 10 23 11 21 1 18 13 21 6 1 19 9 17 29 3 27 5 6 5 21 28 2 26 19 0 0 8 23 
0
0 0 1 1 2 3 5 5 6 6 6 8 8 9 10 11 13 17 18 19 19 21 21 21 23 23 26 27 28 29 
1

簡單排序算法總結：

簡單的排序算法	時間複雜度	空間複雜度	穩定性	已排好(最好)情況
選擇排序 SelectionSort	O(n^2)	O(1)	NO	O(n^2)
插入排序 InsertionSort	O(n^2)	O(1)	YES	O(n)
冒泡排序 BubbleSort	O(n^2)	O(1)	YES	O(n^2)/O(n)

冒泡排序的優化：

如果在一輪比較中沒有發生交換的操作，則證明已經排好序，即可終止後續的排序

可以更改為：

//相鄰值比較，前大于後，則交換
bool Bubble(int* arr,int n){
        bool ordered = true;   //ordered用于标記
        for(int i=0;i<n-1;++i){
                if(arr[i] > arr[i+1]){
                        ordered = false;      //表示本輪有交換操作
                        swap(arr+i,arr+i+1);
                }
        }
        return ordered;
}

//每一輪比較次數減1（疊代）
void BubbleSort(int* arr,int n){
        for(int i=n;i>0;--i){
                if(Bubble(arr,i)) break;     //沒有交換操作直接終止排序
        }
}

基礎資料結構及算法：簡單排序算法，包括選擇排序、插入排序、冒泡排序

文章目錄

1. 測試架構

2. 選擇排序

3. 插入排序

4. 冒泡排序

繼續閱讀

開源低帶寬語音編解碼器

CRC32和CRC8校驗代碼，C語言版

241 Different Ways to Add Parentheses（C代碼版）

【趨高機器視覺】機器視覺技術原了解析及解決方案

CSMA/CD1． CSMA/CD的概述2． CSMA 的工作原理3． CSMA/CD控制規程及特點4． CSMA/CD協定5． CSMA/CD的優點6．結束語

極大似然法(ML)與最大期望法(EM)

C++ 第十五周報告1--《冒泡法排序》

C語言：初學者必定看懂的注釋！！！猴子吃桃問題。猴子第一天摘下若幹個桃子，每天都吃了前一天剩下的一半零一個，到第10天早上想再吃的時候，就剩下一個桃子. 求第一天共摘多少個桃子。

[轉]九大排序算法——C語言實作及詳解

筆試面試題目：滑動視窗(二)

while 循環、do- while 循環和 for 循環之間的那點事C語言自學之三種循環比較

資料結構與算法（27）——排序（二）

結構體：typedef與struct的差別

Dijkstra--簡易版（最短路徑）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

hdu7108哈希