一. 冒泡排序

我們常常在寫冒泡排序的時候會將待排序數(shù)列從第一個元素開始依次和后面的每一個元素進行比對和交換，但是這種做法并沒有體現(xiàn)冒泡排序的精髓，下面用三個不同寫法的來實現(xiàn)一個簡單數(shù)列的冒泡排序。
首先構(gòu)造一些公用的方法：

• 構(gòu)造了一個順序表來存儲待排序數(shù)列

typedef struct {
    int nums[MAXSIZE];
    int length;
}Sqlist;

• 寫了一個交換數(shù)組元素的方法，方便交換時直接調(diào)用

void swapNums(int i, int j, Sqlist *Sq) {
    
    int temp = Sq->nums[i];
    
    Sq->nums[i] = Sq->nums[j];
    Sq->nums[j] = temp;
}

然后就來了：

1. 初級冒泡排序的寫法

void sort(Sqlist *Sq) {
    int i,j;
    
    for (i = 0; i<Sq->length; i++) {
        
        for (j = i+1; j<Sq->length; j++) {
            printf("這次循環(huán)i=%d,j=%d,相比較的兩個數(shù)：%d %d\n",i,j,Sq->nums[i],Sq->nums[j]);
            if (Sq->nums[i] > Sq->nums[j]) {
                swapNums(i, j, Sq);
            }
        }
    }
}

2. 正規(guī)的冒泡排序的寫法

void sort2(Sqlist *Sq) {
    int i,j;       
    for (i = 0; i<Sq->length-1; i++) {
                      
        for (j = Sq->length-1; j>i; j--) {
            printf("這次循環(huán)i=%d,j=%d,相比較的兩個數(shù)：%d %d\n",i,j,Sq->nums[j],Sq->nums[j-1]);
            if (Sq->nums[j] < Sq->nums[j-1]) {
                swapNums(j, j-1, Sq);
            }
        }
    }
}

以上兩種寫法有什么區(qū)別呢？
寫法的區(qū)別其實就是第二層循環(huán)是倒著循環(huán)的。以這個數(shù)列為例調(diào)用這兩個方法：{4,6,7,5,1,2,3,8,9,10}。執(zhí)行中第一種方式可能會出現(xiàn)兩個對比的元素不相鄰的情況，而第二種方式一直是相鄰兩元素之間的比較，經(jīng)過一次次的循環(huán)，小數(shù)字往上浮，大數(shù)字往下沉，這就是冒泡排序的精髓所在。

3. 冒泡排序的優(yōu)化

冒泡排序也是可以優(yōu)化的，當出現(xiàn)例如{10,9,8,1,2,3,4,5,6,7}這樣的數(shù)列，進行升序排序時，從1到7就不用在進行多余的排序了，那么我們在上面第二種方法的基礎(chǔ)上再加上一個標志位，來記錄在某一次循環(huán)中是否出現(xiàn)了交換操作，如果沒有出現(xiàn)，則說明這些元素已經(jīng)是正確的排序了。代碼如下：

void sort2(Sqlist *Sq) {
    int i,j;
    int flag = TRUE;
    
    int time = 0;
    
    for (i = 0; i<Sq->length-1 && flag; i++) {
        
        flag = FALSE;
        
        time++;
        
        printf("循環(huán)次數(shù):");
        printf("%d\n", time);
        
        for (j = Sq->length-1; j>i; j--) {
            printf("這次循環(huán)i=%d,j=%d,相比較的兩個數(shù)：%d %d\n",i,j,Sq->nums[j],Sq->nums[j-1]);
            if (Sq->nums[j] < Sq->nums[j-1]) {
                swapNums(j, j-1, Sq);
                flag = TRUE;
            }
        }
    }
}

二. 選擇排序

升序的排序時，選擇排序是從第一個元素開始在后面的序列中依次查詢最小的值和其進行交換。

void sort3(Sqlist *Sq) {
    int i,j,min;
        
    for (i = 0; i<Sq->length; i++) {
        
        min = i;
        
        for (j = i+1; j<Sq->length; j++) {

            if (Sq->nums[min] > Sq->nums[j]) {
                min = j;
            }
        }
        if (min != i) {
            swapNums(i, min, Sq);
        }
    }
}

三. 插入排序

升序排序時，從第二個元素開始，向前找到這個元素正確的位置

void sort4(Sqlist *Sq) {
    int i,j;
    
    int temp = 0;
    
    for (i = 2; i<Sq->length; i++) {
                
        if (Sq->nums[i] < Sq->nums[i-1]) {
            temp = Sq->nums[i];

            for (j = i-1; Sq->nums[j]>temp; j--) {
                Sq->nums[j+1] = Sq->nums[j];
            }
            Sq->nums[j+1] = temp;
        }
        
    }
}