常見排序演算法

来源:https://www.cnblogs.com/sun2019/archive/2019/09/17/11536971.html
-Advertisement-
Play Games

簡單整理常用演算法，記錄在此。 package com.demo.sort; import java.util.Arrays; public class Sort { public static void main(String[] args) { int size = 10; int[] arr = ...


簡單整理常用演算法，記錄在此。

 

package com.demo.sort;

import java.util.Arrays;

public class Sort {
public static void main(String[] args) {

int size = 10;
int[] arr = new int[size];
for (int j = 0; j < size; j++) {
for (int i = 0; i < size; i++) {
arr[i] = (int) (100*size*Math.random() +1);
}
//測試冒泡
// System.out.println(Arrays.toString(bubble(arr)));
//測試選擇
// System.out.println(Arrays.toString(select(arr)));
//測試快速
// System.out.println(Arrays.toString(fast(arr,0,5)));
//測試插入排序
// System.out.println(Arrays.toString(insert(arr)));
//測試希爾排序
// System.out.println(Arrays.toString(shell(arr)));
//測試桶排序
// System.out.println(Arrays.toString(bucket(arr)));
//測試基數排序
// System.out.println(Arrays.toString(radix(arr)));
//測試歸併排序
// mergeSort(arr);
// System.out.println(Arrays.toString(arr));
//測試堆排序
// System.out.println(Arrays.toString(heap(arr)));
}

}

/**
* heap sort 堆排序原理（升序）：
* 將序列抽象為二叉樹，構建最大堆；
* 依次將最大元素與待排序列的最後位置交換；
* 遍歷刷新直至最後一個元素；
* 演算法思想：完全二叉樹
* 時間複雜度：O[NlogN]
* 空間複雜度：O[1]
* 穩定性：不穩定
*/
private static int[] heap(int[] arr) {

for (int i = 0; i < arr.length; i++) {
maxHeap(arr, arr.length - i);
// 交換
int temp = arr[0];
arr[0] = arr[(arr.length - 1) - i];
arr[(arr.length - 1) - i] = temp;
}
return arr;
}

private static void maxHeap(int[] arr, int size) {
for (int i = size - 1; i >= 0; i--) {
buildheap(arr, i, size);
}
}

private static void buildheap(int[] arr, int rootNode, int size) {
if (rootNode < size) {

int leftNode = 2 * rootNode + 1;
int rightNode = 2 * rootNode + 2;
int max = rootNode;

if (leftNode < size) {
if (arr[leftNode] > arr[max]) {
max = leftNode;
}
}

if (rightNode < size) {
if (arr[rightNode] > arr[max]) {
max = rightNode;
}
}

if (max != rootNode) {
int tmp = arr[max];
arr[max] = arr[rootNode];
arr[rootNode] = tmp;

buildheap(arr, max, size);
}

}
}

/**merge sort 歸併排序原理（升序）：
* 把序列看做對兩個有序隊列的排序，遞歸對兩個序列排序直至隊列只包含兩個元素，然後將兩個有序隊列合併；
* 演算法思想：遞歸加分治
* 時間複雜度：O[NlogN]
* 空間複雜度：O[N]
* 穩定性：穩定
*/
public static void mergeSort(int[] array) {

int length = array.length;
int middle = length / 2;

if (length > 1) {
int[] left = Arrays.copyOfRange(array, 0, middle);// 拷貝數組array的左半部分
int[] right = Arrays.copyOfRange(array, middle, length);// 拷貝數組array的右半部分
mergeSort(left);// 遞歸array的左半部分
mergeSort(right);// 遞歸array的右半部分
merge(array, left, right);// 數組左半部分、右半部分合併到Array
}
}

// 合併數
private static void merge(int[] result, int[] left, int[] right) {

int i = 0, l = 0, r = 0;

while (l < left.length && r < right.length) {
if (left[l] < right[r]) {
result[i] = left[l];
i++;
l++;
} else {
result[i] = right[r];
i++;
r++;
}
}

while (r < right.length) {// 如果右邊剩下合併右邊的
result[i] = right[r];
r++;
i++;
}

while (l < left.length) {
result[i] = left[l];
l++;
i++;
}
}

/**
* radix sort 基數排序原理（升序）：
* 桶排序的改進版窗，桶的大小固定為10；
* 首先對數組元素的個位數值大小按桶排序進行排序；接著按元素的十位數值大小按桶排序進行排序；依次按桶排序將最高位排序完成；
* 時間複雜度：O[d(r+N)]
* 空間複雜度：O[rd+N]
* 穩定性：穩定
*/
private static int[] radix(int[] arr) {
if (null == arr || arr.length == 0) {
return null;
}
int[] tmp1 = new int[10];
int[][] tmp2 = new int[10][arr.length];
int max = arr[0];
for (int i = 1; i < arr.length; i++) {
if (max < arr[i]) {
max = arr[i];
}
}
int num = 1;
while ((max /= 10) > 0) {
num += 1;
}
for (int i = 0; i < num; i++) {
for (int j = 0; j < arr.length; j++) {
int index = arr[j] / ((int) Math.pow(10, i)) % 10;
tmp2[index][tmp1[index]] = arr[j];
tmp1[index] += 1;
}
int k = 0;
for (int j = 0; j < tmp1.length; j++) {
// while(tmp1[j] != 0){
for (int h = 0; h < tmp1[j]; h++) {
arr[k] = tmp2[j][h];
// tmp2[j][h] = 0;
// tmp1[j]--;
k++;
}
tmp1[j] = 0;
// }
}
}

return arr;
}

/**
* bucket sort 桶排序原理（升序）：
* 找出序列最大值，創建最大值加一的新數組；
* 遍曆數組，元素值對應新數組下標的位置加一；
* 遍歷新數組，將元素值非0的下標值載入原數組；
* 時間複雜度：O[N]
* 空間複雜度：O[N]
* 穩定性：不穩定
*/
private static int[] bucket(int[] arr) {
int max = arr[0];
for (int i = 1; i < arr.length; i++) {
if (max < arr[i]) {
max = arr[i];
}
}
int[] tmp = new int[max + 1];
for (int j = 0; j < arr.length; j++) {
tmp[arr[j]] += 1;
}

int k = 0;
for (int i = 0; i < tmp.length; i++) {
while (tmp[i] != 0) {
arr[k] = i;
k++;
tmp[i]--;
}
}
return arr;
}

/**
* shell sort 希爾排序原理（升序）：
* 插入排序改進版；
* 把元素分組，每組插入排序 ；
* 改變分組增量，直至增量為1；
* 時間複雜度：O[N^2]
* 空間複雜度：O[1]
* 穩定性：不穩定
*/
private static int[] shell(int[] arr) {
int len = arr.length;
for (int i = len / 2; i > 0; i = i / 2) {// 增量
for (int j = 0; j < i; j++) {// 分組數
for (int k = 1; k < len / i; k++) {// 每組的元素數
int m = k - 1;
for (; m >= 0; m--)
// 逆序，前面部分為有序
if (arr[j + i * k] >= arr[j + i * m])
break;

if (m != k - 1) {
int n = k;
int tmp = arr[j + i * n];
for (; n > m + 1; n--) {
arr[j + i * n] = arr[j + i * (n - 1)];
}

arr[j + i * n] = tmp;
}
}
}
}
return arr;
}

/*
* insert sort 插入排序原理（升序）：
* 改原理是將待排序元素插入一個有序隊列，將左邊部分當做一個有序隊列；
* 時間複雜度：O[N^2]
* 空間複雜度：O[1]
* 穩定性：穩定
*/
private static int[] insert(int[] arr) {

for (int i = 1; i < arr.length; ++i) {
/*
* 分為1,2兩部分處理，可以囊括j = beg - 1時的情況 即需要將arr[i]插入到首元素前的位置，若使用一個for
* 包括這兩部分，則會在發生這種情況時退出
*/
/* 1 */
int j = i - 1;
for (; j >= 0; --j)
if (arr[j] <= arr[i])
break;
/* 2 */
if (j != i - 1) {
int temp = arr[i];
for (int k = i; k > j + 1; --k) {
arr[k] = arr[k - 1];
}
arr[j + 1] = temp;
}
}
return arr;
}

/*
* fast sort 快速排序原理（升序）：
* 選一基準元素，小於其大小的元素放在左邊，大於它的元素放在右邊；
* 取基準元素的前後兩部分做同樣處理，直至基準元素的兩邊各有一個元素為止；
* 時間複雜度：O[NlogN]
* 空間複雜度：O[NlogN]
* 穩定性：不穩定
*/
private static int[] fast(int[] arr, int begin, int end) {
if (begin >= end) {
return arr;
}
int lindex = begin;
int rindex = end;
int mid = arr[lindex];
while (lindex < rindex) {
while (lindex < rindex) {
if (arr[rindex] < mid) {
arr[lindex++] = arr[rindex];
break;
}
--rindex;
}

while (lindex < rindex) {
if (arr[lindex] >= mid) {
arr[rindex--] = arr[lindex];
break;
}
++lindex;
}
}
arr[lindex] = mid;
fast(arr, begin, lindex);
fast(arr, rindex + 1, end);
return arr;
}

/*
* select sort 選擇排序原理（升序）：
* 找出元素最小值放在第一位，接著次小值放在第二位，依次將數組升序排列
* 時間複雜度：O[N^2]
* 空間複雜度：O[1]
* 穩定性：不穩定
*/
private static int[] select(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[i]) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}
}
return arr;
}

/*
* bubble sort 冒泡排序原理（升序）：
* 依次比較相鄰兩個元素，若後位元素較大則交換至，直至最後一位元素為最大值；
* 接著進行下一輪比較，直至倒數第二位元素為次大值；
* 進行比較至所有元素為升序排列
* 時間複雜度：O[N^2]
* 空間複雜度：O[1]
* 穩定性：不穩定
*/
private static int[] bubble(int[] arr) {
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr.length - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
int tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
}
}
}
return arr;
}
}


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • 編程必備基礎知識|電腦組成原理篇(07)：電腦的匯流排
    電腦基礎方面的知識，對於一些非科班出身的同學來講，一直是他們心中的痛，而對於科班出身的同學，很多同學在工作之後，也意識到自身所學知識的不足與欠缺，想回頭補補基礎知識。關於電腦基礎的課程很多，內容繁雜，但無論是相關書籍還是大學課程，都有點脫離工作。特別地，電腦基礎知識體系龐雜，想要從零學習或者復 ...
  • Java連載31-遞歸方法練習、面向對象
    一、實現階乘（一種用遞歸，一種普通方法） 二、面向對象（Java語言核心內容） 1.面向過程和麵向對象的區別 （1）面向過程：主要關註點是：實現的具體過程，因果關係 優點：對於業務邏輯比較簡單的程式，可以達到快速開發，前期投入成本低 缺點：採用面向對象的方式開發很難解決非常複雜的業務邏輯，另外面向過 ...
  • Centos7上安裝jdk8
    CentOS7 下安裝jdk8環境 1 檢查伺服器環境 首先，我們需要檢查一下伺服器是否安裝過java環境，可以使用如下命令： 如果已經安裝有java環境，會出現類似於以下的信息： 如果未安裝java環境，則會出現類似以下信息： 2 傳輸、解壓jdk 這裡，我們預設系統未安裝過java環境，且伺服器 ...
  • JVM學習分享-思考題
    package zero.desk.stringconstantpool;import org.junit.Test;/** * @author Zero * @since 2019-09-17. * Description: * 當調用intern方法時， * 如果池已經包含此字元串（equals ...
  • 每天兩題02
    題目一： 思路：當n=1的時候很明顯只有一種跳法； 當n>1的時候，那麼總共的跳法應該就是第一次跳一級臺階還剩下n-1個臺階、第一次跳兩級臺階還剩下n-2個臺階，這兩種情況的總和，而至於這裡的n-1和n-2個臺階，同理可以繼續拆分，是不是覺得很熟悉，還是斐波那契數列，這裡用的還是分治的思想，代碼跟上 ...
  • 關於鎖的個人學習筆記
    個人學習筆記！ 1）分散式鎖的實現？①資料庫實現單點、非重入、非阻塞、無失效時間、依賴資料庫（要自己設置，可結合排它鎖、樂觀鎖、悲觀鎖等混合使用）②緩存（Redis等）集群部署解決單點問題、分散式鎖方法直接調用即可（redis的setnx方法）、設置超時時間控制鎖的釋放③zka.集群部署（解決單點問 ...
  • python學習之路-day1
    1 變數 賦值：變數可以是字元串、序列、元組、 輸出效果： 2019 9 17-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*name subjet soce year moth dayali english 65 2019 9 17-*-*-*-*-*-*-*-*- ...
  • Python Flask高級編程之從0到1開發《魚書》精品項目
    Python Flask高級編程之從0到1開發《魚書》精品項目 部分課程截圖： 點擊鏈接或搜索QQ號直接加群獲取其它資料： 鏈接：https://pan.baidu.com/s/1uwU9rUdXw7THg5yEozYeoA 提取碼：l4gz 免費分享，如若鏈接失效請加群 其它資源在群里，私聊管理員 ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發（一）：使用.NET MAUI開發第一個安卓APP
    移動開發（一）：使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說，近來想嘗試開發一款安卓APP，考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP，畢竟是使用Visual Studio開發工具，使用起來也比較的順手，結合微軟官方的教程進行了安卓 ...
  • wpf ToggleButton選中效果和一個登錄界面
    前言 QuestPDF 是一個開源 .NET 庫，用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫，它徹底改變了我們生成 PDF 文檔的方 ...
  • 彈幕樹洞項目功能新增篇
    項目地址 項目後端地址： https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址： ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址： http://tree ...
  • 第27篇 sqlserver2022詳細安裝步驟
    話不多說，直接開乾 一.下載 1.官方鏈接下載： https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe，運行開始下載SQL server； 二. ...
  • .NET 開源高性能 MQTT 類庫
    前言 隨著物聯網（IoT）技術的迅猛發展，MQTT（消息隊列遙測傳輸）協議憑藉其輕量級和高效性，已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫，為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog文檔翻譯系列（六） - 可用的接收器、增強器、格式化輸出
    Serilog支持多種接收器用於日誌存儲，增強器用於添加屬性，LogContext管理動態屬性，支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項，適用於不同需求。 ...
  • 警惕 Visual Studio 屬性求值副作用導致邏輯不符合預期
    目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據，爬取信息時需要模擬瀏覽器行為，否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下： 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • [使用目前最新版]HybridCLR6.9.0+YooAsset2.2.4實現純C# Unity熱更新方案 (一)
    1.前言 什麼是熱更新 游戲或者軟體更新時，無需重新下載客戶端進行安裝，而是在應用程式啟動的情況下，在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR，Xlua，ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles，Addressable， ...
  • 在 ASP.NET Core Web API 中使用操作篩選器統一處理通用操作
    本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺，其實像阿裡雲，騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後，它會送 ...
  • 第28篇 如何.net中實現高效可靠數據同步api
    通過以下方式可以高效，並保證數據同步的可靠性 1.API設計 使用RESTful設計，確保API端點明確，並使用適當的HTTP方法（如POST用於創建，PUT用於更新）。 設計清晰的請求和響應模型，以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證，確保接收到的數據符合預期格 ...
所有分類