冒泡排序与选择排序的优化

冒泡排序跟选择排序是八大排序里最简单的两个,有时候简单意味着高效,但这种想法在这两种排序上行不通,恰恰这两种排序的时间复杂度都是O(n^2)级别的,相对于快排的平均时间复杂度O(nlog2n)来说,确实慢了不少。因此,在还不会使用别的排序方法之前,我们可以先对这两种排序方法进行优化,尽量减少运行时间。

一、冒泡排序

冒泡排序有两种比较好的优化方法:

1.在二级循环外进行优化:

这种方法即在两个for循环之间加入一个标志变量flag,先贴代码:(这是升序排序)

void BubbleSort_Optimization_1(int arr[],int size) {
    for (int i = 0;i < size-1;i++) {
        int flag = 1;
        for (int j = 0;j < size - 1 - i;j++) {
            int temp;
            if (arr[j] > arr[j + 1]) {
                temp = arr[j + 1];
                arr[j + 1] = arr[j];
                arr[j] = temp;
                flag = 0;
            }
        }
        if (flag)
            break;
    }
    return;
}

代码第三行处定义了一个标志变量flag,赋初值为1,进入二级循环,只要在二级循环里不会进入if()语句,那么flag的值就会为1,如果执行完二级循环后flag的值仍为1就意味着整个数列从下标0开始到size-1-i为止都是有序的,那么接下来的外层循环就没必要再进行了,直接结束排序过程。

2.第二种优化即是对内层循环进行的优化:

void BubbleSort_Optimization_2(int arr[], int size) {
    int k = size - 1;
    int temp_k;                        //temp_k用来暂时存k应赋予的值
    for (int i = 0;i < size;i++) {
        int flag = 1;
        for (int j = 0;j < k;j++) {    //这里的循环的上界设置为k
            int temp;
            if (arr[j] > arr[j + 1]) {
                temp = arr[j + 1];
                arr[j + 1] = arr[j];
                arr[j] = temp;
                temp_k = j;    //这里将最后一次交换值时的下标j记录下来,等待赋予k
                flag = 0;
            }
        }
        k = temp_k;
        if (flag)                      //这里依旧是只要数列后边有序就结束排序
            break;
    }
    return;
}

其实上面的代码时两种优化的结合体,第二种优化的关键点在内层循环的上界设置为k,而k的值来自最后一次交换变量所对应的下标j,这样就可以更进一步把排序的范围缩小,减少时间。

二、选择排序的优化

本博文只列出一种选择排序的优化方法:

一般的选择排序每遍历一次数组,只找出最大或最小的那个值,那如果我们在一次遍历之后就把最大和最小值都找出来呢,时间在理论上会比原来少花一半左右。具体代码如下:

void SelectionSort_Optimization(int arr[], int size) {
    int left=0, right=size-1;      //left跟right用于循环上下界的左右逼近
   
    while(left<right){
        int temp;
        int max=right, min=left;
        for (int i = left;i <= right;i++) {
            if (arr[i] > arr[max]) {
                max = i;
            }
            if (arr[i] < arr[min]) {
                min = i;
            }
        }

temp = arr[max];          //
        arr[max] = arr[right];    //  这块代码将遍历后的最大值交换到右边
        arr[right] = temp;        //

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/ce41376d59d41a0453b9e5821fa1c977.html