06.1 冒泡排序

2024 年 7 月 22 日 星期一

06.1 冒泡排序

冒泡排序详解

1. 引言

冒泡排序是一种简单直观的排序算法,其基本思想是通过多次遍历数组,比较相邻元素并交换,使得每一轮遍历后最大的元素都位于数组末尾

2. 冒泡排序原理

冒泡排序的核心思想是相邻元素两两比较,将较大的元素逐步交换到右侧,通过多轮遍历实现整体排序。

3. 冒泡排序步骤

冒泡排序的具体步骤如下:

  1. 从第一个元素开始,依次比较相邻元素。
  2. 如果前一个元素大于后一个元素,则交换它们的位置。
  3. 继续比较下一组相邻元素,重复步骤2。
  4. 一轮遍历后,最大的元素将移动到数组末尾。
  5. 重复以上步骤,每轮遍历确定一个最大元素的位置,直至整个数组有序。

4. 冒泡排序代码示例

4. 1 Python语言实现的冒泡排序

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

    for i in range(n):
        # 每一轮遍历确定一个最大元素的位置
        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]
bubble_sort(arr)
print("排序后的数组:", arr)

4. 2 Java语言实现的冒泡排序

package org.example;  
  
import java.util.Arrays;  
  
public class BubbleSort {  
    public static void main(String[] args) {  
        int arr[] = {-1, -2, 3, 7, 4, 10};  
  
        bubbleSort(arr);  
  
        int arr2[] = new int[80000];  
        for (int i = 0; i < 80000; i++) {  
            arr2[i] = (int)(Math.random()*8000000);  
        }  
  
        System.out.println("arr2:" + Arrays.toString(arr2));  
  
//        bubbleSort(arr2);  
//        for (int i = 0; i < arr.length - 1 - 0; i++) {  
//            if (arr[i] > arr[i + 1]) {  
//                temp = arr[i];  
//                arr[i] = arr[i + 1];  
//                arr[i + 1] = temp;  
//            }  
//        }  
//        System.out.println("第1躺排序:" + Arrays.toString(arr));  
//  
//        for (int i = 0; i < arr.length - 1 - 1; i++) {  
//            if (arr[i] > arr[i + 1]) {  
//                temp = arr[i];  
//                arr[i] = arr[i + 1];  
//                arr[i + 1] = temp;  
//            }  
//        }  
//        System.out.println("第2躺排序:" + Arrays.toString(arr));  
//  
//        for (int i = 0; i < arr.length - 3; i++) {  
//            if (arr[i] > arr[i + 1]) {  
//                temp = arr[i];  
//                arr[i] = arr[i + 1];  
//                arr[i + 1] = temp;  
//            }  
//        }  
//        System.out.println("第3躺排序:" + Arrays.toString(arr));  
//  
//        for (int i = 0; i < arr.length - 4; i++) {  
//            if (arr[i] > arr[i + 1]) {  
//                temp = arr[i];  
//                arr[i] = arr[i + 1];  
//                arr[i + 1] = temp;  
//            }  
//        }  
//        System.out.println("第4躺排序:" + Arrays.toString(arr));  
    }  
  
    public static void bubbleSort(int[] arr){  
        boolean flag = false;//判断是否进行了交换  
        System.out.println("初始数组序列:" + Arrays.toString(arr));  
        int temp = 0;  
  
        for (int j = 0; j < arr.length - 1; j++) {  
            for (int i = 0; i < arr.length - (j + 1); i++) {  
                if (arr[i] > arr[i + 1]) {  
                    flag = true;  
                    temp = arr[i];  
                    arr[i] = arr[i + 1];  
                    arr[i + 1] = temp;  
                }  
            }  
            if (!flag) {  
//                说明没有交换,则可以结束,因为已经有序  
                break;  
            } else {  
                flag = false;  
            }  
            System.out.printf("第%d躺排序:", j + 1);  
            System.out.printf(Arrays.toString(arr));  
            System.out.println();  
        }  
        System.out.println("冒泡排序:" + Arrays.toString(arr));  
    }  
}

5. 冒泡排序的时间复杂度

冒泡排序的时间复杂度为O(n^2),其中n为数组的长度。这是因为在最坏的情况下,需要进行n轮遍历,每轮遍历的比较次数为n-1。

6. 总结

冒泡排序虽然简单,但在大规模数据集上性能较差,不适合处理大量数据。然而,它的思想易于理解,是初学者学习排序算法的良好起点。在实际应用中,更高效的排序算法如快速排序、归并排序通常被优先选择。

  • Loading...
  • Loading...
  • Loading...
  • Loading...
  • Loading...