java arrays.sort排序原理，java快排原理_快速排序 java實現 (原理-優化) 三路快排-基礎知識庫-匯編語言學習筆記

java arrays.sort排序原理，java快排原理_快速排序 java實現 (原理-優化) 三路快排

2023-12-25 阅读 28 评论 0

摘要：一、基本的快速排序在數組中選取一個元素為基點，然后想辦法把這個基點元素移動到它在排好序后的最終位置，使得新數組中在這個基點之前的元素都小于這個基點，而之后的元素都大于這個基點，然后再對前后兩部分數組快速排序，直到數組排序完成。

一、基本的快速排序

在數組中選取一個元素為基點，然后想辦法把這個基點元素移動到它在排好序后的最終位置，使得新數組中在這個基點之前的元素都小于這個基點，而之后的元素都大于這個基點，然后再對前后兩部分數組快速排序，直到數組排序完成。

代碼實現：

public void quickSorted ( int arr[] ) {

int n = arr.length - 1; // 閉區間 [0...n]

java arrays.sort排序原理、__quickSorted (arr, 0, n);

}

private __quickSorted( int arr[], int L, int R) {

if ( (L >= R) {

return;

}

java快速排序簡單代碼、// 將基點移動到最終位置的方法

int p = __partioner(arr, L, R);

// 遞歸拆分數組

__quickSorted(arr, L, p - 1);

__quickSorted(arr, p + 1, R);

}

快速排序算法的原理圖解，那么最大的問題就是怎么把這個基點移動到它最終應該所在的位置。

代碼實現：

private int __partioner ( int arr[], int L, int R ) {

int v = arr[L];

// [L + 1, j] < v ; [j + 1, i) > v;

int j = L;

java實現快速排序算法、for ( int i = L + 1; i <= R; i++ ) {

if ( arr[i] < v) {

// 交換 arr[i] 和 arr [j + 1]

int tmp = arr[j + 1];

arr[j + 1] = arr[i];

arr[i] = tmp;

快速排序思路？j++;

}

// 交換 arr[j] 和arr[L]

int tmp = arr[j];

arr[j] = arr[L];

數據結構快速排序過程，arr[L] = tmp;

return j;

}

最終實現：

public void quickSorted ( int arr[] ) {

int n = arr.length - 1; // 閉區間 [0...n]

java歸并排序？__quickSorted (arr, 0, n);

}

private __quickSorted( int arr[], int L, int R) {

if ( (L >= R) {

return;

}

歸并排序原理，// 將基點移動到最終位置的方法

int p = __partioner(arr, L, R);

// 遞歸拆分數組

__quickSorted(arr, L, p - 1);

__quickSorted(arr, p + 1, R);

}

希爾排序原理，private int __partioner ( int arr[], int L, int R ) {

int v = arr[L];

// [L + 1, j] < v ; [j + 1, i) > v;

int j = L;

for ( int i = L + 1; i <= R; i++ ) {

if ( arr[i] < v) {

java數組快速排序，// 交換 arr[i] 和 arr [j + 1]

int tmp = arr[j + 1];

arr[j + 1] = arr[i];

arr[i] = tmp;

j++;

}

// 交換 arr[j] 和arr[L]

int tmp = arr[j];

arr[j] = arr[L];

arr[L] = tmp;

return j;

}

快速排序完整代碼

二、快速排序的優化

1.??快速排序的第一次優化，減小遞歸的深度，轉而使用選擇排序

private __quickSorted( int arr[], int L, int R) {

// if ( (L >= R) {

// return;

// }

// 快速排序的第一次優化，減小遞歸的深度，轉而使用選擇排序

if ( R - L <= 15) {

insertSorted(arr, L, R);

return;

}

// 將基點移動到最終位置的方法

int p = __partioner(arr, L, R);

// 遞歸拆分數組

__quickSorted(arr, L, p - 1);

__quickSorted(arr, p + 1, R);

}

// 減小遞歸的深度轉而使用選擇排序

private void insertSorted(int arr[], int L, int R) {

for (int i = L + 1; i <= R; i++) {

int i = arr[i];

int j;

for (j = i; j > L && arr[j - 1] > e; j--) {

arr[j] = arr[j - 1];

}

return;

}

2. 優化二，基點的選擇隨機化

private int __partioner ( int arr[], int L, int R ) {

// 第二次優化，將基點的選擇隨機化

int rand = (new Random().nextInt(R + 1)) + L;

// 交換最左側和隨機點的元素

int tmp = arr[rand];

arr[rand] = arr[L];

arr[L] = tmp;

int v = arr[L];

// [L + 1, j] < v ; [j + 1, i) > v;

int j = L;

for ( int i = L + 1; i <= R; i++ ) {

if ( arr[i] < v) {

// 交換 arr[i] 和 arr [j + 1]

int tmp = arr[j + 1];

arr[j + 1] = arr[i];

arr[i] = tmp;

j++;

}

// 交換 arr[j] 和arr[L]

int tmp = arr[j];

arr[j] = arr[L];

arr[L] = tmp;

return j;

}

三、兩路快排

解決排序的數組中存在多數重復元素的情況

代碼實現

public void quickSorted ( int arr[] ) {

int n = arr.length - 1; // 閉區間 [0...n]

__quickSorted (arr, 0, n);

}

private __quickSorted( int arr[], int L, int R) {

// if ( (L >= R) {

// return;

// }

// 快速排序的第一次優化，減小遞歸的深度，轉而使用選擇排序

if ( R - L <= 15) {

insertSorted(arr, L, R);

return;

}

// 將基點移動到最終位置的方法

int p = __partioner(arr, L, R);

// 遞歸拆分數組

__quickSorted(arr, L, p - 1);

__quickSorted(arr, p + 1, R);

}

private int __partioner ( int arr[], int L, int R ) {

// 第二次優化，將基點的選擇隨機化

int rand = (new Random().nextInt(R + 1)) + L;

// 交換最左側和隨機點的元素

int tmp = arr[rand];

arr[rand] = arr[L];

arr[L] = tmp;

int v = arr[L];

// 兩路快排的實現過程

int i = L + 1;

int j = R ;

while (true) {

while (i <= R && arr[i] < v ){

i++;

}

while (j >= L + 1 && arr[j] > v) {

j--;

}

if (i > j) {

break;

}

// 交換 i 和 j 的位置

int tmp arr[i];

arr[i] = arr[j];

arr[j] = tmp;

}

int tmp arr[L];

arr[L] = arr[j];

arr[j] = tmp;

return j;

}

// 減小遞歸的深度轉而使用選擇排序

private void insertSorted(int arr[], int L, int R) {

for (int i = L + 1; i <= R; i++) {

int i = arr[i];

int j;

for (j = i; j > L && arr[j - 1] > e; j--) {

arr[j] = arr[j - 1];

}

return;

}

兩路快排代碼實現

四、三路快排

代碼實現：

public static void quickSorted3Ways(int arr[]) {

int n = arr.length -1;

// arr[0, n] 閉區間

__quickSorted3Ways(arr, 0, n);

}

private static void __quickSorted3Ways(int[] arr, int L, int R) {

// if (L >= R) {

// return;

// }

// 快速排序的第一次優化，減小遞歸的深度，轉而使用選擇排序

if ( R - L <= 15) {

insertSorted(arr, L, R);

return;

}

// 第二次優化，將基點的選擇隨機化

int rand = (new Random().nextInt(R + 1)) + L;

// 交換最左側和隨機點的元素

int tmp = arr[rand];

arr[rand] = arr[L];

arr[L] = tmp;

int v = arr[L];

// partioner

// 這三個變量的初始值，相當重要

int lt = L; // arr[L + 1, lt] < v

int gt = R + 1; // arr[gt, R] > v

int i =L + 1; // arr[lt + 1, i ) ==v // 此處的 i 的比較對象

while (i < gt ) {

if (arr[i] < v) {

SortedHandler.swap(arr, i, lt + 1);

lt++;

i++;

} else if (arr[i] > v) {

SortedHandler.swap(arr, i, gt - 1);

gt--;

} else {

i++;

}

SortedHandler.swap(arr, lt, L);

__quickSorted3Ways(arr, L, lt -1);

__quickSorted3Ways(arr, gt, R);

}

三路快排

最后附上整篇關于快速排序從實現到逐步優化的思路圖 (畫到我懷疑人生了....)

快速排序—三路快排 vs 雙基準

快速排序被公認為是本世紀最重要的算法之一,這已經不是什么新聞了.對很多語言來說是實際系統排序,包括在Java中的Arrays.sort. 那么快速排序有什么新進展呢? 好吧,就像我剛才提到的那樣(Ja ...

LeetCode 75&period; Sort Colors (顏色分類)：三路快排

Given an array with?n?objects colored red, white or blue, sort them?in-place?so that objects of the ...

普林斯頓大學算法課 Algorithm Part I Week 3 重復元素排序 - 三路快排 Duplicate Keys

很多時候排序是為了對數據進行歸類,這種排序重復值特別多通過年齡統計人口刪除郵件列表里的重復郵件通過大學對求職者進行排序若使用普通的快排對重復數據進行排序,會造成N^2復雜度,但是歸并排序和三路 ...

leetcode 75 Sort Colors 計數排序，三路快排

解法一:計數排序:統計0,1,2 的個數時間復雜度:O(n) 空間復雜度:O(k) ?? k為元素的取值范圍, 此題為O(1) class Solution { public: void sortC ...

LeetCode 75&period; Sort Colors (python一次遍歷，模擬三路快排)

LeetCode 75. Sort Colors (python一次遍歷,模擬三路快排) 題目分析: 本題需要實現數字只包含0,1,2的排序,并且要求一次遍歷. 由于只用把數字隔離開,很容易想到快排的 ...

【C語言編程入門筆記】排序算法之快速排序，一文輕松掌握快排！

排序算法一直是c語言重點,各個算法適應不用的環境,同時,在面試時,排序算法也是經常被問到的.今天我們介紹下快速排序,簡稱就是快排. 1.快速排序思想: 快排使用?分治法?(Divide and con ...

Java寫插入選擇冒泡快排

/** * Created by wushuang on 2014/11/19. */ public class SortTest { @Test public void mainTest() { i ...

&lt&semi;泛&gt&semi; 多路快排

今天寫一個多路快排函數模板,與STL容器兼容的. 我們默認為升序排序因為,STL容器均為逾尾容器,所以我們這里采用的參數也是逾尾的參數一.二路快排基本思路給你一個序列,先選擇一個數作為基數,我 ...

LeetCode75----分類顏色(變相快排)

給定一個包含紅色.白色和藍色,一共?n?個元素的數組,原地對它們進行排序,使得相同顏色的元素相鄰,并按照紅色.白色.藍色順序排列. 此題中,我們使用整數 0.?1 和 2 分別表示紅色.白色和藍色. ...

隨機推薦

跟我一起云計算(5)——Shards

什么是sharding Sharding的基本思想就要把一個數據庫切分成多個部分放到不同的數據庫 (server)上,從而緩解單一數據庫的性能問題.不太嚴格的講,對于海量數據的數據庫,如果是因為表多而 ...

自定義ConfigSection

CCustom configuration section with intelisense

Hibernate注解----關聯映射注解以及課程總結詳解----圖片版本

上一篇,記錄了Hibernate注解----類級別注解以及屬性注解詳解?,我們這一節主要講解的是Hibernate注解----關聯映射注解以及課程總結詳解. 本節的主要內容: 第3章關聯映射注解 3 ...

基于FPGA的音頻信號的FIR濾波(Matlab+Modelsim驗證)

1 設計內容本設計是基于FPGA的音頻信號FIR低通濾波,根據要求,采用Matlab對WAV音頻文件進行讀取和添加噪聲信號.FFT分析.FIR濾波處理,并分析濾波的效果.通過Matlab的分析驗證濾 ...

如何讓LinearLayout也有類似Button的點擊效果？

有的時候,我們希望LinearLayout布局也有點擊的效果,這時候我們不僅需要一個作為背景的selector,還要設置一些其它屬性才行: android:clickable="true&q ...

XSLT2&period;0實用的新功能 &period;(轉)

轉自:http://blog.csdn.net/crystalbruce/article/details/7407631 2007年1月,W3C發布了XSLT2.0規范,2009年發布了XSLT2.1 ...

Cisco(思科)路由器靜態路由的配置

實驗拓撲實驗步驟我們要使得 1.1.1.0/24.2.2.2.0/24.3.3.3.0/24 網絡之間能夠互相通信. (1)? 步驟 1:在各路由器上配置 IP 地址.保證直連鏈路的連通性 R1( ...

curd——5

curd——5 SELECT area_id? FROM 16tree.ts_area? where pid=0; <?php //1可以防止注入$db = Yii::app()->db; ...

JAVA I/O(四)網絡Socket和ServerSocket

中第一章描述了用Socket和Channel的網絡編程,核心即為Socket和Channel,本文簡單講述Socket的應用. S ...

原文链接：https://hbdhgg.com/5/194699.html

发表评论: