数据结构-冒泡排序-优化- 双向冒泡排序

冒泡排序基本介绍

冒泡排序（Bubble Sorting）：是一种计算机科学领域的较简单的排序算法。它的基本思想是：通过对待排序序列从前向后（从下标较小的元素开始）, 依次比较相邻元素的值，若发现逆序则交换，使值较大的元素逐渐从前移向后部，就象水底下的气泡一样逐渐向上冒。故名“冒泡排序”。

冒泡排序原理

• 外层循环 0到n-1 //控制比较轮数 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("冒泡执行了：%d", times);
}

冒泡排序的优化（1）

• 一共进行数组的大小-1 次大的循环
• 每一趟排序的次数在逐渐的减少
• 在冒泡排序中，没有发生一次交换，可以提前结束冒泡排序。这个就是优化

冒泡排序优化（2）-双向冒泡排序（鸡尾酒排序）

上面的代码已经进行过优化，加了排序中，没有发生一次交换，提前结束冒泡排序的标识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("双向冒泡执行了：%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]);
    }
}