您现在的位置是:首页 >技术教程 >【算法】冒泡排序网站首页技术教程
【算法】冒泡排序
一.冒泡排序
主要思想:
反复交换相邻的元素,使较大的元素 逐渐冒泡到数组的末尾,从而实现排序的效果
实现过程:
1.遍历待排序数组,比较相邻的元素,如果前面的元素比后面的元素大,
就交换这两个元素的位置
2.重复上述操作,直至不再需要交换
3.返回排序后的结果
演示:(64 34 25 12 22 11 90)
第一躺:
64 34 25 12 22 11 90
34 64 25 12 22 11 90 (64>34 交换)
34 25 64 12 22 11 90 ( 64>25 交换)
34 25 12 64 22 11 90 (64>12 交换)
34 25 12 22 64 11 90 (64>22 交换)
34 25 12 22 11 64 90 (64>11 交换)
34 25 12 22 11 64 90 (64<90 不交换)
第二趟:
34 25 12 22 11 64 90
25 34 12 22 11 64 90 (34>25 交换)
25 12 34 22 11 64 90 (34>12 交换)
25 12 22 34 11 64 90 (34>22 交换)
25 12 22 11 34 64 90 (34>11 交换)
25 12 22 11 34 64 90 (34<64 不交换)
25 12 22 11 34 64 90 (64<90 不交换)
第三趟:
25 12 22 11 34 64 90
12 25 22 11 34 64 90 (25>12 交换)
12 22 25 11 34 64 90 (25>22 交换)
12 22 11 25 34 64 90 (25>11 交换)
12 22 11 25 34 64 90 (25<34 不交换)
12 22 11 25 34 64 90(34<64 不交换)
12 22 11 25 34 64 90 (64<90 不交换)
第三趟:
12 22 11 25 34 64 90
12 22 11 25 34 64 90 (12<22 不交换)
12 11 22 25 34 64 90 (22>11 交换)
12 11 22 25 34 64 90 (22<25 不交换)
12 11 22 25 34 64 90 (25<34 不交换)
12 11 22 25 34 64 90 (34<64 不交换)
12 11 22 25 34 64 90 (64<90 不交换)
第四趟:
12 11 22 25 34 64 90
11 12 22 25 34 64 90
总结:
冒泡排序的时间复杂度为O(n^2),是一种稳定的排序方法,在实际应用中可能效率低。
二. C语言版
#include<stdio.h>
#include<Windows.h>
void bubble_sort(int arr[] ,int n){
int i ,j,temp;
for(i=0;i<n-1;i++){
for(j=0;j<n-1;j++){
if(arr[j] > arr[j+1]){
temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
}
}
}
}
int main(){
int arr[] ={64,34,25,12,22,11,90};
int n=sizeof(arr)/sizeof(arr[0]);
bubble_sort(arr,n);
printf("Sorted array:
");
for(int i=0;i<n;i++){
printf("%d ",arr[i]);
}
system("pause");
return 0;
}
代码解析:
#include<stdio.h>
#include<Windows.h>
void bubble_sort(int arr[] ,int n){
//冒泡排序算法,参数为整数数组和数组大小
int i ,j,temp;
//定义比较用的两个指针i和j
for(i=0;i<n-1;i++){
//外层循环用于遍历所有元素
for(j=0;j<n-i-1;j++){
//内层循环用于循环比较相邻元素,从头一个一直到后一个未归为的元素
if(arr[j] > arr[j+1]){
//如果前面的数大于后面的数
temp=arr[j];
//交换他们的位置
arr[j]=arr[j+1];
arr[j+1]=temp;
}
}
}
}
int main(){
int arr[] ={64,34,25,12,22,11,90};
//声明未排序的整数数组
int n=sizeof(arr)/sizeof(arr[0]);
//通过数组长度计算元素数量
bubble_sort(arr,n);
//调用冒泡排序算法
printf("Sorted array:
");
for(int i=0;i<n;i++){
//循环遍历排序后的数组并打印出来
printf("%d ",arr[i]);
}
system("pause");
return 0;
}
调试:
三.Java版
package BubbleSort;
public class BubbleSort {
public static void main(String[] args) {
int [] arr={64,34,25,12,22,11,90};
bubbleSort(arr);
for(int num:arr){
System.out.println(num+"");
}
}
private static void bubbleSort(int[] arr) {
int temp;
for(int i=0;i<arr.length-1;i++){
for(int j=0;j<arr.length-i-1;j++){
if(arr[j]>arr[j+1]){
temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
}
}
}
}
}
调试: