您现在的位置是:首页 >技术教程 >【算法】冒泡排序网站首页技术教程

【算法】冒泡排序

freedomSTUDENT 2023-06-26 04:00:02
简介【算法】冒泡排序

一.冒泡排序

主要思想:

反复交换相邻的元素,使较大的元素 逐渐冒泡到数组的末尾,从而实现排序的效果

实现过程:

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;
                }
            }
        }
    }
}

调试:

 

 

风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。