【算法基礎】冒泡排序算法 - JAVA

一、算法基礎

1.1 什么是冒泡排序

冒泡排序是一種簡單直觀的比較排序算法。它重復地走訪待排序的數列,依次比較相鄰兩個元素,如果順序錯誤就交換它們,直到沒有元素需要交換為止。

1.2 基本思想

  • 比較相鄰元素:從頭開始,兩兩比較相鄰元素
  • 交換位置:如果前一個元素大于后一個元素,則交換位置
  • 重復操作:每完成一次迭代,最大的元素會"冒泡"到數組末尾
  • 多次迭代:重復以上步驟,每次排除已排好序的末尾元素

1.3 時間復雜度

  • 最好情況:O(n),當數組已經排好序
  • 最壞情況:O(n2),當數組逆序排列
  • 平均情況:O(n2)

二、冒泡排序的分類

2.1 標準冒泡排序

標準版本每次將最大元素冒泡到末尾:

  • 外層循環:控制排序輪數,最多n-1輪
  • 內層循環:控制每輪比較次數,逐漸減少
  • 無優化:即使數組已排序仍會執行全部循環

2.2 優化冒泡排序

通過標記變量檢測一輪比較中是否有交換發生:

  • 設置標記:初始假設本輪無交換
  • 發生交換:更新標記變量
  • 提前終止:若一輪比較無交換發生,則排序完成

三、冒泡排序實現

3.1 標準實現

public class BubbleSort {/*** 標準冒泡排序算法* @param arr 待排序數組*/public static void bubbleSort(int[] arr) {int n = arr.length;// 外層循環控制排序輪數for (int i = 0; i < n - 1; i++) {// 內層循環進行相鄰元素比較和交換// 每輪結束后,最大的i+1個元素已經排好序for (int j = 0; j < n - i - 1; j++) {// 如果當前元素大于下一個元素,交換它們if (arr[j] > arr[j + 1]) {int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}}}
}

3.2 優化實現

public class OptimizedBubbleSort {/*** 優化版冒泡排序算法* @param arr 待排序數組*/public static void bubbleSort(int[] arr) {int n = arr.length;boolean swapped;// 外層循環控制排序輪數for (int i = 0; i < n - 1; i++) {swapped = false;// 內層循環進行相鄰元素比較和交換for (int j = 0; j < n - i - 1; j++) {if (arr[j] > arr[j + 1]) {// 交換元素int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;// 標記發生了交換swapped = true;}}// 如果沒有發生交換,說明數組已經有序,提前結束if (!swapped) {break;}}}
}

3.3 雙向冒泡排序(雞尾酒排序)

public class CocktailSort {/*** 雙向冒泡排序(雞尾酒排序)算法* @param arr 待排序數組*/public static void cocktailSort(int[] arr) {int left = 0;int right = arr.length - 1;boolean swapped;while (left < right) {swapped = false;// 從左向右,將最大元素冒泡到右側for (int i = left; i < right; i++) {if (arr[i] > arr[i + 1]) {int temp = arr[i];arr[i] = arr[i + 1];arr[i + 1] = temp;swapped = true;}}// 如果沒有交換,數組已經有序if (!swapped) {break;}right--; // 最大元素已經到位,縮小右邊界swapped = false;// 從右向左,將最小元素冒泡到左側for (int i = right; i > left; i--) {if (arr[i] < arr[i - 1]) {int temp = arr[i];arr[i] = arr[i - 1];arr[i - 1] = temp;swapped = true;}}// 如果沒有交換,數組已經有序if (!swapped) {break;}left++; // 最小元素已經到位,縮小左邊界}}
}

四、算法分析與優化

4.1 理論推導

冒泡排序的工作原理可以用以下數學表達式描述:

  • 比較次數:(n-1) + (n-2) + ... + 1 = n(n-1)/2
  • 最大交換次數:同上 n(n-1)/2
  • 元素移動次數:最多3×n(n-1)/2(每次交換需要3次移動)

4.2 優化策略

  1. 提前終止優化:如前述,檢測是否有交換發生
  2. 記錄最后交換位置:每輪記錄最后一次交換的位置,下一輪只需掃描到該位置即可
  3. 奇偶交替掃描:類似雞尾酒排序,減少"烏龜"(小元素靠后)的情況
public class EnhancedBubbleSort {/*** 記錄最后交換位置的優化冒泡排序* @param arr 待排序數組*/public static void bubbleSort(int[] arr) {int n = arr.length;int lastSwappedIndex = n - 1;int newLastSwappedIndex;while (lastSwappedIndex > 0) {newLastSwappedIndex = 0;for (int i = 0; i < lastSwappedIndex; i++) {if (arr[i] > arr[i + 1]) {// 交換元素int temp = arr[i];arr[i] = arr[i + 1];arr[i + 1] = temp;// 記錄最后交換的位置newLastSwappedIndex = i;}}// 更新下一輪排序的終止位置lastSwappedIndex = newLastSwappedIndex;}}
}

五、完整示例程序

public class BubbleSortDemo {public static void main(String[] args) {// 測試數據int[] arr = {64, 34, 25, 12, 22, 11, 90};System.out.println("原始數組: ");printArray(arr);// 執行優化版冒泡排序optimizedBubbleSort(arr);System.out.println("\n排序后數組: ");printArray(arr);}/*** 優化的冒泡排序實現*/public static void optimizedBubbleSort(int[] arr) {int n = arr.length;boolean swapped;for (int i = 0; i < n - 1; i++) {swapped = false;for (int j = 0; j < n - i - 1; j++) {// 如果當前元素大于下一個元素,交換它們if (arr[j] > arr[j + 1]) {swap(arr, j, j + 1);swapped = true;}}// 如果沒有發生交換,數組已經有序if (!swapped) {System.out.println("提前結束于第 " + (i + 1) + " 輪");break;}}}/*** 交換數組中兩個元素*/private static void swap(int[] arr, int i, int j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}/*** 打印數組*/private static void printArray(int[] arr) {for (int num : arr) {System.out.print(num + " ");}System.out.println();}
}

六、總結

冒泡排序是一種經典的排序算法,其特點如下:

6.1 優點

  • 實現簡單:代碼直觀易懂,適合教學使用
  • 穩定性好:相等元素不會改變相對順序
  • 原地排序:不需要額外空間
  • 自適應性:對于部分有序數據效率較高

6.2 缺點

  • 效率低下:平均時間復雜度為O(n2)
  • 比較次數多:即使數據已經有序,基本版本仍需大量比較

6.3 適用場景

  • 小規模數據:元素數量較少時表現尚可
  • 教學演示:算法思想簡單直觀
  • 接近有序數據:優化版本在這種情況下效率較高

冒泡排序雖然在大規模數據中效率不高,但其思想簡單,實現容易,是學習排序算法的良好起點。在實際應用中,可根據數據特性選擇更高效的排序算法,如快速排序、歸并排序等。

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:http://www.pswp.cn/pingmian/79322.shtml
繁體地址,請注明出處:http://hk.pswp.cn/pingmian/79322.shtml
英文地址,請注明出處:http://en.pswp.cn/pingmian/79322.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

0902Redux_狀態管理-react-仿低代碼平臺項目

文章目錄 1 Redux 概述1.1 核心概念1.2 基本組成1.3 工作流程1.4 中間件&#xff08;Middleware&#xff09;1.5 適用場景1.6 優缺點1.7 Redux Toolkit&#xff08;現代推薦&#xff09;1.8 與其他工具的對比1.9 總結 2 todoList 待辦事項案例3 Redux開發者工具3.1 核心功能3.2…

《ATPL地面培訓教材13:飛行原理》——第6章:阻力

翻譯&#xff1a;Leweslyh&#xff1b;工具&#xff1a;Cursor & Claude 3.7&#xff1b;過程稿 第6章&#xff1a;阻力 目錄 引言寄生阻力誘導阻力減少誘導阻力的方法升力對寄生阻力的影響飛機總阻力飛機總重量對總阻力的影響高度對總阻力的影響構型對總阻力的影響速度穩…

C++總結01-類型相關

一、數據存儲 1.程序數據段 ? 靜態&#xff08;全局&#xff09;數據區&#xff1a;全局變量、靜態變量 ? 堆內存&#xff1a;程序員手動分配、手動釋放 ? 棧內存&#xff1a;編譯器自動分配、自動釋放 ? 常量區&#xff1a;編譯時大小、值確定不可修改 2.程序代碼段 ?…

【Hot 100】94. 二叉樹的中序遍歷

目錄 引言二叉樹的中序遍歷我的解題代碼優化更清晰的表述建議&#xff1a; &#x1f64b;?♂? 作者&#xff1a;海碼007&#x1f4dc; 專欄&#xff1a;算法專欄&#x1f4a5; 標題&#xff1a;【Hot 100】94. 二叉樹的中序遍歷?? 寄語&#xff1a;書到用時方恨少&#xff…

大語言模型(LLMs)微調技術總結

文章目錄 全面總結當前大語言模型&#xff08;LLM&#xff09;微調技術1. 引言2. 為什么需要微調&#xff1f;3. 微調技術分類概覽4. 各種微調技術詳細介紹4.1 基礎微調方法4.1.1 有監督微調&#xff08;Supervised Fine-Tuning, SFT&#xff09;4.1.2 全參數微調&#xff08;F…

解決Maven項目中報錯“java不支持版本6即更高的版本 7”

錯誤背景 當Maven項目編譯或運行時出現錯誤提示 Java不支持版本6即更高的版本7&#xff0c;通常是由于項目配置的JDK版本與當前環境或編譯器設置不一致導致的。例如&#xff1a; 項目配置的Java版本為6或7&#xff0c;但實際使用的是JDK 17。Maven或IDE的編譯器未正確指定目標…

C++筆記-多態(包含虛函數,純虛函數和虛函數表等)

1.多態的概念 多態(polymorphism)的概念:通俗來說&#xff0c;就是多種形態。多態分為編譯時多態(靜態多態)和運行時多態(動態多態)&#xff0c;這里我們重點講運行時多態&#xff0c;編譯時多態(靜態多態)和運行時多態(動態多態)。編譯時多態(靜態多態)主要就是我們前面講的函…

【Unity】MVP框架的使用例子

在提到MVP之前&#xff0c;可以先看看這篇MVC的帖子&#xff1a; 【Unity】MVC的簡單分享以及一個在UI中使用的例子 MVC的不足之處&#xff1a; 在MVC的使用中&#xff0c;會發現View層直接調用了Model層的引用&#xff0c;即這兩個層之間存在著一定的耦合性&#xff0c;而MV…

前端js學算法-實踐

1、兩數之和 const twoSum (nums, target) > {const obj {}for (let m 0; m < nums.length; m) {const cur nums[m]const diff target - curif(obj.hasOwnProperty(diff)){ // 查詢對象中是否存在目標值-當前值鍵值對console.log([obj[diff], m]) // 存在則直接獲取…

《MATLAB實戰訓練營:從入門到工業級應用》趣味入門篇-用聲音合成玩音樂:MATLAB電子琴制作(超級趣味實踐版)

《MATLAB實戰訓練營&#xff1a;從入門到工業級應用》趣味入門篇-用聲音合成玩音樂&#xff1a;MATLAB電子琴制作&#xff08;超級趣味實踐版&#xff09; 開篇&#xff1a;當MATLAB遇見音樂 - 一場數字與藝術的浪漫邂逅 想象一下&#xff0c;你正坐在一臺古老的鋼琴前&#x…

實戰探討:為什么 Redis Zset 選擇跳表?

在了解了跳表的原理和實現后&#xff0c;一個常見的問題&#xff08;尤其是在面試中&#xff09;隨之而來&#xff1a;為什么像 Redis 的有序集合 (Zset) 這樣的高性能組件會選擇使用跳表&#xff0c;而不是大家熟知的平衡樹&#xff08;如紅黑樹&#xff09;呢&#xff1f; 對…

數據結構-線性結構(鏈表、棧、隊列)實現

公共頭文件common.h #define TRUE 1 #define FALSE 0// 定義節點數據類型 #define DATA_TYPE int單鏈表C語言實現 SingleList.h #pragma once#include "common.h"typedef struct Node {DATA_TYPE data;struct Node *next; } Node;Node *initList();void headInser…

高中數學聯賽模擬試題精選學數學系列第3套幾何題

△ A B C \triangle ABC △ABC 的內切圓 ⊙ I \odot I ⊙I 分別與邊 B C BC BC, C A CA CA, A B AB AB 相切于點 D D D, E E E, F F F, D D ′ DD DD′ 為 ⊙ I \odot I ⊙I 的直徑, 過圓心 I I I 作直線 A D ′ AD AD′ 的垂線 l l l, 直線 l l l 分別與 D E DE…

使用 ossutil 上傳文件到阿里云 OSS

在處理文件存儲和傳輸時&#xff0c;阿里云的對象存儲服務&#xff08;OSS&#xff09;是一個非常方便的選擇。特別是在需要批量上傳文件或通過命令行工具進行文件管理時&#xff0c;ossutil提供了強大的功能。本文將詳細說明如何使用 ossutil 上傳文件到阿里云 OSS&#xff0c…

DeepSeek與MySQL:開啟數據智能新時代

目錄 一、引言&#xff1a;技術融合的力量二、DeepSeek 與 MySQL&#xff1a;技術基石2.1 DeepSeek 技術探秘2.2 MySQL 數據庫深度解析 三、DeepSeek 與 MySQL 集成&#xff1a;從理論到實踐3.1 集成原理剖析3.2 集成步驟詳解 四、應用案例&#xff1a;實戰中的價值體現4.1 電商…

WebAPI項目從Newtonsoft.Json遷移到System.Text.Json踩坑備忘

1.控制器層方法返回類型不能為元組 控制器層方法返回類型為元組時&#xff0c;序列化結果為空。 因為元組沒有屬性只有field&#xff0c;除非使用IncludeFields參數專門指定&#xff0c;否則使用System.Text.Json進行序列化時不會序列化field var options new JsonSerializ…

202553-sql

目錄 一、196. 刪除重復的電子郵箱 - 力扣&#xff08;LeetCode&#xff09; 二、602. 好友申請 II &#xff1a;誰有最多的好友 - 力扣&#xff08;LeetCode&#xff09; 三、176. 第二高的薪水 - 力扣&#xff08;LeetCode&#xff09; 一、196. 刪除重復的電子郵箱 - 力扣…

Spring Boot的GraalVM支持:構建低資源消耗微服務

文章目錄 引言一、GraalVM原生鏡像技術概述二、Spring Boot 3.x的GraalVM支持三、適配GraalVM的關鍵技術點四、構建原生鏡像微服務實例五、性能優化與最佳實踐總結 引言 微服務架構已成為企業應用開發的主流模式&#xff0c;但隨著微服務數量的增加&#xff0c;資源消耗問題日…

pip 常用命令及配置

一、python -m pip install 和 pip install 的區別 在講解 pip 的命令之前&#xff0c;我們有必要了解一下 python -m pip install 和 pip install 的區別&#xff0c;以便于我們在不同的場景使用不同的方式。 python -m pip install 命令使用 python 可執行文件將 pip 模塊作…

Vue高級特性實戰:自定義指令、插槽與路由全解析

一、自定義指令 1.如何自定義指令 ⑴.全局注冊語法 通過 Vue.directive 方法注冊&#xff0c;語法格式為&#xff1a; Vue.directive(指令名, {// 鉤子函數&#xff0c;元素插入父節點時觸發&#xff08;僅保證父節點存在&#xff0c;不一定已插入文檔&#xff09;inserted(…