lwz blog

# 冒泡排序

基于交换排序，根据序列中两个元素关键字的对比结果来对换这两个记录在序列中的位置，当两个元素的关键字相等时，它们的相对位置不变。

# 基本思想

从前往后或者从后往前 两两对比相邻元素的值，若为逆序 则交换他们的位置，直到序列比较完毕。


int arr = {9,1,2,5,7,4,8,6,3,5};

//举例从左到右的冒泡排序
//第一组
//第一轮比较 比较下表为0和1的两个元素 9和1 9>1 交换位置
int arr = {1,9,2,5,7,4,8,6,3,5};

//第二轮比较 比较下表为1和2的两个元素 9和2 9>2 交换位置
int arr = {1,2,9,5,7,4,8,6,3,5};

//第三轮比较 比较下表为2和3的两个元素 9和5 9>5 交换位置
int arr = {1,2,5,9,7,4,8,6,3,5};

//第四轮比较 比较下表为3和4的两个元素 9和7 9>7 交换位置
int arr = {1,2,5,7,9,4,8,6,3,5};

// ... 依次类推 第一组比较完毕
int arr = {1,2,5,7,4,8,6,3,5,9};

//第二组
//第一轮比较 这里注意：无需比较下表为0和1的两个元素 直接比较下表为1和2的两个元素 2和5 2<5 不交换位置

//... 依次类推 第二组比较完毕
  

    //代码实现
 void bubbleSort(int *arr, int length) {

  //从右到左的冒泡排序
   for (int i = 0; i < length - 1; ++i) {
       bool flag = false;
       for (int j = length - 1; j > i; --j) {
           if (arr[j] < arr[j - 1]) {
               flag = true;
               int temp = arr[j];
               arr[j] = arr[j - 1];
               arr[j - 1] = temp;
           }
       }
       if (flag==false) {
           return;
       }
   }

    //从左到右的冒泡排序
    //循环对比的次数
    for (int i = 0; i < length - 1; ++i) {
        bool flag = false;
        //每次循环都会将最大的数放到最后 所以每次循环都会减少一个数
        for (int j = 0; j < length - i - 1; ++j) {
            //如果前一个数比后一个数大 则交换位置
            if (arr[j + 1] < arr[j]) {
                int temp = arr[j + 1];
                arr[j + 1] = arr[j];
                arr[j] = temp;
                flag = true;
            }

        }
        //这里注意的是 如果一次循环下来 没有发生交换 则说明已经是有序的了 直接返回
        if (flag == false) {
            return;
        }
    }
}

# 算法分析

# 空间复杂度

O(1)

# 时间复杂度

最好情况下 O(n) 比较次数为 n-1，交换次数为 0

  • 一般就是有序的 是不需要移动的 也是常数级别的

最坏情况下 O(n^2) 比较次数为 n(n-1)/2，交换次数为 n(n-1)/2。(N-1)+(N-2)+...+1=N(N-1)/2。

  • 一般就是逆序的，每一项都需要移动

平均情况下 O(n^2) 比较次数为 n(n-1)/2，交换次数为 n(n-1)/2。

# 稳定性

稳定

  • 两个相等的元素不会交换位置

# 其他

可以使用链表来实现冒泡排序，这样就不需要交换元素，只需要改变指针的指向即可。因为冒泡排序不需要随机访问元素，所以链表实现的冒泡排序也是一种很好的思路。

← 快速排序 →