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

C語言直接選擇排序算法詳解

 更新時(shí)間:2022年08月11日 16:16:49   作者:柒號(hào)華仔  
直接選擇排序就是遍歷整個(gè)數(shù)組,每遍歷一遍的目的是找出該數(shù)組中的最大數(shù)和最小數(shù)對(duì)應(yīng)的下標(biāo),然后將最小數(shù)和數(shù)組的第一個(gè)數(shù)進(jìn)行交換,最大數(shù)和數(shù)組的最后一個(gè)數(shù)進(jìn)行交換,然后縮小范圍再次遍歷

1. 直接選擇排序介紹

1.1 定義

直接選擇排序是指每次都從剩余數(shù)據(jù)中選出最大或者最小的,將其排在已經(jīng)排好的有序表后面。

1.2 基本原理

每次從無序表中選擇最小(或最大)元素,將其作為首元素,知道所有元素排完為止。將一個(gè)有n個(gè)元素的數(shù)組從小到大排序,第一次從R[0] ~ R[n-1]中選取最小值,與R[0]交換,第二次從R[1] ~ R[n-1]中選取最小值,與R[1]交換,…,第i次從R[i-1] ~ R[n-1]中選取最小值,與R[i-1]交換,…,第n-1次從R[n-2] ~ R[n-1]中選取最小值,與R[ n -2]交換,總共通過n-1次,得到一個(gè)按排序碼從小到大排列的有序序列。

下面的動(dòng)圖非常清晰的詮釋了直接插入排序的過程:

1.3 時(shí)間復(fù)雜度

最好的情況是數(shù)組所有元素已經(jīng)是有序排列,移動(dòng)次數(shù)為0;

最差的情況是數(shù)組所有元素全部反序,移動(dòng)次數(shù)為3(n-1)。

無論最好與最差情況,在排序時(shí)所有待排元素均需與后面的元素進(jìn)行比較,比較次數(shù)為:

(n-1)+(n-2)+ …+2+1= n(n-1)/2

因此,直接插入排序的平均時(shí)間復(fù)雜度為O( n 2 n^2 n2) 。

1.4 空間復(fù)雜度

直接選擇排序僅需一個(gè)存儲(chǔ)空間用于記錄交換的暫存單元,因此空間復(fù)雜度為:O(1) 。

1.5 優(yōu)缺點(diǎn)

優(yōu)點(diǎn):直接選擇排序算法簡(jiǎn)單直觀,當(dāng)待排序記錄數(shù)量n很小時(shí),局部有序時(shí),較為適用。

缺點(diǎn):不穩(wěn)定,由于直接選擇排序是以最大或最小值直接與最前方未排序的鍵值交換,數(shù)據(jù)排序順序很有可能被改變。

2. 代碼實(shí)現(xiàn)

2.1 代碼設(shè)計(jì)

a. 實(shí)現(xiàn)直接插入排序需要設(shè)計(jì)兩層循環(huán),整個(gè)數(shù)組為外循環(huán),后面未排列好的無序元素為內(nèi)循環(huán);

b. 使用變量minIndex存儲(chǔ)最小值的數(shù)組元素下標(biāo),依次遍歷無序元素,找出最小元素下標(biāo);

c. 將最小元素與無序元素的首元素進(jìn)行交換,無序元素個(gè)數(shù)減1,相應(yīng)i加1;

d. 重復(fù)b和c兩步操作,直至i=n-1,即無序元素個(gè)數(shù)為0,則排序完成。

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

#include <stdio.h>
void printArray(int array[], int size) {
    int i;
    for (i = 0; i < size; i++) {
        printf("%d ", array[i]);
    }
    printf("\n");
} 
void chooseSort(int array[],int n)
{
    int i,j;
    int minIndex,temp,num;
    for(i=0;i<n-1;i++)
    {
        minIndex=i;
        for(j=i+1;j<n;j++)
        {
            if(array[j]<=array[minIndex])
            {
                minIndex=j;
            }
        }
        if(i!=minIndex)
        {
            temp=array[minIndex];
            array[minIndex]=array[i];
            array[i]=temp;
        }
        printArray(array, n);
    }
}
int main(void)
{
    int array[]={3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};
    printArray(array,sizeof(array)/sizeof(int));
    chooseSort(array,sizeof(array)/sizeof(int));
    printf("\n");
    return 0;
}

運(yùn)行結(jié)果:

3 44 38 5 47 15 36 26 27 2 46 4 19 50 48
2 44 38 5 47 15 36 26 27 3 46 4 19 50 48
2 3 38 5 47 15 36 26 27 44 46 4 19 50 48
2 3 4 5 47 15 36 26 27 44 46 38 19 50 48
2 3 4 5 47 15 36 26 27 44 46 38 19 50 48
2 3 4 5 15 47 36 26 27 44 46 38 19 50 48
2 3 4 5 15 19 36 26 27 44 46 38 47 50 48
2 3 4 5 15 19 26 36 27 44 46 38 47 50 48
2 3 4 5 15 19 26 27 36 44 46 38 47 50 48
2 3 4 5 15 19 26 27 36 44 46 38 47 50 48
2 3 4 5 15 19 26 27 36 38 46 44 47 50 48
2 3 4 5 15 19 26 27 36 38 44 46 47 50 48
2 3 4 5 15 19 26 27 36 38 44 46 47 50 48
2 3 4 5 15 19 26 27 36 38 44 46 47 50 48
2 3 4 5 15 19 26 27 36 38 44 46 47 48 50

到此這篇關(guān)于C語言直接選擇排序算法詳解的文章就介紹到這了,更多相關(guān)C語言直接選擇排序內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!

相關(guān)文章

  • OpenCV實(shí)現(xiàn)繪制輪廓外接矩形

    OpenCV實(shí)現(xiàn)繪制輪廓外接矩形

    這篇文章主要為大家詳細(xì)介紹了OpenCV實(shí)現(xiàn)繪制輪廓外接矩形的方法,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2022-12-12
  • C語言中隱藏結(jié)構(gòu)體的細(xì)節(jié)

    C語言中隱藏結(jié)構(gòu)體的細(xì)節(jié)

    以筆者粗淺的認(rèn)識(shí),有兩種最常用的方法,可以實(shí)現(xiàn)庫內(nèi)結(jié)構(gòu)體定義的隱藏:接口函數(shù)形參使用結(jié)構(gòu)體指針,接口函數(shù)形參使用句柄。
    2017-05-05
  • C++中spdlog的簡(jiǎn)單使用示例

    C++中spdlog的簡(jiǎn)單使用示例

    spdlog是一個(gè)開源、跨平臺(tái)、無依賴、只有頭文件的C++11日志庫,所以這篇文章主要來和大家介紹一下一個(gè)簡(jiǎn)單的spdlog使用示例,感興趣的小伙伴可以了解一下
    2023-08-08
  • C語言運(yùn)用回調(diào)函數(shù)實(shí)現(xiàn)計(jì)算器

    C語言運(yùn)用回調(diào)函數(shù)實(shí)現(xiàn)計(jì)算器

    這篇文章主要為大家詳細(xì)介紹了C語言運(yùn)用回調(diào)函數(shù)實(shí)現(xiàn)計(jì)算器,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2021-10-10
  • C語言 操作符分類解析與使用

    C語言 操作符分類解析與使用

    C 語言提供了豐富的操作符,有:算術(shù)操作符,移位操作符,位操作符,邏輯操作符,逗號(hào)表達(dá)式。讓我們通讀本篇來詳細(xì)了解吧
    2021-11-11
  • C語言字符串操作總結(jié)大全(超詳細(xì))

    C語言字符串操作總結(jié)大全(超詳細(xì))

    本篇文章是對(duì)C語言字符串操作進(jìn)行了詳細(xì)的總結(jié)分析,需要的朋友參考下
    2013-05-05
  • C語言實(shí)現(xiàn)簡(jiǎn)單的通訊錄

    C語言實(shí)現(xiàn)簡(jiǎn)單的通訊錄

    這篇文章主要為大家詳細(xì)介紹了C語言實(shí)現(xiàn)簡(jiǎn)單的通訊錄,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2018-02-02
  • Java C++題解leetcode856括號(hào)的分?jǐn)?shù)

    Java C++題解leetcode856括號(hào)的分?jǐn)?shù)

    這篇文章主要為大家介紹了Java C++題解leetcode856括號(hào)的分?jǐn)?shù)實(shí)現(xiàn)示例,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪
    2022-10-10
  • C語言實(shí)現(xiàn)電腦關(guān)機(jī)程序

    C語言實(shí)現(xiàn)電腦關(guān)機(jī)程序

    這篇文章主要為大家詳細(xì)介紹了C語言實(shí)現(xiàn)電腦關(guān)機(jī)程序,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2020-02-02
  • C++語言基礎(chǔ) this和static關(guān)鍵字

    C++語言基礎(chǔ) this和static關(guān)鍵字

    這篇文章主要介紹了C++語言基礎(chǔ) this和static關(guān)鍵字,需要的朋友可以參考下
    2020-01-01

最新評(píng)論