C語言直接選擇排序算法怎么使用

今天小編給大家分享一下C語言直接選擇排序算法怎么使用的相關(guān)知識點(diǎn)，內(nèi)容詳細(xì)，邏輯清晰，相信大部分人都還太了解這方面的知識，所以分享這篇文章給大家參考一下，希望大家閱讀完這篇文章后有所收獲，下面我們一起來了解一下吧。

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è)按排序碼從小到大排列的有序序列。

下面的動圖非常清晰的詮釋了直接插入排序的過程：

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

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

最差的情況是數(shù)組所有元素全部反序，移動次數(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è)存儲空間用于記錄交換的暫存單元，因此空間復(fù)雜度為：O(1) 。

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

優(yōu)點(diǎ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存儲最小值的數(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

以上就是“C語言直接選擇排序算法怎么使用”這篇文章的所有內(nèi)容，感謝各位的閱讀！相信大家閱讀完這篇文章都有很大的收獲，小編每天都會為大家更新不同的知識，如果還想學(xué)習(xí)更多的知識，請關(guān)注億速云行業(yè)資訊頻道。