冒泡排序 - 简书

冒泡排序

一、算法描述：

1.比较相邻的元素，如果前一个比后一个大，交换
2.第一次排序第1个和第2个一对，比较与交换，然后第二个和第三个对比交换，以此类推，直到比较倒数第二个和最后一个为止
3.重复步骤2，直到没有任何数字需要进行比较

二、算法分析

时间复杂度

1.正序（一趟扫描即可完成排序）

所需的关键字比较次数 C 和记录移动次数 N 都是最小值：（n：数据规模）
C_min=n-1
M_min=0

2.逆序(进行n-1次排序)

每次排序都要进行 n-i 次比较（1<=i<=n-1），且每次比较都需要移动，这种情况，比较和移动次数都达到了最大
C_man= n(n-1)/2=O(n²)
M_man=3n(n-1)/2=O(n²)
冒泡排序的平均时间复杂度为O(n²)

算法稳定性

冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较，交换也发生在这两个元素之间。所以，如果两个元素相等，是不会再交换的；如果两个相等的元素没有相邻，那么即使通过前面的两两交换把两个相邻起来，这时候也不会交换，所以相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法

三、具体代码

1.Java

public class BubbleSort implements IArraySort {

    @Override
    public int[] sort(int[] sourceArray) throws Exception {
        // 对 arr 进行拷贝，不改变参数内容
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
        for (int i = 1; i < arr.length; i++) {
            // 设定一个标记，若为true，则表示此次循环没有进行交换，也就是待排序列已经有序，排序已经完成。每次遍历标志位都要先置为true，才能判断后面的元素是否发生了交换
            boolean flag = true;
            for (int j = 0; j < arr.length - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    int tmp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = tmp;
                    flag = false;
                }
            }
//// 判断标志位是否为false，如果为false，说明后面的元素已经有序，就直接return
            if (flag) {
                break;
            }
        }
        return arr;
    }
}

2.C语言

/* 冒泡排序 */
/* 1. 从当前元素起，向后依次比较每一对相邻元素，若逆序则交换 */
/* 2. 对所有元素均重复以上步骤，直至最后一个元素 */
/* elemType arr[]: 排序目标数组; int len: 元素个数 */
void bubbleSort (elemType arr[], int len) {
    elemType temp;
    int i, j;
    for (i=0; i<len-1; i++) /* 外循环为排序趟数，len个数进行len-1趟 */
        for (j=0; j<len-1-i; j++) { /* 内循环为每趟比较的次数，第i趟比较len-i次 */
            if (arr[j] > arr[j+1]) { /* 相邻元素比较，若逆序则交换（升序为左大于右，降序反之） */
                temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
}
 
int main (void) {
    elemType arr[ARR_LEN] = {3,5,1,-7,4,9,-6,8,10,4};
    int len = 10;
    int i;
    bubbleSort (arr, len);
    for (i=0; i<len; i++)
    printf ("%d\t", arr[i]);
    putchar ('\n');
    return 0;
}

3.C++

#include <iostream>
using namespace std;
template<typename T>
//整数或浮点数皆可使用
void bubble_sort(T arr[], int len){
    int i, j;  T temp;
    for (i = 0; i < len - 1; i++)
        for (j = 0; j < len - 1 - i; j++)
        if (arr[j] > arr[j + 1]){
            temp = arr[j];
            arr[j] = arr[j + 1];
            arr[j + 1] = temp;
        }
}
int main(){
    int arr[] = { 61, 17, 29, 22, 34, 60, 72, 21, 50, 1, 62 };
    int len = (int) sizeof(arr) / sizeof(*arr);
    bubble_sort(arr, len);
    for (int i = 0; i < len; i++)
        cout << arr[i] << ' ';
    cout << endl;
    float arrf[] = { 17.5, 19.1, 0.6, 1.9, 10.5, 12.4, 3.8, 19.7, 1.5, 25.4, 28.6, 4.4, 23.8, 5.4 };
    len = (int) sizeof(arrf) / sizeof(*arrf);
    bubble_sort(arrf, len);
    for (int i = 0; i < len; i++)
        cout << arrf[i] << ' ';
    return 0;
}

4.Kotlin

fun bubbleSort(array: Array<Int>) { 
   val arrayLength = array.size    
   for (i in 0 until arrayLength) {        
       for (j in 0 until arrayLength - i - 1) {            
           if (array[j] > array[j + 1]) {                
               val temp = array[j]                
               array[j] = array[j + 1]                
               array[j + 1] = temp           
           }       
       }   
   }   
   // Prints result.
}

最后编辑于：2020.09.19 01:02:31