冒泡排序法(C语言)

发布于 2021-04-11  100 次阅读


文章目录[隐藏]

以从小到大排序为例,冒泡排序的整体思想是这样的:

  • 从数组头部开始,不断比较相邻的两个元素的大小,让较大的元素逐渐往后移动(交换两个元素的值),直到数组的末尾。经过第一轮的比较,就可以找到最大的元素,并将它移动到最后一个位置。
  • 第一轮结束后,继续第二轮。仍然从数组头部开始比较,让较大的元素逐渐往后移动,直到数组的倒数第二个元素为止。经过第二轮的比较,就可以找到次大的元素,并将它放到倒数第二个位置。
  • 以此类推,进行 n-1(n 为数组长度)轮“冒泡”后,就可以将所有的元素都排列好。
    整个排序过程就好像气泡不断从水里冒出来,最大的先出来,次大的第二出来,最小的最后出来,所以将这种排序方式称为冒泡排序(Bubble Sort)。

以“3 2 4 1”为例对冒泡排序进行说明。
第一轮 排序过程
3 2 4 1 (最初)
2 3 4 1 (比较3和2,交换)
2 3 4 1 (比较3和4,不交换)
2 3 1 4 (比较4和1,交换)
第一轮结束,最大的数字 4 已经在最后面,因此第二轮排序只需要对前面三个数进行比较。
第二轮 排序过程
2 3 1 4 (第一轮排序结果)
2 3 1 4 (比较2和3,不交换)
2 1 3 4 (比较3和1,交换)
第二轮结束,次大的数字 3 已经排在倒数第二个位置,所以第三轮只需要比较前两个元素。
第三轮 排序过程
2 1 3 4 (第二轮排序结果)
1 2 3 4 (比较2和1,交换)
至此,排序结束。

算法总结及实现

对拥有 n 个元素的数组 R[n] 进行 n-1 轮比较。
第一轮,逐个比较 (R[1], R[2]), (R[2], R[3]), (R[3], R[4]), ……. (R[N-1], R[N]),最大的元素被移动到 R[n] 上。
第二轮,逐个比较 (R[1], R[2]), (R[2], R[3]), (R[3], R[4]), ……. (R[N-2], R[N-1]),次大的元素被移动到 R[n-1] 上。
。。。。。。
以此类推,直到整个数组从小到大排序。

具体的代码实现如下所示:

#include <stdio.h>
int main(){
    int nums[10] = {4, 5, 2, 10, 7, 1, 8, 3, 6, 9};
    int i, j, temp;

    //冒泡排序算法:进行 n-1 轮比较
    for(i=0; i<10-1; i++){
        //每一轮比较前 n-1-i 个,也就是说,已经排序好的最后 i 个不用比较
        for(j=0; j<10-1-i; j++){
            if(nums[j] > nums[j+1]){
                temp = nums[j];
                nums[j] = nums[j+1];
                nums[j+1] = temp;
            }
        }
    }

    //输出排序后的数组
    for(i=0; i<10; i++){
        printf("%d ", nums[i]);
    }
    printf("\n");

    return 0;
}

优化算法
上面的算法是大部分教材中提供的算法,其中有一点是可以优化的:当比较到第 i 轮的时候,如果剩下的元素已经排序好了,那么就不用再继续比较了,跳出循环即可,这样就减少了比较的次数,提高了执行效率。
未经优化的算法一定会进行 n-1 轮比较,经过优化的算法最多进行 n-1 轮比较,高下立判。
优化后的算法实现如下所示:

#include <stdio.h>
int main(){
    int nums[10] = {4, 5, 2, 10, 7, 1, 8, 3, 6, 9};
    int i, j, temp, isSorted;

    //优化算法:最多进行 n-1 轮比较
    for(i=0; i<10-1; i++){
        isSorted = 1;  //假设剩下的元素已经排序好了
        for(j=0; j<10-1-i; j++){
            if(nums[j] > nums[j+1]){
                temp = nums[j];
                nums[j] = nums[j+1];
                nums[j+1] = temp;
                isSorted = 0;  //一旦需要交换数组元素,就说明剩下的元素没有排序好
            }
        }
        if(isSorted) break; //如果没有发生交换,说明剩下的元素已经排序好了
    }

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

    return 0;
}

外设置了一个变量 isSorted,用它作为标志,值为“真”表示剩下的元素已经排序好了,值为“假”表示剩下的元素还未排序好。

每一轮比较之前,我们预先假设剩下的元素已经排序好了,并将 isSorted 设置为“真”,一旦在比较过程中需要交换元素,就说明假设是错的,剩下的元素没有排序好,于是将 isSorted 的值更改为“假”。

每一轮循环结束后,通过检测 isSorted 的值就知道剩下的元素是否排序好。

//      一个可以自己调节数字个数的排序
#include<stdio.h>
int main(void)
{
    int i,j,t,x;
    int a[1000];
    printf("请输入你要排序的数字数目(<=1000):");
    scanf("%d",&x);

    for(i=0;i<x;i++){
        scanf("%d",&a[i]);
    }
    for(i=0;i<x-1;i++)
            {
        for(j=0;j<x-1-i;j++)
        {
            if(a[j]>a[j+1])
    {
                t = a[j];
                a[j] = a[j+1];
                a[j+1] = t;
            }
        }
    }

    printf("宁输入的数字排序结果为:");
    for(i=0;i<x;i++)
    {
        printf("%d ",a[i]);
    }

    return 0;
}

Python写法

def bubbleSort(arr):
    n = len(arr)

    # 遍历所有数组元素
    for i in range(n):

        # Last i elements are already in place
        for j in range(0, n-i-1):

            if arr[j] > arr[j+1] :
                arr[j], arr[j+1] = arr[j+1], arr[j]

arr = [64, 34, 25, 12, 22, 11, 90]

bubbleSort(arr)

print ("排序后的数组:")
for i in range(len(arr)):
    print ("%d" %arr[i])

擦肩而过的概率