冒泡排序——C与JavaScript实现

2021-12-13 数据结构与算法 #C #JavaScript

简单的冒泡算法。

算法思路

冒泡排序的核心思想是对大小为 n 的数组进行 n 轮排序，第一轮从里面揪出来最大的“泡泡”，冒到最顶上，第二轮揪出来第二大的“泡泡”，冒到除了“大泡”以外的最顶上……以此类推。

至于过程中如何让泡泡冒上去，则是通过交换实现，为了便于说明，把泡泡们从前到后进行编号，即 1 号泡泡、2 号泡泡、3 号泡泡……每个泡泡对应一个坑位，也编号为 1 号坑位、2 号坑位、3 号坑位……简单说来，初始时，1 号泡泡待在 1 号坑位，2 号泡泡待在 2 号坑，3 号泡泡待在 3 号坑……

然后，每轮中发生的排序过程如下：

比较 1 号坑和 2 号坑中的泡泡，如果前者大于后者，则交换两个坑中的泡泡，即让前者冒上去。
继续比较 2 号坑和 3 号坑中的泡泡，要注意，经过前一次比较，2 号坑中不一定还是 2 号泡泡了，而是 1 号泡泡和 2 号泡泡中较大的那个泡泡。
然后是 3 号坑和 4 号坑中的泡泡，此时，3 号坑中是 1、2、3 号泡泡中最大的那个泡泡。
以此类推，一直比较到第 n-1 号坑和第 n 号坑，最后，第 n 号坑中放的就是所有泡泡中最大的那个泡泡啦。

经过上面一轮的比较后，到第 2 轮时，由于已经可以确定第 n 号坑中是最大的泡泡，所以最后一次比较，也就是第 n-1 号坑和第 n 号坑的比较，是必然不会发生交换的。因此，第二轮的实际效果就是把第二大的泡泡冒到了 n-1 号坑。

代码实现

C

首先讲一下 main 函数，它负责随机生成一个数组，然后调用排序函数对数组进行排序，再然后下面没了。

int main(void)
{
    int nums[SIZE];
    generateNums(nums, SIZE); // 生成 SIZE 大小的数组，放在 nums 中

    printf("origin:\n");
    for (int i = 0; i < SIZE; i++)
    {
        printf("%d ", nums[i]);
    }

    bubbleSort(nums, SIZE);

    printf("\nsorted:\n");
    for (int i = 0; i < SIZE; i++)
    {
        printf("%d ", nums[i]);
    }
}

接下来就是排序函数 bubbleSort，该讲的都在注释里了，应该不需要再多解释了。

void bubbleSort(int *arr, int size)
{
    int flag;                      //记录本轮是否发生过交换
    for (int i = 0; i < size; i++) //第一轮得到最大值，第二轮得到第二大值，以此类推
    {
        flag = 0; // 初始为未发生交换
        for (int j = 0; j < size; j++)
        {
            if (arr[j] > arr[j + 1])
            {
                swap(arr + j, arr + j + 1); // 交换

                if (!flag) // 修改flag
                {
                    flag = 1;
                }
            }
        }
        if (!flag)
        {
            break;
        }
    }
}

这里就需要讲一下代码中未曾在算法思路里提到过的 flag 了，很显然，如果一轮比较下来，一次交换都没有发生，说明没两个相邻泡泡之间的大小关系都是正确的，也就是排序已经完成了，此时当然也就没必要再继续一轮轮跑下去了，所以此时直接终止排序就可以了。

此外，代码中的 swap 函数用来交换两个泡泡，怎么做的就不必说了吧。

此此外，代码其实还有继续优化的余地，比如每一轮都是从头比较到尾，而实际上对于那些在前面轮次冒到顶的泡泡，已经不需要再比较了，所以上面的代码存在许多多余的比较。

JavaScript

js 写起来仿佛就要方便得多，这里直接放代码了，思路跟用 C 没什么不同，只是实现差异而已。

const SIZE = 20
const MIN = 0
const MAX = 100

let bubbleSort = (arr) => {
  let flag
  for (let i = 0; i < arr.length; i++) {
    flag = false
    for (let j = 0; j < arr.length; j++) {
      if (arr[j] > arr[j + 1]) {
        arr[j] += arr[j + 1]
        arr[j + 1] = arr[j] - arr[j + 1]
        arr[j] -= arr[j + 1]

        if (!flag) {
          flag = true
        }
      }
    }
    if ((flag = false)) {
      break
    }
  }
}

let arr = []
for (let i = 0; i < SIZE; i++) {
  arr.push(Math.round(Math.random() * (MAX - MIN + 1) + MIN))
}

console.log('before:\n', arr)

bubbleSort(arr)

console.log('sorted:\n', arr)

Chipmunk & Panda

-- 鼠熊部落格

冒泡排序——C与JavaScript实现

算法思路

代码实现

C

JavaScript