冒泡排序及其优化

2018-12-08  本文已影响49人  徒步青云

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

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
上一篇下一篇

猜你喜欢

热点阅读