冒泡排序基本介紹

冒泡排序（Bubble Sorting）：是一種計算機科學領域的較簡單的排序算法尚卫。它的基本思想是：通過對待排序序列從前向后（從下標較小的元素開始）, 依次比較相鄰元素的值糙置，若發(fā)現逆序則交換偿荷，使值較大的元素逐漸從前移向后部谣辞，就象水底下的氣泡一樣逐漸向上冒虱颗。故名“冒泡排序”赋访。

冒泡排序原理

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

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

代碼

//冒泡排序
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）

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

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

上面的代碼已經進行過優(yōu)化歌逢，加了排序中巾钉，沒有發(fā)生一次交換，提前結束冒泡排序的標識flag秘案。

• 1砰苍、正常的冒泡排序
• 2、在第一輪排序結束后阱高，從后往前排除最小數
• 3赚导、最終就是排好的數據

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、第一次從待排序的數據元素中選出最刑殖汀（或最大）的一個元素，存放在序列的起始位置寒屯，
• 2荐捻、然后再從剩余的未排序元素中尋找到最小（大）元素寡夹，然后放到已排序的序列的末尾处面。
• 3、以此類推菩掏，直到全部待排序的數據元素的個數為零魂角。

代碼

//選擇排序
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]);
    }
}