关于冒泡排序算法的实验

  在数据量比较少的应用场景，所有的排序算法的时间差异是比较小的，冒泡排序可能是经常用于处理小数据量的排序算法，冒泡排序的时间复杂度为 O(n²)，但是写法不一样，效果还是大相径庭。

  1.C语言的冒泡排序和选择排序的实例：

#include 
 
int main(){
 
    int arr[] = {986,89,56,2,78,8,23,47,36,98,3,876,234};
   
    int temp, i, j, total;
    int len = (unsigned)sizeof(arr)/sizeof(arr[0]);
   
    printf("原始数据：\n");
   
    for(i = 0; i < len; i++){
        printf("%d ", arr[i]);
    }
   
    printf("\n\n");
   
    //1.-------------------------------
    printf("1.冒泡排序方法1：\n");
   
    int arr_1[len];
   
    for(i = 0;i < len;i++){
        arr_1[i] = arr[i];
    }
   
    total = 0;
   
    //1.冒泡排序(注意细节，这里使用 i < len，j < len - 1)
    for(i = 0;i < len; i++){
        for(j = 0; j < len - 1; j++){
            if(arr_1[j] > arr_1[j + 1]){
                temp = arr_1[j];
                arr_1[j] = arr_1[j + 1];
                arr_1[j + 1] = temp;
            }
            total++;
        }
    }
   
    for(i = 0; i < len; i++){
        printf("%d ", arr_1[i]);
    }
   
    printf("\n循环次数：%d\n", total);
   
    //2.-------------------------------
    printf("\n\n2.冒泡排序方法2：\n");
   
    int arr_2[len];
   
    for(i = 0;i < len;i++){
        arr_2[i] = arr[i];
    }
   
    total = 0;
   
    //2.冒泡排序(注意细节，这里使用 i < len - 1，j < len - 1)
    for(i = 0;i < len - 1; i++){
        for(j = 0; j < len - 1; j++){
            if(arr_2[j] > arr_2[j + 1]){
                temp = arr_2[j];
                arr_2[j] = arr_2[j + 1];
                arr_2[j + 1] = temp;
            }
            total++;
        }
    }
   
    for(i = 0; i < len; i++){
        printf("%d ", arr_2[i]);
    }
   
    printf("\n循环次数：%d\n", total);
   
    //3.-------------------------------
    printf("\n\n3.冒泡排序方法3：\n");
   
    int arr_3[len];
   
    for(i = 0;i < len;i++){
        arr_3[i] = arr[i];
    }
   
    total = 0;
   
    //3.冒泡排序(注意细节，这里使用 i < len，j < (len - i - 1))
    for(i = 0;i < len; i++){
        for(j = 0; j < (len - i - 1); j++){
            if(arr_3[j] > arr_3[j + 1]){
                temp = arr_3[j];
                arr_3[j] = arr_3[j + 1];
                arr_3[j + 1] = temp;
            }
            total++;
        }
    }
   
    for(i = 0; i < len; i++){
        printf("%d ", arr_3[i]);
    }
   
    printf("\n循环次数：%d\n", total);
   
    //4.-------------------------------
    printf("\n\n4.冒泡排序方法4(得到错误结果)：\n");
   
    int arr_4[len];
   
    for(i = 0;i < len;i++){
        arr_4[i] = arr[i];
    }
   
    total = 0;
   
    //4.冒泡排序(注意细节，这里使用 i < len，j < (len - i))
    for(i = 0;i < len; i++){
        for(j = 0; j < (len - i); j++){
            if(arr_4[j] > arr_4[j + 1]){
                temp = arr_4[j];
                arr_4[j] = arr_4[j + 1];
                arr_4[j + 1] = temp;
            }
            total++;
        }
    }
   
    for(i = 0; i < len; i++){
        printf("%d ", arr_4[i]);
    }
   
    printf("\n循环次数：%d\n", total);
   
    //5.-------------------------------
    printf("\n\n5.选择排序：\n");
   
    int arr2[len];
   
    for(i = 0;i < len;i++){
        arr2[i] = arr[i];
    }
   
    total = 0;
   
    //5.选择排序
    for(i = 0;i < len - 1; i++){
        for(j = i + 1; j < len; j++){
            if(arr2[i] > arr2[j]){
                temp = arr2[i];
                arr2[i] = arr2[j];
                arr2[j] = temp;
            }
            total++;
        }
    }
   
    for(i = 0; i < len; i++){
        printf("%d ", arr2[i]);
    }
   
    printf("\n循环次数：%d\n", total);
}

 

2.执行后的效果，自已去比对：

 

3.根据实验，最优的冒泡排序算法应该是：

//待排序数组
int arr[] = {89, 23, 5, 98};
 
int i, j, temp, len;
len = sizeof(arr)/sizeof(arr[0]);
 
for(i = 0; i < len; i++){
    for(j = 0; j < (len - i - 1); j++){
        if(arr[j] > arr[j + 1]){
            temp = arr[j];
            arr[j] = arr[j + 1];
            arr[j + 1] = temp;
        }
    }
}

  其实上面的冒泡排序算法还可以继续优化，如果检测到排序中一个循环里没有数据交换，就应该立即跳出所有循环，程序没有必要继续傻跑。