Java數據結構9-排序

1. 排序的概念及引用

1.1 排序的概念

排序:所謂排序,就是使一串記錄,按照其中的某個或某些關鍵字的大小,遞增或遞減的排列起來的操作。

穩定性:假定在待排序的記錄序列中,存在多個具有相同的關鍵字的記錄,若經過排序,這些記錄的相對次序保持不變,即在原序列中,r[i]=r[j],且r[i]在r[j]之前,而在排序后的序列中,r[i]仍在r[j]之前,則稱這種排序算法是穩定的;否則稱為不穩定的。

在這里插入圖片描述

內部排序:數據元素全部放在內存中的排序。

外部排序:數據元素太多不能同時放在內存中,根據排序過程的要求不能在內外存之間移動數據的排序。

1.2 排序運用

在這里插入圖片描述

1.3 常見的排序算法

在這里插入圖片描述

2. 常見排序算法的實現

2.1 插入排序

2.1.1基本思想

直接插入排序是一種簡單的插入排序法,其基本思想是:

把待排序的記錄按其關鍵碼值的大小逐個插入到一個已經排好序的有序序列中,直到所有的記錄插入完為止,得到一個新的有序序列 。實際中我們玩撲克牌時,就用了插入排序的思想。

在這里插入圖片描述

2.1.2 直接插入排序

當插入第i(i>=1)個元素時,前面的array[0],array[1],…,array[i-1]已經排好序,此時用array[i]的排序碼與array[i-1],array[i-2],…的排序碼順序進行比較,找到插入位置即將array[i]插入,原來位置上的元素順序后移

在這里插入圖片描述

 public static void insertSort(int[] array) {for (int i = 1; i < array.length; i++) {int tmp = array[i];int j = i-1;for (; j >= 0; j--) {if (array[j] > tmp) {array[j+1] = array[j];} else {break;}}array[j+1] = tmp;}}

直接插入排序的特性總結:

  1. 元素集合越接近有序,直接插入排序算法的時間效率越高
  2. 時間復雜度:O(N^2)
  3. 空間復雜度:O(1),它是一種穩定的排序算法
  4. 穩定性:穩定

2.1.3 希爾排序( 縮小增量排序 )

希爾排序法又稱縮小增量法。希爾排序法的基本思想是:先選定一個整數,把待排序文件中所有記錄分成多個組,所有距離為的記錄分在同一組內,并對每一組內的記錄進行排序。然后,取,重復上述分組和排序的工作。當到達=1時,所有記錄在統一組內排好序。

在這里插入圖片描述

public static void shellSort(int[] array) {int gap = array.length;while (gap > 1) {gap /= 2;shell(array, gap);}}private static void shell(int[] array, int gap) {for (int i = gap; i < array.length; i++) {int tmp = array[i];int j = i-gap;for (; j >= 0; j-=gap) {if (array[j] > tmp) {array[j+gap] = array[j];} else {break;}}array[j+gap] = tmp;}}

  1. 希爾排序是對直接插入排序的優化。
  2. 當gap > 1時都是預排序,目的是讓數組更接近于有序。當gap == 1時,數組已經接近有序的了,這樣就會很
    快。這樣整體而言,可以達到優化的效果。我們實現后可以進行性能測試的對比。
  3. 希爾排序的時間復雜度不好計算,因為gap的取值方法很多,導致很難去計算,因此在好些樹中給出的希爾排
    序的時間復雜度都不固定
  4. 穩定性:不穩定

2.2 選擇排序

2.2.1基本思想

每一次從待排序的數據元素中選出最小(或最大)的一個元素,存放在序列的起始位置,直到全部待排序的數據元素排完 。

2.2.2 直接選擇排序

  • 在元素集合array[i]–array[n-1]中選擇關鍵碼最大(小)的數據元素
  • 若它不是這組元素中的最后一個(第一個)元素,則將它與這組元素中的最后一個(第一個)元素交換
  • 在剩余的array[i]–array[n-2](array[i+1]–array[n-1])集合中,重復上述步驟,直到集合剩余1個元素

在這里插入圖片描述

public static void selectSort1(int [] array) {for (int i = 0; i < array.length; i++) {int minIndex = i;for (int j = i+1; j < array.length; j++) {if (array[j] < array[minIndex]){minIndex = j;}}swap(array, i, minIndex);}}public static void selectSort2(int [] array) {int left = 0;int right = array.length-1;while (left < right) {int minIndex = left;int maxIndex = left;for (int i = left+1; i <= right; i++) {if (array[i] < array[minIndex]) {minIndex = i;}if (array[i] > array[maxIndex]) {maxIndex = i;}}swap(array, minIndex, left);if (maxIndex == left) {maxIndex = minIndex;}swap(array, maxIndex, right);left++;right--;}}private static void swap(int[] array, int i, int j) {int tmp = array[i];array[i] = array[j];array[j] = tmp;}

【直接選擇排序的特性總結】

  1. 直接選擇排序思考非常好理解,但是效率不是很好。實際中很少使用
  2. 時間復雜度:O(N^2)
  3. 空間復雜度:O(1)
  4. 穩定性:不穩定

2.2.3 堆排序

堆排序(Heapsort)是指利用堆積樹(堆)這種數據結構所設計的一種排序算法,它是選擇排序的一種。它是通過堆來進行選擇數據。需要注意的是排升序要建大堆,排降序建小堆。

private static void swap(int[] array, int i, int j) {int tmp = array[i];array[i] = array[j];array[j] = tmp;}public static void heapSort(int[] array) {createBigHeap(array);int end = array.length-1;while (end >= 0) {swap(array, 0, end);shiftDown(0, array, end);end--;}}private static void createBigHeap(int[] array) {for (int parent = (array.length-1-1) / 2; parent >=0 ; parent--) {shiftDown(parent, array, array.length);}}private static void shiftDown(int parent, int[] array, int end) {int child = 2*parent+1;while (child < end) {if (child + 1 < end && array[child] < array[child+1]) {child++;}if (array[child] > array[parent]) {swap(array, child, parent);parent = child;child = 2*parent+1;} else {break;}}}

【冒泡排序的特性總結】

  1. 冒泡排序是一種非常容易理解的排序
  2. 時間復雜度:O(N^2)
  3. 空間復雜度:O(1)
  4. 穩定性:穩定

2.3 交換排序

基本思想:所謂交換,就是根據序列中兩個記錄鍵值的比較結果來對換這兩個記錄在序列中的位置,交換排序的特點是:將鍵值較大的記錄向序列的尾部移動,鍵值較小的記錄向序列的前部移動。

2.3.1冒泡排序


在這里插入圖片描述

public static void bubbleSort(int[] array) {boolean flg = false;for (int i = 0; i < array.length-1; i++) {for (int j = 0; j < array.length-1-i; j++) {if (array[j+1] < array[j]) {swap(array, j, j+1);flg =true;}}if (!flg) {break;}}}

【冒泡排序的特性總結】

  1. 冒泡排序是一種非常容易理解的排序
  2. 時間復雜度:O(N^2)
  3. 空間復雜度:O(1)
  4. 穩定性:穩定

2.3.2 快速排序

快速排序是Hoare于1962年提出的一種二叉樹結構的交換排序方法,其基本思想為:任取待排序元素序列中的某元素作為基準值,按照該排序碼將待排序集合分割成兩子序列,左子序列中所有元素均小于基準值,右子序列中所有元素均大于基準值,然后最左右子序列重復該過程,直到所有元素都排列在相應位置上為止。

public static void quickSort(int[] array) {quick(array, 0, array.length-1);}private static void quick(int[] array, int start, int end) {if (start >= end) {return;}int par = partition(array, start, end);quick(array, start, par-1);quick(array, par+1, end);
}private static int partition(int[] array, int left, int right) {int tmp = array[left];while (left < right) {while (left < right && array[right] >= tmp) {right--;}array[left] = array[right];while (left < right && array[left] <= tmp) {left++;}array[right] = array[left];}array[left] = tmp;return left;}private static void swap(int[] array, int i, int j) {int tmp = array[i];array[i] = array[j];array[j] = tmp;
}

上述為快速排序遞歸實現的主框架,發現與二叉樹前序遍歷規則非常像,同學們在寫遞歸框架時可想想二叉樹前序遍歷規則即可快速寫出來,后序只需分析如何按照基準值來對區間中數據進行劃分的方式即可。

將區間按照基準值劃分為左右兩半部分的常見方式有:

  1. Hoare版

    在這里插入圖片描述

public static void quickSort(int[] array) {quick(array, 0, array.length-1);}private static void quick(int[] array, int start, int end) {if (start >= end) {return;}int par = partitionHoare(array, start, end);quick(array, start, par-1);quick(array, par+1, end);
}private static int partitionHoare(int[] array, int left, int right) {int tmp = array[left];int start = left;while(left < right) {while (left < right && array[right] >= tmp) {right--;}while (left < right && array[left] <= tmp) {left++;}swap(array, left, right);}swap(array, start, left);return left;}private static void swap(int[] array, int i, int j) {int tmp = array[i];array[i] = array[j];array[j] = tmp;}

  1. 挖坑法

在這里插入圖片描述

private static int partitionW(int[] array, int left, int right) {int i = left;int j = right;int pivot = array[left];while (i < j) {while (i < j && array[j] >= pivot) {j--;}array[i] = array[j];while (i < j && array[i] <= pivot) {i++;}array[j] = array[i];}array[i] = pivot;return i;}

  1. 前后指針

在這里插入圖片描述

private static int partition(int[] array, int left, int right) {int prev = left ;int cur = left+1;while (cur <= right) {if(array[cur] < array[left] && array[++prev] != array[cur]) {swap(array,cur,prev);}cur++;}swap(array,prev,left);return prev;
}

2.3.2 快速排序優化

  1. 三數取中法選key
  2. 遞歸到小的子區間時,可以考慮使用插入排序

2.3.3 快速排序非遞歸

void quickSortNonR(int[] a, int left, int right) {Stack<Integer> st = new Stack<>();st.push(left);st.push(right);while (!st.empty()) {right = st.pop();left = st.pop();if(right - left <= 1)continue;int div = PartSort1(a, left, right);// 以基準值為分割點,形成左右兩部分:[left, div) 和 [div+1, right)st.push(div+1);st.push(right);st.push(left);st.push(div);}
}

2.3.4 快速排序總結

  1. 快速排序整體的綜合性能和使用場景都是比較好的,所以才敢叫快速排序

  2. 時間復雜度:O(N*logN)

  3. 空間復雜度:O(logN)

  4. 穩定性:不穩定

2.4 歸并排序

2.4.1 基本思想

歸并排序(MERGE-SORT)是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法(Divide and Conquer)的一個非常典型的應用。將已有序的子序列合并,得到完全有序的序列;即先使每個子序列有序,再使子序列段間有序。若將兩個有序表合并成一個有序表,稱為二路歸并。 歸并排序核心步驟:

在這里插入圖片描述

public static void mergeSort(int[] array) {mergeSortFun(array, 0, array.length-1);}private static void mergeSortFun(int[] array, int left, int right) {if (left == right) {return;}int mid = (right + left) / 2;mergeSortFun(array, left, mid);mergeSortFun(array, mid+1, right);merge(array, left, mid, right);}private static void merge(int[] array, int left, int mid, int right) {int[] tmp = new int[right-left+1];int k = 0;int s1 = left;int e1 = mid;int s2 = mid+1;int e2 = right;while (s1<=e1 && s2<=e2) {if (array[s1] <= array[s2]) {tmp[k] = array[s1];k++;s1++;} else {tmp[k] = array[s2];k++;s2++;}}while (s1<=e1) {tmp[k++] = array[s1++];}while (s2<=e2) {tmp[k++] = array[s2++];}if (k >= 0) System.arraycopy(tmp, 0, array, left, k);}

2.4.2 歸并排序總結

  1. 歸并的缺點在于需要O(N)的空間復雜度,歸并排序的思考更多的是解決在磁盤中的外排序問題。
  2. 時間復雜度:O(N*logN)
  3. 空間復雜度:O(N)
  4. 穩定性:穩定

2.4.3 海量數據的排序問題

外部排序:排序過程需要在磁盤等外部存儲進行的排序
前提:內存只有 1G,需要排序的數據有 100G
因為內存中因為無法把所有數據全部放下,所以需要外部排序,而歸并排序是最常用的外部排序

  1. 先把文件切分成 200 份,每個 512 M
  2. 分別對 512 M 排序,因為內存已經可以放的下,所以任意排序方式都可以
  3. 進行 2路歸并,同時對 200 份有序文件做歸并過程,最終結果就有序了

3. 排序算法復雜度及穩定性分析

在這里插入圖片描述


排序方法最好時間復雜度平均時間復雜度最壞時間復雜度空間復雜度穩定性
冒泡排序O(n)O(n^2)O(n^2)O(1)穩定
插入排序O(n)O(n^2)O(n^2)O(1)穩定
選擇排序O(n^2)O(n^2)O(n^2)O(1)不穩定
希爾排序O(n)O(n^1.3)O(n^2)O(1)不穩定
堆排序O(n * log(n))O(n * log(n))O(n * log(n))O(1)不穩定
快速排序O(n * log(n))O(n * log(n))O(n^2)O(log(n)) ~ O(n)不穩定
歸并排序O(n * log(n))O(n * log(n))O(n * log(n))O(n)穩定

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

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

相關文章

【vuejs】vue-router多層級路由配置以及頁面嵌套的處理

1. 多層級頁面嵌套概念 1.1 什么是多層級頁面嵌套 多層級頁面嵌套指的是在單頁面應用&#xff08;SPA&#xff09;中&#xff0c;頁面結構由多個嵌套的組件組成&#xff0c;每個組件可能代表不同的頁面或頁面區域。這種結構允許開發者將應用組織成多個模塊&#xff0c;每個模…

認證資訊|Bluetooth SIG認證

在當今高度互聯的世界中&#xff0c;無線技術的普及已經成為我們生活和工作中不可或缺的一部分。作為領先的無線通信技術之一&#xff0c;Bluetooth技術以其穩定性、便捷性和廣泛的應用場景而備受青睞。然而&#xff0c;要想在激烈的市場競爭中脫穎而出&#xff0c;獲得Bluetoo…

6、Redis系統-數據結構-04-Hash

四、哈希表&#xff08;Hashtable&#xff09; 哈希表是一種高效的鍵值對數據結構&#xff0c;通過散列函數將鍵映射到表中的位置&#xff0c;實現快速的插入、刪除和查找操作。Redis 廣泛使用哈希表來實現 Hash 對象和數據庫的鍵值存儲。以下將從結構設計、哈希沖突與鏈式哈希…

深入源碼,探究#、$號替換符的區別

在Mybatis的日常使用過程中以及在一些技術論壇上我們都能常常聽到&#xff0c;不要使用$符號來進行SQL的編寫&#xff0c;要使用#符號&#xff0c;否則會有SQL注入的風險。那么&#xff0c;為什么在使用$符號時會有注入的風險呢&#xff0c;以及#號為什么不會有風險呢&#xff…

C/C+++服務器之libuv的使用實戰

libuv libuv簡介 1: 開源跨平臺的異步IO庫, 主要功能有網絡異步&#xff0c;文件異步等。 2: libuv主頁: http://libuv.org/ 3: libuv是node.js的底層庫; 4: libuv的事件循環模型: epoll, kqueue, IOCP, event ports; 異步 TCP 與 UDP sockets; DNS 解析 異步文件讀寫; 信號處…

Python結合MobileNetV2:圖像識別分類系統實戰

一、目錄 算法模型介紹模型使用訓練模型評估項目擴展 二、算法模型介紹 圖像識別是計算機視覺領域的重要研究方向&#xff0c;它在人臉識別、物體檢測、圖像分類等領域有著廣泛的應用。隨著移動設備的普及和計算資源的限制&#xff0c;設計高效的圖像識別算法變得尤為重要。…

設計模式-結構型-08-組合模式

文章目錄 1、學校院系展示需求2、組合模式基本介紹3、組合模式示例3.1、 解決學校院系展示&#xff08;透明模式1&#xff09;3.2、高考的科目&#xff08;透明模式2&#xff09;3.3、高考的科目&#xff08;安全組合模式&#xff09; 4、JDK 源碼分析5、注意事項和細節 1、學校…

存儲過程編程-創建(CREATE PROCEDURE)、執行(EXEC)、刪除(DROP PROCEDURE)

一、定義 1、存儲過程是在SQL服務器上存儲的已經編譯過的SQL語句組。 2、存儲過程分為三類&#xff1a;系統提供的存儲過程、用戶定義的存儲過程和擴展存儲過程 &#xff08;1&#xff09;系統提供的存儲過程&#xff1a;在安裝SQL Server時&#xff0c;系統創建了很多系統存…

AI機器人在企業拓客上常見的功能有哪些

AI機器人具備多種功能&#xff0c;這些功能主要基于其被設計和訓練的目的。整理了一些常見的AI機器人功能&#xff1a; 1. 語音識別與自然語言處理&#xff1a; - 語音識別&#xff1a;將用戶的語音輸入轉換為文本&#xff0c;以便機器人可以理解和處理。 - 自然語言處理…

QCC5181 歌詞歌曲名多國語言顯示替代QCC5125 CSR8675

QCC518X作為Qualcomm新一代藍牙技術芯片&#xff0c;支持最新藍牙協議V5.4&#xff0c;較QCC512X系列&#xff0c;它有更強大的DSP、CPU。除支持USB、I2S、SPDIF等接口外&#xff0c;還擴展了LE Audio功能&#xff0c;擴展支持AptX Lossless。以5181為例&#xff0c;我們還擴展…

vscode語言模式

1.背景 寫vue3ts項目的時候&#xff0c;用到了volar插件&#xff0c;在單文件使用的時候&#xff0c;鼠標懸浮在代碼上面會有智能提示&#xff1b; 但是最近volar插件提示被棄用了&#xff0c;然后我按照它的官方提示&#xff0c;安裝了Vue-official擴展插件&#xff0c;但是…

Banana Pi BPI-M5 Pro 低調 SBC 采用 Rockchip RK3576 八核 Cortex-A72/A53 AIoT SoC

Banana Pi BPI-M5 Pro&#xff0c;也稱為 Armsom Sige5&#xff0c;是一款面向 AIoT 市場的低調單板計算機 (SBC)&#xff0c;由 Rockchip RK3576 八核 Cortex-A72/A53 SoC 驅動&#xff0c;提供Rockchip RK3588和RK3399 SoC 之間的中檔產品。 該主板默認配備 16GB LPDDR4X 和…

如何大幅減少 Vue.js 中的包大小和加載時間,提升用戶體驗!

大家好,我是CodeQi! 一位熱衷于技術分享的碼仔。 你知道嗎,根據Google 的一項研究,如果網站加載時間超過 3 秒,53% 的移動用戶會離開該網站? 性能優化是一個經常討論的話題,但很多開發人員并不關心提高應用的速度。 在前端開發中,優化包大小和加載時間對于提升用戶體…

下一代 CLI 工具,使用Go語言用于構建令人驚嘆的網絡應用程序

大家好&#xff0c;今天給大家分享一個創新的命令行工具Gowebly CLI&#xff0c;它專注于使用Go語言來快速構建現代Web應用程序。 Gowebly CLI 是一款免費開源軟件&#xff0c;有助于在后端使用 Go、在前端使用 htmx 和 hyperscript 以及最流行的 CSS 框架輕松構建令人驚嘆的 W…

入門PHP就來我這(高級)15 ~ 圖書刪除功能

有膽量你就來跟著路老師卷起來&#xff01; -- 純干貨&#xff0c;技術知識分享 路老師給大家分享PHP語言的知識了&#xff0c;旨在想讓大家入門PHP&#xff0c;并深入了解PHP語言。 今天給大家接著上篇文章實現圖書刪除功能&#xff0c;來實現刪除圖書信息記錄行的功能。 1 刪…

高顏值官網(3):家居用品網站12個,好的創意都在這里。

hello&#xff0c;大家好&#xff0c;我是大千UI工場&#xff0c;本文為大家帶來家居用品網站UI&#xff0c;供大家欣賞。

項目代碼優化(1)——下單邏輯

給一個電商開發的系統排查&#xff0c;發現漏洞很多。很多經驗不夠的開發者很容易忽視的邏輯錯誤陷阱。在給一個項目做二次開發時候&#xff0c;檢測到的相關經典案例。這里整理支付和產品相關的邏輯&#xff0c;方便后續查看。&#xff0c;這里進行一些簡單的邏輯漏洞梳理與修…

Ubuntu 22.04 LTS 上安裝 MySQL8.0.23(在線安裝)

目錄 在線安裝MySQL 步驟1&#xff1a;更新軟件包列表 步驟2&#xff1a;安裝MySQL服務器 步驟3&#xff1a;啟動MySQL服務 步驟4&#xff1a;檢查MySQL狀態 步驟5&#xff1a;修改密碼、權限 在線安裝MySQL 步驟1&#xff1a;更新軟件包列表 在進行任何軟件安裝之前&a…

p9函數(1)

int Add(int x,int y) { int z0; zxy; return z; } int main() { int a10; int b20; int sumAdd(a,b); printf("%d\n",sum); return 0; } 字符串求長度 int main() { char arr1[]"bit"; char arr2[20]"###…

移動UI: 什么特征會被認為是簡潔風格,用案例告訴你

什么是簡潔風格&#xff0c;恐怕一百個人有一百個是理解&#xff0c;本文通過理論分析案例的方式進行探討。 移動 UI 中的簡潔風格通常具有以下幾個特征&#xff1a; 1. 平面化設計&#xff1a; 簡潔風格的移動 UI 善于運用平面化設計&#xff0c;即去除過多的陰影、漸變和立…