冒泡排序、選擇排序、插入排序、快速排序

目錄

1.?冒泡排序?(Bubble?Sort)

算法思路分析

代碼實現

復雜度分析

2. 選擇排序?(Selection Sort)

算法思路分析

代碼實現

復雜度分析

3. 插入排序?(Insertion Sort)

算法思路分析

代碼實現

復雜度分析

4. 快速排序 (Quick?Sort)

算法思路分析

代碼實現

復雜度分析

5. 歸并排序?(Merge?Sort)

算法思路分析

代碼實現

復雜度分析

6.?堆排序?(Heap?Sort)

算法思路分析

代碼實現

復雜度分析

算法性能對比總結


排序算法穩定性解釋:

  • 穩定排序:相等的元素在排序后保持原有的相對順序
  • 不穩定排序:相等的元素在排序后可能改變原有的相對順序

比如:

原始順序是?4?, 2,?4?,?1,?3,排序后變成了?1, 2,?3,?4?, 4?

  • 原來:4??在?4??前面
  • 現在:4??仍然在?4??前面

這就是穩定排序

1.?冒泡排序?(Bubble?Sort)

算法思路分析

冒泡排序是最簡單的排序算法之一,其核心思想是:

  1. 相鄰比較:比較相鄰的兩個元素,如果第一個比第二個大,則交換它們
  2. 逐步冒泡:每一輪比較后,最大的元素會"冒泡"到數組的末尾
  3. 重復執行:重復n-1輪,直到所有元素都排好序

代碼實現

/*** 冒泡排序算法* * 算法思路:* 1. 比較相鄰的兩個元素,如果第一個比第二個大,則交換它們* 2. 對每一對相鄰元素執行同樣的操作,從開始第一對到結尾的最后一對* 3. 重復以上步驟,每次都能將當前最大的元素"冒泡"到數組末尾* 4. 重復n-1輪,直到沒有任何一對數字需要比較*/
public static void bubbleSort(int[] arr) {int n = arr.length;// 外層循環控制排序輪數,總共需要n-1輪for (int i = 0; i < n - 1; i++) {// 設置一個標志位,用于優化算法// 如果某一輪沒有發生交換,說明數組已經有序,可以提前退出boolean swapped = false;// 內層循環進行相鄰元素比較和交換// 每輪排序后,最大的元素會"冒泡"到數組末尾// 因此內層循環的范圍可以逐漸縮小for (int j = 0; j < n - 1 - i; 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;}}
}

復雜度分析

  • 時間復雜度:O(n2) - 最壞和平均情況都是O(n2)
  • 空間復雜度:O(1)?- 只需要一個臨時變量
  • 穩定性:穩定排序

2. 選擇排序?(Selection Sort)

算法思路分析

選擇排序的核心思想是:

  1. 找最小值:在未排序序列中找到最小元素
  2. 交換位置:將找到的最小元素與未排序序列的第一個元素交換位置
  3. 重復執行:重復上述過程,直到所有元素都排好序

代碼實現

/*** 選擇排序算法* * 算法思路:* 1. 在未排序序列中找到最小元素,存放到排序序列的起始位置* 2. 然后,再從剩余未排序元素中繼續尋找最小元素* 3. 重復第二步,直到所有元素均排序完畢*/
public static void selectionSort(int[] arr) {int n = arr.length;// 外層循環控制排序輪數for (int i = 0; i < n - 1; i++) {// 假設當前位置的元素是最小的int minIndex = i;// 在未排序序列中尋找最小元素for (int j = i + 1; j < n; j++) {// 如果找到更小的元素,更新最小元素的索引if (arr[j] < arr[minIndex]) {minIndex = j;}}// 將找到的最小元素與當前位置的元素交換if (minIndex != i) {int temp = arr[i];arr[i] = arr[minIndex];arr[minIndex] = temp;}}
}

復雜度分析

  • 時間復雜度:O(n2)?- 無論最好、最壞、平均情況都是O(n2)
  • 空間復雜度:O(1) - 只需要一個臨時變量
  • 穩定性:不穩定排序

3. 插入排序?(Insertion Sort)

算法思路分析

插入排序的核心思想是:

  1. 構建有序序列:將第一個元素看作已排序序列
  2. 逐個插入:對于未排序數據,在已排序序列中從后向前掃描,找到相應位置并插入
  3. 重復執行:重復上述過程,直到所有元素都插入到有序序列中

代碼實現

/*** 插入排序算法* * 算法思路:* 1. 從第一個元素開始,該元素可以認為已經被排序* 2. 取出下一個元素,在已經排序的元素序列中從后向前掃描* 3. 如果該元素(已排序)大于新元素,將該元素移到下一位置* 4. 重復步驟3,直到找到已排序的元素小于或者等于新元素的位置* 5. 將新元素插入到該位置后* 6. 重復步驟2~5*/
public static void insertionSort(int[] arr) {int n = arr.length;// 從第二個元素開始,逐個插入到已排序序列中for (int i = 1; i < n; i++) {// 保存當前要插入的元素int key = arr[i];// j指向已排序序列的最后一個元素int j = i - 1;// 從后向前掃描已排序序列,尋找插入位置// 如果已排序序列中的元素大于key,則將其向后移動while (j >= 0 && arr[j] > key) {arr[j + 1] = arr[j];j--;}// 找到插入位置,將key插入arr[j + 1] = key;}
}

復雜度分析

  • 時間復雜度:O(n2) - 最壞和平均情況,最好情況O(n)(已排序數組)
  • 空間復雜度:O(1)?- 只需要一個臨時變量
  • 穩定性:穩定排序

4. 快速排序 (Quick?Sort)

算法思路分析

快速排序是一種高效的排序算法,使用分治策略:

  1. 選擇基準:從數組中選擇一個基準元素(通常是最后一個元素)
  2. 分區操作:將數組分為兩部分,左邊都小于基準,右邊都大于基準
  3. 遞歸排序:對左右兩部分分別進行快速排序
  4. 合并結果:由于分區操作,合并時數組已經有序

代碼實現

/*** 快速排序算法* * 算法思路:* 1. 選擇一個基準元素(通常是最后一個元素)* 2. 將數組分為兩部分:左邊都小于基準,右邊都大于基準* 3. 對左右兩部分分別遞歸執行快速排序* 4. 由于分區操作,合并時數組已經有序*/
public static void quickSort(int[] arr) {quickSort(arr, 0, arr.length - 1);
}/*** 快速排序的遞歸實現* @param arr 待排序數組* @param low 起始索引* @param high 結束索引*/
private static void quickSort(int[] arr, int low, int high) {// 遞歸終止條件:當起始索引小于結束索引時if (low < high) {// 進行分區操作,返回基準元素的最終位置int pi = partition(arr, low, high);// 遞歸排序基準元素左邊的子數組quickSort(arr, low, pi - 1);// 遞歸排序基準元素右邊的子數組quickSort(arr, pi + 1, high);}
}/*** 分區操作:將數組分為兩部分* @param arr 待分區數組* @param low 起始索引* @param high 結束索引* @return 基準元素的最終位置*/
private static int partition(int[] arr, int low, int high) {// 選擇最后一個元素作為基準int pivot = arr[high];// i指向小于基準元素的最后一個位置int i = low - 1;// 遍歷數組,將小于基準的元素移到左邊for (int j = low; j < high; j++) {// 如果當前元素小于基準if (arr[j] < pivot) {i++;// 交換元素int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}}// 將基準元素放到正確的位置int temp = arr[i + 1];arr[i + 1] = arr[high];arr[high] = temp;// 返回基準元素的最終位置return i + 1;
}

復雜度分析

  • 時間復雜度:O(n log n) - 平均情況,最壞情況O(n2)
  • 空間復雜度:O(log n)?- 遞歸調用棧的深度
  • 穩定性:不穩定排序

5. 歸并排序?(Merge?Sort)

算法思路分析

歸并排序是一種穩定的排序算法,使用分治策略:

  1. 分解:將數組分成兩個子數組,遞歸地對子數組進行排序
  2. 合并:將兩個已排序的子數組合并成一個有序數組
  3. 遞歸執行:重復上述過程,直到所有元素都排好序

代碼實現

/*** 歸并排序算法* * 算法思路:* 1. 將數組分成兩個子數組,遞歸地對子數組進行排序* 2. 將兩個已排序的子數組合并成一個有序數組* 3. 重復上述過程,直到所有元素都排好序*/
public static void mergeSort(int[] arr) {mergeSort(arr, 0, arr.length - 1);
}/*** 歸并排序的遞歸實現* @param arr 待排序數組* @param left 左邊界* @param right 右邊界*/
private static void mergeSort(int[] arr, int left, int right) {// 遞歸終止條件:當左邊界小于右邊界時if (left < right) {// 計算中間位置int mid = left + (right - left) / 2;// 遞歸排序左半部分mergeSort(arr, left, mid);// 遞歸排序右半部分mergeSort(arr, mid + 1, right);// 合并兩個已排序的子數組merge(arr, left, mid, right);}
}/*** 合并兩個已排序的子數組* @param arr 原數組* @param left 左邊界* @param mid 中間位置* @param right 右邊界*/
private static void merge(int[] arr, int left, int mid, int right) {// 計算兩個子數組的長度int n1 = mid - left + 1;int n2 = right - mid;// 創建臨時數組來存儲兩個子數組int[] leftArray = new int[n1];int[] rightArray = new int[n2];// 復制數據到臨時數組for (int i = 0; i < n1; i++) {leftArray[i] = arr[left + i];}for (int j = 0; j < n2; j++) {rightArray[j] = arr[mid + 1 + j];}// 合并兩個子數組int i = 0, j = 0, k = left;// 比較兩個子數組的元素,將較小的元素放入原數組while (i < n1 && j < n2) {if (leftArray[i] <= rightArray[j]) {arr[k] = leftArray[i];i++;} else {arr[k] = rightArray[j];j++;}k++;}// 將剩余的元素復制到原數組while (i < n1) {arr[k] = leftArray[i];i++;k++;}while (j < n2) {arr[k] = rightArray[j];j++;k++;}
}

復雜度分析

  • 時間復雜度:O(n?log?n) - 無論最好、最壞、平均情況都是O(n?log?n)
  • 空間復雜度:O(n)?- 需要額外的數組來存儲合并結果
  • 穩定性:穩定排序

6.?堆排序?(Heap?Sort)

算法思路分析

堆排序是一種基于堆數據結構的排序算法:

  1. 構建堆:將數組構建成最大堆(或最小堆)
  2. 提取根節點:將堆的根節點(最大值)與最后一個元素交換
  3. 調整堆:對剩余的n-1個元素重新構建堆
  4. 重復執行:重復上述過程,直到所有元素都排好序

代碼實現

/*** 堆排序算法* * 算法思路:* 1. 將數組構建成最大堆* 2. 將堆的根節點(最大值)與最后一個元素交換* 3. 對剩余的n-1個元素重新構建堆* 4. 重復上述過程,直到所有元素都排好序*/
public static void heapSort(int[] arr) {int n = arr.length;// 構建最大堆// 從最后一個非葉子節點開始,自底向上構建堆for (int i = n / 2 - 1; i >= 0; i--) {heapify(arr, n, i);}// 逐個提取堆頂元素(最大值)for (int i = n - 1; i > 0; i--) {// 將堆頂元素(最大值)與最后一個元素交換int temp = arr[0];arr[0] = arr[i];arr[i] = temp;// 對剩余的i個元素重新構建最大堆heapify(arr, i, 0);}
}/*** 將以root為根的子樹調整為最大堆* @param arr 數組* @param n 堆的大小* @param root 根節點的索引*/
private static void heapify(int[] arr, int n, int root) {// 假設根節點是最大的int largest = root;// 計算左子節點的索引int left = 2 * root + 1;// 計算右子節點的索引int right = 2 * root + 2;// 如果左子節點存在且大于根節點if (left < n && arr[left] > arr[largest]) {largest = left;}// 如果右子節點存在且大于當前最大值if (right < n && arr[right] > arr[largest]) {largest = right;}// 如果最大值不是根節點if (largest != root) {// 交換根節點和最大值int temp = arr[root];arr[root] = arr[largest];arr[largest] = temp;// 遞歸調整被交換的子樹heapify(arr, n, largest);}
}

復雜度分析

  • 時間復雜度:O(n?log n) - 無論最好、最壞、平均情況都是O(n?log n)
  • 空間復雜度:O(1)?-?原地排序
  • 穩定性:不穩定排序

堆排序原理參考:堆排序步驟推演-CSDN博客


算法性能對比總結

排序算法時間復雜度空間復雜度穩定性適用場景
冒泡排序O(n2)O(1)穩定小數據量
選擇排序O(n2)O(1)不穩定小數據量,交換次數少
插入排序O(n2)O(1)穩定小數據量,基本有序
快速排序O(n log n)O(log n)不穩定大數據量,實際應用
歸并排序O(n log n)O(n)穩定大數據量,要求穩定
堆排序O(n?log n)O(1)不穩定大數據量,原地排序

?使用建議:小數據量(n?< 50):使用插入排序,代碼簡單且效率較高;大數據量:優先使用快速排序,平均性能最好;要求穩定性:使用歸并排序;內存受限:使用堆排序,原地排序;

推薦:Java的Arrays.sort(),此方法已經為我們提供了高效的排序實現

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

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

相關文章

PHP語言基礎知識(超詳細)第一節

一. PHP簡介: PHP即“超文本預處理器”,創建于1994年,是一種通用開源腳本語言。PHP是在服務器端執行的腳本語言,與C語言類似,是常用的網站編程語言。PHP獨特的語法混合了C、Java、Perl以及 PHP 自創的語法。利于學習,使用廣泛,主要適用于Web開發領域。 二. PHP的優點:…

Reloaded-II項目:解決GitHub下載Mod缺少DLL文件的問題

Reloaded-II項目&#xff1a;解決GitHub下載Mod缺少DLL文件的問題 問題現象分析 在使用Reloaded-II項目加載從GitHub下載的"Debug Stuff"模組時&#xff0c;用戶遇到了一個常見的技術問題&#xff1a;系統提示缺少DLL文件&#xff0c;導致模組無法正常運行。這種情況…

0-1搭建springboot+vue的教務管理系統(核心源碼)

目錄 后端核心代碼&#xff1a; control層 service 層 mapper層 后端核心代碼&#xff1a; control層&#xff1a; classControlsImpl package com.itheima.controls.impl;import com.itheima.mapper.ClassMapper; import com.itheima.pojo.Clazz; import com.itheima.po…

Ubuntu中man手冊不全解決以及man手冊中英文切換方法

步入正題之前&#xff0c;先來幫助大家了解一下man手冊的作用&#xff0c;讓大家對其有更深的理解并充分利用一、man 手冊的作用?man 手冊&#xff0c;即 manual pages&#xff0c;是 Linux 系統自帶的幫助文檔系統。通過 man 命令&#xff0c;用戶能快速獲取系統中幾乎所有命…

數據結構----線性表(棧及其棧的實現)C語言 學習筆記

棧&#xff1a;線性邏輯結構棧的分類 順序棧&#xff1a;順序存儲結構實現的棧鏈式棧&#xff1a;鏈式存儲結構實現的棧相關概念線性表&#xff1a;可以在任意位置操作棧&#xff1a;對線性表進行約束只能在一端插入和刪除操作的線性表&#xff0c;中間不允許操作。棧底&#x…

手滑誤操作? vue + Element UI 封裝二次確認框 | 附源碼

一諾最近在做后臺管理系統時&#xff0c;遇到一個很常見但又容易被忽視的小問題&#xff1a;單選框切換時&#xff0c;用戶一不小心點錯&#xff0c;原有配置就沒了&#xff0c;數據丟失&#xff0c;后悔也來不及。你是不是也遇到過類似的場景&#xff1f;比如切換網絡模式、切…

力扣刷題367——有效的完全平方數

力扣刷題367——有效的完全平方數&#xff08;69的相似題&#xff09; 題目&#xff1a; 給你一個正整數 num 。如果 num 是一個完全平方數&#xff0c;則返回 true &#xff0c;否則返回 false 。 完全平方數 是一個可以寫成某個整數的平方的整數。換句話說&#xff0c;它可以…

kubernetes架構原理與集群環境部署

kubernetes架構原理與集群環境部署概述為什么需要 KubernetesKubernetes 帶來的挑戰kubernetes架構解析master 節點的組件(1)API server(2)scheduler(3)Controller Manager(4)etcdNode 節點包含的組件(1)容器運行時(2)kubelet(3)kube-proxy代理kubernetes 網絡插件(1)Flannel 網…

Python爬蟲實戰:Requests與Selenium詳解

目錄 一 網絡爬蟲的了解 1 爬蟲庫 urllib庫 requests庫 scrapy庫 selenium庫 2 注意&#xff01;&#xff01;&#xff01; 二 requests庫 1 request庫的安裝 2 認識網頁資源 3 獲取網頁資源 4 小案例 5 代理服務器 三 selenium 1 準備工作 2 應用 3 實例 一 網…

什么是樂觀鎖?什么是悲觀鎖?

&#x1f512; 深入淺出&#xff1a;樂觀鎖 vs 悲觀鎖終極對決&#xff01;面試必考知識點詳解 各位CSDN的小伙伴們好呀&#xff01;&#x1f44b; 我是雪碧聊技術&#xff0c;今天給大家帶來高并發編程中的核心概念——樂觀鎖與悲觀鎖的深度解析&#xff01;&#x1f4bb; 無論…

HTML前端性能優化完整指南

圖片優化&#xff1a;性能優化的重中之重 重新審視圖片的必要性 在開始優化之前&#xff0c;首先需要思考一個根本問題&#xff1a;要實現預期的視覺效果&#xff0c;真的需要使用圖片嗎&#xff1f; 隨著Web技術的快速發展&#xff0c;許多以往只能通過圖片實現的效果&…

數據煉金術:用Python做智能數據整理員

數據煉金術&#xff1a;用Python做智能數據整理員 解鎖自動化魔法&#xff1a;文件批量重命名Excel智能清洗數據凈化全流程實戰 一、數據整理的困境與破局之道 你是否面臨這些數據噩夢場景&#xff1f; &#x1f9e9; ??混亂文件目錄??&#xff1a;最終版_報告_V4(1).doc…

HTML基礎P1 | HTML基本元素

HTML標簽標簽名放在<>中&#xff0c;如<body>大部分標簽成對出現&#xff0c;如<h1>為開始標簽&#xff0c;</h1>為其對應的結束標簽&#xff0c;少數標簽只有開始標簽&#xff0c;如換行標簽<br/>&#xff0c;成為"單標簽"有的標簽中…

LVS集群搭建

集群是為了解決某個特定問題將多臺計算機組合起來形成的單個系統知識點&#xff1a;1.關鍵術語&#xff1a;VS&#xff1a;Virtual Server&#xff08;調度器&#xff09;RS&#xff1a;Real Server&#xff08;真實服務器&#xff09;CIP&#xff1a;Client IP&#xff08;客戶…

吳恩達《AI for everyone》第一周課程筆記

課程的核心目標&#xff1a;- AI是什么&#xff1f; - AI能做什么&#xff1f; - AI最擅長什么類型的任務&#xff1f; - AI怎么做決策&#xff1f; - 企業為什么需要AI戰略&#xff1f;導航Machine Learning 機器學習> 最常見的機器學習類型&#xff1a; > 人工智能中最…

iOS App 電池消耗管理與優化 提升用戶體驗的完整指南

在當今智能手機的使用中&#xff0c;電池壽命和續航能力是用戶選擇App時的重要考慮因素之一。iOS設備的電池管理功能較為封閉&#xff0c;這也讓開發者、產品經理以及普通用戶對于App的電池消耗有時無法全面了解。而如果你的App因電池消耗過快而遭到用戶卸載&#xff0c;無論功…

關于用git上傳遠程庫的一些常見命令使用和常見問題:

克隆遠程庫gitee到本地用命令git clone git clone https://gitee.com/automated-piggy-senior/20250717-test.gitLinux/macOS 終端&#xff1a; 執行 touch readme.txt&#xff08;創建空文件&#xff09;&#xff0c;或 echo "這是說明文件" > readme.txt&#…

想刪除表中重復數據,只留下一條,sql怎么寫

PostgreSQL 方法: DELETE FROM tbl_case_model WHERE id NOT IN (SELECT MIN(id) -- 保留id最小的記錄FROM tbl_case_modelGROUP BYcolumn1, -- 替換為實際重復列名column2, -- 繼續添加重復列... -- [所有需要比較的列] );因為我這次遇到的情況比較特殊&#xff0…

微服務中token鑒權設計的4種方式

1. JWT鑒權 「概述」&#xff1a;JWT是一種用于雙方之間安全傳輸信息的簡潔的、URL安全的令牌標準。它基于JSON格式&#xff0c;包含三個部分&#xff1a;頭部&#xff08;Header&#xff09;、負載&#xff08;Payload&#xff09;和簽名&#xff08;Signature&#xff09;。J…

nodejs搭建

1.創建一個空文件夾&#xff0c;在vscode中打開 2.執行命令開啟package文件 npm init -y3.設置根目錄文件app.js 先執行 npm install express 命令安裝 express 模塊 執行 npm install cors 命令安裝 cors 模塊 // app.js const express require(express) const app express…