冒泡排序及其优化

冒泡排序原理：通过交换相邻元素，来将未排序中最大（小）元素依次“冒泡”到数组最后方。
最原始的冒泡排序：

template<typename T>
void bubbleSort(T arr[], int n) {
    //n-1次冒泡(最后1次自然有序)
    for (int i = 0; i < n - 1; i++) {
        //每次冒泡，相邻两个元素进行比较，将当前数组中最大元素移至末尾
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(arr[j], arr[j + 1]);
            }
        }
    }
}

从代码中我们可以发现，最原始的冒泡排序算法对相同规模的输入，其排序次数是固定不变的。然而经过一次次“冒泡”操作后，未排数据将趋于稳定（即有序），这是因为每次“冒泡”都是相邻元素进行比较和交换完成的。考虑到这种情况，我们便有了下面这种优化方案：

template<typename T>
void bubbleSort1(T arr[], int n) {
    bool isSwap = true;//本次循环是否发生过数值交换，若false，则表示所有元素都有序
    for (int i = 0; isSwap && i < n - 1; i++) {
        isSwap = false;
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(arr[j], arr[j + 1]);
                isSwap = true;
            }
        }
    }
}

第一种改进方案虽然有一定的优化效果，但至是考虑了尾端元素有序的情况，并没有考虑到元素局部有序这种情况，因此我们有了第二种改进方案：

template<typename T>
void bubbleSort2(T arr[], int n) {
    int lastSwapPos = n - 1;//最后一次交换的位置,此时后面数列顺序已经正确
    int tempPos;
    do {
        tempPos = lastSwapPos;
        lastSwapPos = 0;
        for (int j = 0; j < tempPos; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(arr[j], arr[j + 1]);
                lastSwapPos = j;
            }
        }
    } while (lastSwapPos > 0);
}

鸡尾酒排序

template<typename T>
void cocktailSort(T arr[], int n) {
    int left = 0;
    int right = n - 1;
    while (left < right) {
        for (int i = left; i < right; i++) {  //向右进行“冒泡”
            if (arr[i] > arr[i + 1])
                swap(arr[i], arr[i + 1]);
        }
        right--;
        for (int j = right; j > left; j--) { //向左进行“冒泡”
            if (arr[j] < arr[j - 1])
                swap(arr[j], arr[j - 1]);
        }
        left++;
    }
}

改进的鸡尾酒排序

template<typename T>
void cocktailSort1(T arr[], int n) {
    int left = 0;
    int right = n - 1;
    int swapPos = left;
    while (left < right) {
        for (int i = left; i < right; i++) {  //向右进行“冒泡”
            if (arr[i] > arr[i + 1]) {
                swap(arr[i], arr[i + 1]);
                swapPos = i;//此时记录向右冒泡最后一次交换位置
            }
        }
        right = swapPos;//将最后一次交换位置作为右冒泡起点
        for (int j = right; j > left; j--) { //向左进行“冒泡”
            if (arr[j] < arr[j - 1]) {
                swap(arr[j], arr[j - 1]);
                swapPos = j;//此时记录向左冒泡最后一次交换位置
            }
        }
        left = swapPos;//将最后一次交换位置作为左冒泡起点
    }
}

image.png