常用排序算法之冒泡排序 (C、Javascript实现)

本文主要是介绍常用排序算法之冒泡排序 (C、Javascript实现)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1.“冒泡”的由来

按照气泡在水中上浮的顺序进行模拟的一种算法，一般较大的气泡上浮越快，较小的气泡则在其后。

(介是由于浮力,别问我为什么 \(^o^)/~)

2.基本思想

每次比较两个相邻的元素，如果按照从大到小的顺序依次排序，一旦他们出现错误顺序，则将其相互置换。

3.算法流程(未优化)

假设有3个元素3，1，2，将这3个数按大到小的顺序进行排序，也就是说越往后的数越小。

0 1 2

第一轮比较，(第一个数与每一个数进行比较，找到错误顺序，将其与第一个数进行交换。)

首先，比较第一个(3)与第一个(3)；

此时，不用进行交换顺序。

然后，比较第一个(3)与第二个数(5)；

很显然，后一个数5比3大，出现错误顺序，因此交换两者的顺序。顺序如下图，

0 1 2

然后，将新排好序的第一个数(5)与第三个数(1)进行比较；

此时，不用进行交换顺序。(第一轮结束)

第二轮比较，(第二个数与每一个数进行比较，找到错误顺序，将其与第二个数进行交换。)

首先，比较第二个数(3)与第一个数(5)；

此时，不用进行交换顺序。

然后，比较第二个数(3)与第二个数(3);

此时，不用进行交换顺序。

最后，比较第二个数(3)与第三个数(1)；

此时，不用进行交换顺序。

第三轮比较，(第二个数与每一个数进行比较，找到错误顺序，将其与第二个数进行交换。)

首先，比较第三个数(1)与第一个数(5)；

此时，不用进行交换顺序。

然后，比较第三个数(1)与第二个数(3);

此时，不用进行交换顺序。

最后，比较第三个数(1)与第三个数(1)；

此时，不用进行交换顺序。

4.核心代码

for(i=0;i<N;i++){for(j=0;j<N;j++){
<span style="white-space:pre">		</span>if(a[i]>a[j]){<span style="white-space:pre">			</span>int temp = a[i];
<span style="white-space:pre">			</span>a[i]=a[j];<span style="white-space:pre">			</span>a[j]=temp;
<span style="white-space:pre">		</span>}}
}

5.代码优化

通过以上例子，是不是觉得每i轮数比较完之后，第i个数之前的数都是已经排好序的，我们只需要将i之后的数进行再排序，这样所用的时间将是原来算法的一半。1/2O(n2)

for(i=0;i<N;i++){for(j=i;j<N;j++){
<span style="white-space:pre">	</span> <span style="white-space:pre">	</span>if(a[i]>a[j]){
<span style="white-space:pre">			</span>int temp = a[i];
<span style="white-space:pre">		</span> <span style="white-space:pre">	</span>a[i]=a[j];
<span style="white-space:pre">		</span> <span style="white-space:pre">	</span>a[j]=temp;
<span style="white-space:pre">	</span> <span style="white-space:pre">	</span>}}
}

6.完整代码

#include <stdio.h>
#define N 5
int main(void){int a[N]={3,5,1,2,4};int i=0;printf("数组初始顺序如下:\n");for(;i<N;i++){printf("%-5d",a[i]);}printf("\n-------------------\n");int j;for(i=0;i<N;i++){for(j=i;j<N;j++){if(a[i]>a[j]){int temp = a[i];a[i]=a[j];a[j]=temp;}}}printf("\n数组排序后的顺序如下:\n");for(i=0;i<N;i++){printf("%-5d",a[i]);}return 0;}

7.运行结果