欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

C語言實現(xiàn)經(jīng)典排序算法的示例代碼

 更新時間:2022年08月08日 16:01:07   作者:隨便寫寫。  
這篇文章主要為大家詳細介紹了如何利用C語言實現(xiàn)經(jīng)典排序算法中的冒泡排序、選擇排序、插入排序、希爾排序,文中的示例代碼講解詳細,需要的可以參考一下

一、冒泡排序

1.原理

從數(shù)組的頭開始不斷比較相鄰兩個數(shù)的大小,不斷將較大的數(shù)右移,一個循環(huán)后,最大數(shù)移至最后一位,無序數(shù)組規(guī)模減一。不斷重復前面動作,知道數(shù)組完全有序。

2.實現(xiàn)

void swap(int* a, int* b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}
void bubble_sort(int* arr, int len)
{
    bool issort = false;
    while (!issort)
    {
        issort = true;//如果有序則直接退出
        for (int i = 1; i < len; i++)
        {
            if (arr[i-1] > arr[i])//不斷比較相鄰兩個數(shù)
            {
                swap(&arr[i - 1], &arr[i]);//將較大的數(shù)不斷往右移
                issort = false;//如果進行了交換則無序
            }
        }
        len--;//無序規(guī)模減一
    }
}

3.算法分析

時間復雜度: 最好情況,當數(shù)組完全有序,則只需要進行一輪比較,時間復雜度為o(n);最壞情況為完全無序,每次比較后都要將該數(shù)移至數(shù)組末尾,時間復雜度為o(n ^2);平均時間復雜度為o(n ^2)。

空間復雜度: 冒泡排序為就地排序,空間復雜度為o(1)。

穩(wěn)定排序: 當數(shù)字相同時不會改變相對次序。

二、選擇排序

1.原理

數(shù)組前面為無序,后面為有序。剛開始全是無序,從中選擇一個最大值與最后一個無序數(shù)字進行交換,無序數(shù)組規(guī)模減一,有序數(shù)組規(guī)模加一。不斷循環(huán)前面操作,直到數(shù)組變?yōu)橛行驍?shù)組?;蛘咔懊鏋橛行驍?shù)組,后面為無序數(shù)組,不斷選擇最小值與無序數(shù)組的第一個數(shù)交換,前面的有序數(shù)組加一,后面的無序數(shù)組減一。

2.實現(xiàn)

void selection_sort(int* arr, int len)
{
    int max_index;
    while (len)
    {
        max_index = 0;
        for (int i = 1; i < len; i++)
        {
            if (arr[max_index] < arr[i])
            {
                max_index = i;//獲取最大值的索引
            }
        }
        swap(&arr[max_index], &arr[len - 1]);//將最大值與最后一個值交換
        len--;//無序規(guī)模減一
    }
}

3.算法分析

時間復雜度: 所有的復雜度為每次選擇最大值,不管數(shù)字的有序性,時間復雜度都為o(n)+o(n-1)+…+o(1)=o(n^2)。所以該算法平均復雜度、最好情況、最差情況都為o(n ^2)。

空間復雜度: 就地排序,空間復雜度為o(1)。

不穩(wěn)定性算法: 排序后相同元素的順序可能被打亂。例子:選擇最大進行排序。3,1,2,2* 第一輪排序后 2*,1,2,3 2的相對順序發(fā)生了改變。選擇最小進行排序,2*,2,3,1 第一輪排序后1,2,3,2*. 2的相對順序也被打亂。如果增加空間復雜度也能將選擇排序變成穩(wěn)定性排序。

三、插入排序

1.原理

數(shù)組前面為有序,后面為無序,將無序數(shù)組中的第一個數(shù)不斷插入有序數(shù)組中(具體實現(xiàn)為不斷比較相鄰兩數(shù)大小,前面一個數(shù)大于后一個數(shù),則交換順序,較小的數(shù)不斷前移),有序規(guī)模增加一,無序規(guī)模減小一。或者,數(shù)組前面為無序,后面為有序,通過將無序數(shù)組的最后一位數(shù)字插入有序數(shù)組中(具體實現(xiàn)為將無序數(shù)組的最后一位與相鄰的有序數(shù)組不斷比較,將無序數(shù)組不斷右移)。

2.實現(xiàn)

void insert_sort(int arr[], int len)
{
    for (int i = 1; i < len; i++)//i前面為有序
    {
        for (int j = i - 1; j >= 0; j--)//j為有序數(shù)的末尾
        {
            bool issort = true;//當數(shù)組有序時能夠提前退出
            if (arr[j] > arr[j + 1])//將無序數(shù)組的第一個數(shù)不斷與有序數(shù)組比較
            {
                swap(&arr[j], &arr[j + 1]);//將無序數(shù)字插入有序數(shù)組合適的位置
                issort = false;
            }
            if (issort) break;
        }
    }
}

3.算法分析

時間復雜度: 插入排序和冒泡排序類似,最好情況完全有序則時間復雜度為o(n),最壞情況為完全無序時間復雜度為o(n^2),平均復雜度為o(n ^2)。

空間復雜度: 就地排序不需要額外空間,空間復雜度為o(1)。

穩(wěn)定性排序: 和冒泡排序類似。

四、希爾排序

1.原理

每次選擇一個增量進行分組,增量不斷減小到一(為插入排序),數(shù)組不斷變得有序,增量為一時變成完全有序。屬于插入排序的改進,通過增量進行分組,對每一組進行插入排序,相比于插入排序的優(yōu)勢在于,shell排序能夠大尺度的移動每一組的最小值,而插入排序得挨著進行比較,所以shell排序效率更高。

增量為6:

每一組只有兩個數(shù),分別比較兩個數(shù)的大小,如64,57交換順序變成57,64,所有的分組比較完后繼續(xù)縮減增量。

增量為3:

每一組有四個數(shù),總共三組,分別為23,12,53,79;57,9,64,87;24,16,71,97;以增量開始(12開始)遍歷數(shù)組,遍歷到12則在第一組中對12進行插入排序,交換23和12的順序;遍歷到9則在第二組對9進行插入排序。。。。遍歷到64對一組中的9,57,64進行插入排序。最后每一組都變得有序。整體有序性變大。

增量為1:

對之前排序過的數(shù)組進行插入排序,通過前面的步驟數(shù)組有序性變大,最后進行插入排序的效率就更高。

2.實現(xiàn)

void shell_sort(int* arr, int len)
{
    int gap = 0; //分組的跨度
    int i = 0;
    int j = 0;
    for (gap = len / 2; gap >= 1; gap /= 2) //分組增量
    {
        for (i = gap; i < len; i++) {  //遍歷每組
            for (j = i - gap; j >= 0; j -= gap)  //對組內(nèi)進行插入排序
            {
                if (arr[j] > arr[j + gap])
                {
                    swap(&arr[j], &arr[j + gap]);
                }
            }
        }
    }
}

3.算法分析

時間復雜度:最好情況為完全有序o(n),最差情況為完全無序o(n^2),平均復雜度為o(n ^1.3)。

空間復雜度:該算法為就地排序空間復雜度為o(1)。

穩(wěn)定性:shell排序在分組中可能將相同數(shù)字劃分成不同的分組,會改變相對順序,屬于不穩(wěn)定性排序算法。

總結

冒泡排序、選擇排序、插入排序、希爾排序的實現(xiàn)都是基于線性表進行實現(xiàn)的(數(shù)組或者鏈表),實現(xiàn)邏輯都是通過比較數(shù)字的大小。算法的時間復雜度都比較大,但是屬于就地排序,不需要額外空間。幾種算法相比之下希爾排序更具有優(yōu)勢。

到此這篇關于C語言實現(xiàn)經(jīng)典排序算法的示例代碼的文章就介紹到這了,更多相關C語言排序算法內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家!

相關文章

  • C語言實現(xiàn)文件讀寫操作

    C語言實現(xiàn)文件讀寫操作

    這篇文章主要為大家詳細介紹了C語言實現(xiàn)文件讀寫操作,文中示例代碼介紹的非常詳細,具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2020-12-12
  • C語言輪轉數(shù)組的三種實現(xiàn)

    C語言輪轉數(shù)組的三種實現(xiàn)

    輪轉數(shù)組是一種將數(shù)組元素循環(huán)移動的處理方式,它通常用于解決一些需要對固定長度的數(shù)組進行循環(huán)滾動處理的問題,本文就介紹了C語言輪轉數(shù)組的三種實現(xiàn),感興趣的可以了解一下
    2023-08-08
  • 一起來學習C++中remove與erase的理解

    一起來學習C++中remove與erase的理解

    這篇文章主要為大家詳細介紹了C++的remove與erase,文中示例代碼介紹的非常詳細,具有一定的參考價值,感興趣的小伙伴們可以參考一下,希望能夠給你帶來幫助
    2022-03-03
  • C++多態(tài)虛析構和純虛析構的實現(xiàn)

    C++多態(tài)虛析構和純虛析構的實現(xiàn)

    本文主要介紹了C++多態(tài)虛析構和純虛析構的實現(xiàn),文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧
    2023-09-09
  • C語言使用posix正則表達式庫的實現(xiàn)

    C語言使用posix正則表達式庫的實現(xiàn)

    在C語言中,你可以使用 POSIX 正則表達式庫(regex.h)來進行正則表達式的模式匹配,本文主要介紹了C語言使用posix正則表達式庫的實現(xiàn),具有一定的參考價值,感興趣的可以了解一下
    2023-12-12
  • 如何利用C++實現(xiàn)mysql數(shù)據(jù)庫的連接池詳解

    如何利用C++實現(xiàn)mysql數(shù)據(jù)庫的連接池詳解

    為了提高MySQL數(shù)據(jù)庫的訪問的瓶頸,除了在服務器端增設緩存服務器緩存常用的數(shù)據(jù)之外(如redis),還可以增加數(shù)據(jù)庫連接池,來提高MySQL Server的訪問效率,這篇文章主要給大家介紹了關于如何利用C++實現(xiàn)mysql數(shù)據(jù)庫的連接池的相關資料,需要的朋友可以參考下
    2021-07-07
  • 詳解C/C++高精度算法的簡單實現(xiàn)

    詳解C/C++高精度算法的簡單實現(xiàn)

    這篇文章主要為大家詳細介紹了C/C++中高精度算法(加減乘除)的簡單實現(xiàn),方便以后需要時拷貝使用。感興趣的小伙伴可以跟隨小編一起了解一下
    2022-12-12
  • C語言零基礎講解指針和數(shù)組

    C語言零基礎講解指針和數(shù)組

    由于數(shù)據(jù)的表現(xiàn)形式多種多樣,還有字符型和其它的數(shù)值類型,因此僅有基本數(shù)據(jù)類型是不夠的。是否可以通過基本數(shù)據(jù)類型的組合抽象構造其它的數(shù)據(jù)類型呢?下面是小編為大家?guī)淼腃語言數(shù)組與指針詳解的知識
    2022-04-04
  • C++分析構造函數(shù)與析造函數(shù)的特點梳理

    C++分析構造函數(shù)與析造函數(shù)的特點梳理

    本文對類的構造函數(shù)和析構函數(shù)進行總結,主要包括了構造函數(shù)的初始化、重載、使用參數(shù)和默認參數(shù),拷貝構造函數(shù)和析構函數(shù),希望能幫助讀者在程序開發(fā)中更好的理解類,屬于C/C++基礎
    2022-05-05
  • C到C++的升級關系及區(qū)別實例探究

    C到C++的升級關系及區(qū)別實例探究

    這篇文章主要為大家介紹了C到C++的升級關系及區(qū)別實例探究,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進步,早日升職加薪
    2024-01-01

最新評論