冒泡排序基本介紹

冒泡排序（Bubble Sorting）：是一種計算機科學(xué)領(lǐng)域的較簡單的排序算法。它的基本思想是：通過對待排序序列從前向后（從下標(biāo)較小的元素開始）, 依次比較相鄰元素的值，若發(fā)現(xiàn)逆序則交換，使值較大的元素逐漸從前移向后部，就象水底下的氣泡一樣逐漸向上冒。故名“冒泡排序”。

冒泡排序原理

• 外層循環(huán) 0到n-1 //控制比較輪數(shù) n 表示元素的個數(shù)
• 內(nèi)層循環(huán) 0到n-i-1 //控制每一輪比較次數(shù)
• 兩兩比較做交換

第一次找到一個最大的，在剩下的數(shù)據(jù)中找到最大的
對于一組N個元素數(shù)據(jù)，每次從待排數(shù)據(jù)中 比較相鄰元素中交換最大數(shù)值，最大值最終移到后部

代碼

//冒泡排序
void bubble_sort(int *array, int length){
    int times = 0;
    int temp;
    for (int i = 0; i< length; i++) {
        int flag = 0;
        for (int j = 0; j < length - 1 - i; j++) {
            if (array[j] > array[j + 1]) {
                temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
                flag = 1;
            }
            times++;
        }
        if (flag == 0) {
            break;
        }
    }
    printf("\n排序后：");
    for (int i = 0; i< length; i++) {
        printf("%d ", array[i]);
    }
    printf("冒泡執(zhí)行了：%d", times);
}

冒泡排序的優(yōu)化（1）

• 一共進行數(shù)組的大小-1 次大的循環(huán)
• 每一趟排序的次數(shù)在逐漸的減少
• 在冒泡排序中，沒有發(fā)生一次交換，可以提前結(jié)束冒泡排序。這個就是優(yōu)化

冒泡排序優(yōu)化（2）-雙向冒泡排序（雞尾酒排序）

上面的代碼已經(jīng)進行過優(yōu)化，加了排序中，沒有發(fā)生一次交換，提前結(jié)束冒泡排序的標(biāo)識flag。

• 1、正常的冒泡排序
• 2、在第一輪排序結(jié)束后，從后往前排除最小數(shù)
• 3、最終就是排好的數(shù)據(jù)

void doubleBubble_sort(int *array, int lenght) {
    int times = 0;
    int temp;
    for (int i = 0; i < lenght/2; i++) {
        int flag = 0;
        for (int j = 0; j < lenght - i - 1; j++) {
            if (array[j] > array[j + 1]) {
                temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
                flag = 1;
            }
            times ++;
        }
        if (flag == 0) {
            break;
        }
        
        for (int j = lenght - i - 1; j > i; j--) {
            if (array[j] < array[j - 1]) {
                temp = array[j];
                array[j] = array[j - 1];
                array[j - 1] = temp;
                flag = 1;
            }
            times ++;
        }
        if (flag == 0) {
            break;
        }
    }
    
    printf("\n排序后：");
    for (int i = 0; i< lenght; i++) {
        printf("%d ", array[i]);
    }
    printf("雙向冒泡執(zhí)行了：%d", times);
}

選擇排序

工作原理是：

• 1、第一次從待排序的數(shù)據(jù)元素中選出最?。ɑ蜃畲螅┑囊粋€元素，存放在序列的起始位置，
• 2、然后再從剩余的未排序元素中尋找到最?。ù螅┰兀缓蠓诺揭雅判虻男蛄械哪┪?。
• 3、以此類推，直到全部待排序的數(shù)據(jù)元素的個數(shù)為零。

代碼

//選擇排序
void select_sort(int *array, int length) {
    int temp;
    for (int i = 0; i< length - 1; i++) {
        for (int j = i + 1; j <length; j++) {
            if (array[i] > array[j]) {
                temp = array[i];
                array[j] = array[j];
                array[j] = temp;
            }
        }
    }
    printf("\n排序后：");
    for (int i = 0; i< length; i++) {
        printf("%d ", array[i]);
    }
}