本篇主要簡(jiǎn)單介紹選擇排序，并且通過圖片和代碼的形式幫助大家理解應(yīng)用。

（1）什么是選擇排序？

選擇排序（Selection sort）是一種簡(jiǎn)單直觀的排序算法。它的工作原理是：第一次從待排序的中數(shù)據(jù)元素選出最?。ɑ蜃畲螅┑囊粋€(gè)元素，存放在序列的起始位置，然后再?gòu)氖Ｓ嗟奈磁判蛟刂袑ふ业阶钚。ù螅┰兀缓蠓诺揭雅判虻男蛄械哪┪?。以此類推，直到全部待排序的?shù)據(jù)元素的個(gè)數(shù)為零。選擇排序是不穩(wěn)定的排序方法。

（2）選擇排序思路

首先在未排序序列中找到最?。ù螅┰?，存放到排序序列的起始位置，然后，再?gòu)氖Ｓ辔磁判蛟刂欣^續(xù)尋找最?。ù螅┰?，然后放到已排序序列的末尾。以此類推，直到所有元素均排序完畢。

（3）排序過程

例：定義一個(gè)數(shù)組 int a[8] = {9，3，7，2，6，1，5，8}，要求利用選擇排序的方法將數(shù)組從小到大排序。

排序的次數(shù)：因?yàn)槊颗藕靡粋€(gè)元素，那么所需要排的元素個(gè)數(shù)減一，直到排到倒數(shù)第二個(gè)元素停止，將倒數(shù)第二個(gè)元素也排好后，整體數(shù)組排序就完成了。所以排序的次數(shù) = 元素個(gè)數(shù) - 1。(冒泡排序的排序次數(shù)與該排序的排序次數(shù)計(jì)算方法相同)

第一次排序：假設(shè)首元素作為整體元素?cái)?shù)據(jù)最小值，然后從該元素的后一個(gè)元素開始每個(gè)元素都與該最小值進(jìn)行比較，假如有比該元素小的值，就用一個(gè)變量去記住下標(biāo)值，最后比較完成后，把兩個(gè)元素互換位置即可。

第一次排序結(jié)果：{1，3，7，2，6，9，5，8}

第二次排序：因?yàn)榈谝淮闻判蜻x擇的是將首元素作為最小值，最終經(jīng)過互換位置，首元素排序完成，第二次排序就不需要排序首元素，只需要排序除首元素以外的元素，然后在依照第一次排序的原理進(jìn)行排序。

第二次排序結(jié)果：{1，2，7，3，6，9，5，8}

然后根據(jù)第一次排序和第二次排序的原理，最終的排序結(jié)果為：{1，2，3，5，6，7，8，9}

（4）C語言代碼實(shí)現(xiàn)如下：

#include <stdio.h>
#include <stdlib.h>
#define MAX 9
//單個(gè)記錄的結(jié)構(gòu)體
typedef struct {
    int key;
}SqNote;
//記錄表的結(jié)構(gòu)體
typedef struct {
    SqNote r[MAX];
    int length;
}SqList;
//交換兩個(gè)記錄的位置
void swap(SqNote *a,SqNote *b){
    int key=a->key;
    a->key=b->key;
    b->key=key;
}
//查找表中關(guān)鍵字的最小值
int SelectMinKey(SqList *L,int i){
    int min=i;
    //從下標(biāo)為 i+1 開始，一直遍歷至最后一個(gè)關(guān)鍵字，找到最小值所在的位置
    while (i+1<L->length) {
        if (L->r[min].key>L->r[i+1].key) {
            min=i+1;
        }
        i++;
    }
    return min;
}
//簡(jiǎn)單選擇排序算法實(shí)現(xiàn)函數(shù)
void SelectSort(SqList * L){
    for (int i=0; i<L->length; i++) {
        //查找第 i 的位置所要放置的最小值的位置
        int j=SelectMinKey(L,i);
        //如果 j 和 i 不相等，說明最小值不在下標(biāo)為 i 的位置，需要交換
        if (i!=j) {
            swap(&(L->r[i]),&(L->r[j]));
        }
    }
}

int main() {
    SqList * L=(SqList*)malloc(sizeof(SqList));
    L->length=8;
    L->r[0].key=9;
    L->r[1].key=3;
    L->r[2].key=7;
    L->r[3].key=2;
    L->r[4].key=6;
    L->r[5].key=1;
    L->r[6].key=5;
    L->r[7].key=8;
    SelectSort(L);
    for (int i=0; i<L->length; i++) {
        printf("%d ",L->r[i].key);
    }
    return 0;
}

如果我們編譯并運(yùn)行上述程序，那么它應(yīng)該產(chǎn)生以下結(jié)果：

1 2 3 5 6 7 8 9