Java實(shí)現(xiàn)快速排序和堆排序的示例代碼
快速排序
快速排序是由東尼·霍爾所發(fā)展的一種排序算法。在平均狀況下,排序 n 個(gè)項(xiàng)目要 Ο(nlogn) 次比較。在最壞狀況下則需要 Ο(n2) 次比較,但這種狀況并不常見。事實(shí)上,快速排序通常明顯比其他 Ο(nlogn) 算法更快,因?yàn)樗膬?nèi)部循環(huán)(inner loop)可以在大部分的架構(gòu)上很有效率地被實(shí)現(xiàn)出來。
快速排序使用分治法(Divide and conquer)策略來把一個(gè)串行(list)分為兩個(gè)子串行(sub-lists)。
快速排序又是一種分而治之思想在排序算法上的典型應(yīng)用。本質(zhì)上來看,快速排序應(yīng)該算是在冒泡排序基礎(chǔ)上的遞歸分治法。
快速排序的名字起的是簡單粗暴,因?yàn)橐宦牭竭@個(gè)名字你就知道它存在的意義,就是快,而且效率高!它是處理大數(shù)據(jù)最快的排序算法之一了。雖然 Worst Case 的時(shí)間復(fù)雜度達(dá)到了 O(n²),但是人家就是優(yōu)秀,在大多數(shù)情況下都比平均時(shí)間復(fù)雜度為 O(n logn) 的排序算法表現(xiàn)要更好,可是這是為什么呢,我也不知道。好在我的強(qiáng)迫癥又犯了,查了 N 多資料終于在《算法藝術(shù)與信息學(xué)競賽》上找到了滿意的答案:
快速排序的最壞運(yùn)行情況是 O(n²),比如說順序數(shù)列的快排。但它的平攤期望時(shí)間是 O(nlogn),且 O(nlogn) 記號(hào)中隱含的常數(shù)因子很小,比復(fù)雜度穩(wěn)定等于 O(nlogn) 的歸并排序要小很多。所以,對絕大多數(shù)順序性較弱的隨機(jī)數(shù)列而言,快速排序總是優(yōu)于歸并排序。
算法步驟
- 從數(shù)列中挑出一個(gè)元素,稱為 “基準(zhǔn)”(pivot);
- 重新排序數(shù)列,所有元素比基準(zhǔn)值小的擺放在基準(zhǔn)前面,所有元素比基準(zhǔn)值大的擺在基準(zhǔn)的后面(相同的數(shù)可以到任一邊)。在這個(gè)分區(qū)退出之后,該基準(zhǔn)就處于數(shù)列的中間位置。這個(gè)稱為分區(qū)(partition)操作;
- 遞歸地(recursive)把小于基準(zhǔn)值元素的子數(shù)列和大于基準(zhǔn)值元素的子數(shù)列排序;
遞歸的最底部情形,是數(shù)列的大小是零或一,也就是永遠(yuǎn)都已經(jīng)被排序好了。雖然一直遞歸下去,但是這個(gè)算法總會(huì)退出,因?yàn)樵诿看蔚牡╥teration)中,它至少會(huì)把一個(gè)元素?cái)[到它最后的位置去。
動(dòng)圖演示
JavaScript代碼實(shí)現(xiàn)
function quickSort(arr,left,right){ var len = arr.length, partitionIndex, left = typeof left != 'number' ? 0 : left, right = typeof right != 'number' ? len - 1 : right; if(left < right){ partitionIndex = partition(arr,left,right); quickSort(arr,left,partitionIndex-1); quickSort(arr,partitionIndex+1,right); } return arr; } function partition(arr,left,right){ //分區(qū)操作 var prvot = left, //設(shè)定基準(zhǔn)值(pivot) index = pivot + 1; for(var i = index;i <= right;i++){ if(arr[i] < arr[pivot]){ swap(arr,i,index); index++; } } swap(arr,pivot,index - 1); return index-1; } function swap(arr,i ,j){ var temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } function partition2(arr,low,high){ let pivot = arr[low]; while(low < high){ while(low < high && arr[high] > pivot){ --high; } arr[low] = arr[high]; while(low < high && arr[low] <= pivot){ ++low } arr[high] = arr[low]; } arr[low] = pivot; return low; } function qunickSort2(arr,low,high){ if(low < high){ let pivot = pratition2(arr,low,high); quickSort2(arr,low,pivot - 1); quickSort2(arr,pivot + 1,high); } return arr; }
python代碼實(shí)現(xiàn)
def quickSort(arr,left=None,right=None): left = 0 if not isinstance(left,(int,float)) else left right = len(arr)-1 if not isinstance(right,(int,float)) else right if left < right: partitionIndex = partition(arr,left,right) quickSort(arr,left,partitionIndex-1) qunckSort(arr,partitionIndex+1,right) return arr def partition(arr,left,right): pivot = left index = pivot+1 i = index while i <= right: if arr[i] < arr[pivot]: swap(arr,i,index0 index+=1 i+=1 swap(arr,pivot,index-1) return index-1 def swap(arr,i,j): arr[i],arr[j] = arr[j],arr[i]
Go代碼實(shí)現(xiàn)
func quickSort(arr []int) []int{ return _quickSort(arr,0,len(arr)-1) } func _quickSort(arr []int,left,right int) []int{ if left < right { partitionIndex := partition(arr,left,right) _quickSort(arr,left,partitionIndex-1) _quickSort(arr,partitionIndex+1,right) } return arr } func partition(arr []int,left,right int)int{ pivot := left index := pivot + 1 for i := index; i <= right; i++{ if arr[i] < arr[pivot]{ swap(arr,i,index) index += 1 } } swap(arr,pivot,index-1) return index - 1 } func swap(arr []int, i, j int){ arr[i],arr[j] = arr[j],arr[i] }
C++代碼實(shí)現(xiàn)
Partition1(int A[],int low,int high){ int pivot = A[low]; while(low < high){ while(low<high && A[high] >= pivot){ --high; } A[low] = A[high]; while(low < high && A[low] <= pivot){ ++low; } A[high] = A[low]; } A[low] = pivot; return low; } void QuickSort(int A[], int low, int high) { if(low < high){ int pivot = Partition1(A,low,high); QuickSort(A,low,pivot - 1); QuickSort(A,pivot + 1,high); } }
Java代碼實(shí)現(xiàn)
public class QuickSort implements IArraySort{ @Override public int[] sort(int[] sourceArray) throws Exception{ //對arr進(jìn)行拷貝,不改變參數(shù)內(nèi)容 int[] arr = Arrays.copyOf(sourceArray,sourceArray.length); return quickSort(arr,0,arr.length - 1); } private int[] quickSort(int[] arr, int left, int right){ if(left < right){ int partitionIndex = partition(arr,left,right); quicksort(arr,left,partitionIndex - 1); quickSort(arr,partitionIndex + 1,right); } return arr; } private int partition(int[] arr, int left, int right){ //設(shè)定基準(zhǔn)值(pivot) int pivot = left; int index = pivot + 1; for(int i = index; i<= right; i++){ if(arr[i] < arr[pivot]){ swao(arr,i,index); index++; } } swap(arr,pivot,index - 1); return index - 1; } private void swap(int[] arr, int i, int j){ int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } }
堆排序
堆排序(Heapsort)是指利用堆這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計(jì)的一種排序算法。堆積是一個(gè)近似完全二叉樹的結(jié)構(gòu),并同時(shí)滿足堆積的性質(zhì):即子結(jié)點(diǎn)的鍵值或索引總是小于(或者大于)它的父節(jié)點(diǎn)。堆排序可以說是一種利用堆的概念來排序的選擇排序。分為兩種方法:
- 大頂堆:每個(gè)節(jié)點(diǎn)的值都大于或等于其子節(jié)點(diǎn)的值,在堆排序算法中用于升序排列;
- 小頂堆:每個(gè)節(jié)點(diǎn)的值都小于或等于其子節(jié)點(diǎn)的值,在堆排序算法中用于降序排列;
堆排序的平均時(shí)間復(fù)雜度為 Ο(nlogn)。
算法步驟
1.將待排序序列構(gòu)建成一個(gè)堆 H[0……n-1],根據(jù)(升序降序需求)選擇大頂堆或小頂堆;
2.把堆首(最大值)和堆尾互換;
3.把堆的尺寸縮小 1,并調(diào)用 shift_down(0),目的是把新的數(shù)組頂端數(shù)據(jù)調(diào)整到相應(yīng)位置;
4.重復(fù)步驟 2,直到堆的尺寸為 1。
動(dòng)圖演示
JavaScript代碼實(shí)現(xiàn)
var len; //因?yàn)槁暶鞯亩鄠€(gè)函數(shù)都需要數(shù)據(jù)長度,所以把len設(shè)置成為全局變量 function buildMaxHeap(arr){ //建立大頂堆 len = arr.length; for(var i = Math.floor(len/2);i>=0;i--){ heapify(arr,i); } } function heapify(arr,i){ //堆調(diào)整 var left = 2 * i + 1, right = 2 * i + 2, largest = i; if(left < len && arr[left] > arr[largest]){ largest = left; } if(right < len && arr[right] > arr[largest]){ largest = right; } if(largest != i){ swap(arr,i,largest); heapify(arr,largest); } } function swap(arr,i,j){ var temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } function heapSort(arr){ buildMaxHeap(arr); for(var i = arr.length-1; i > 0; i--){ swap(arr,0,i); len--; heapify(arr,0); } return arr; }
Python代碼實(shí)現(xiàn)
def buildMaxHeap(arr): import math for i in range(math.floor(len(arr)/2),-1,-1): heapify(arr,i) def heapify(arr,i): left = 2*i+1 right = 2*i+2 largest = i if left < arrLen and arr[left] > arr[largest]: largest = left if right < arrLen and arr[right] > arr[largest]: largest = right if largest != i: swap(arr,i,largest) heapify(arr,largest) def swap(arr,i,j): arr[i],arr[j] = arr[j],arr[i] def heapSort(arr): global arrLen aeeLen = len(arr) buildMasxHeap(arr) for i in range(len(arr)-1,0,-1): swap(arr,0,i) arrLen -= 1 heapify(arr,0) return arr
Go代碼實(shí)現(xiàn)
func heapSort(arr []int) []int { arrLen := len(arr) buildMaxHeap(arr, arrLen) for i := arrLen - 1; i >= 0; i-- { swap(arr, 0, i) arrLen -= 1 heapify(arr, 0, arrLen) } return arr } func buildMaxHeap(arr []int, arrLen int) { for i := arrLen / 2; i >= 0; i-- { heapify(arr, i, arrLen) } } func heapify(arr []int, i, arrLen int) { left := 2*i + 1 right := 2*i + 2 largest := i if left < arrLen && arr[left] > arr[largest] { largest = left } if right < arrLen && arr[right] > arr[largest] { largest = right } if largest != i { swap(arr, i, largest) heapify(arr, largest, arrLen) } } func swap(arr []int, i, j int) { arr[i], arr[j] = arr[j], arr[i] }
Java代碼實(shí)現(xiàn)
public class HeapSort implements IArraySort{ @Override public int[] sort(int[] sourceArray) throws Exception{ //對arr進(jìn)行拷貝,不改變參數(shù)內(nèi)容 int[] arr = Array.copyOf(sourceArray,sourceArray.length); int len = arr.length; buildMaxHeap(arr,len); for(int i = len - 1; i > 0; i--){ swap(arr,0,i); len--; heapify(arr,0,len); } return arr; } private void buildMaxHeap(int[] arr,int i , int len){ int left = 2 * i + 1; int right = 2 * i + 2; int largest = i; if(left < len && arr[left] > arr[largest]){ largest = left; } if(right < len && arr[right] > arr[largest]){ largest = right; } if(largest != i){ swap(arr,i,largest); heapify(arr,length,len); } } private void swap(int[] arr, int i, int j){ int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } }
到此這篇關(guān)于Java實(shí)現(xiàn)快速排序和堆排序的示例代碼的文章就介紹到這了,更多相關(guān)Java 排序內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
spring cloud gateway中如何讀取請求參數(shù)
這篇文章主要介紹了spring cloud gateway中如何讀取請求參數(shù)的操作,具有很好的參考價(jià)值,希望對大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2021-07-07SpringBoot+Vue+Redis實(shí)現(xiàn)單點(diǎn)登錄(一處登錄另一處退出登錄)
小編接到一個(gè)需求,需要實(shí)現(xiàn)用戶在瀏覽器登錄后,跳轉(zhuǎn)到其他頁面,當(dāng)用戶在其它地方又登錄時(shí),前面用戶登錄的頁面退出登錄,這篇文章主要介紹了SpringBoot+Vue+Redis實(shí)現(xiàn)單點(diǎn)登錄,需要的朋友可以參考下2019-12-12SpringBoot+OCR?實(shí)現(xiàn)圖片文字識(shí)別
本文主要介紹了SpringBoot+OCR 實(shí)現(xiàn)圖片文字識(shí)別,文中通過示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2021-12-12Java設(shè)計(jì)通用的返回?cái)?shù)據(jù)格式過程講解
現(xiàn)在很多的項(xiàng)目server端返回client端的數(shù)據(jù)多數(shù)以JSON格式返回,同時(shí)結(jié)合其它需要,通常加一下狀態(tài)碼和信息之類,給前端處理帶來很大的方便,這篇文章就用Java設(shè)計(jì)了通用的返回?cái)?shù)據(jù)格式,感興趣的同學(xué)可以參考下文2023-05-05使用maven實(shí)現(xiàn)有關(guān)Jsoup簡單爬蟲的步驟
這篇文章主要介紹了使用maven實(shí)現(xiàn)有關(guān)Jsoup簡單爬蟲的步驟,文中附含詳細(xì)示例代碼,有需要的朋友可以借鑒參考下,希望能夠有所幫助2021-09-09學(xué)習(xí)Java模擬實(shí)現(xiàn)百度文檔在線瀏覽
這片文章介紹了如何使用Java模擬實(shí)現(xiàn)百度文檔在線瀏覽,文章思路清晰,需要的朋友可以參考下2015-07-07一分鐘入門Java Spring Boot徹底解決SSM配置問題
Spring Boot是由Pivotal團(tuán)隊(duì)提供的全新框架,其設(shè)計(jì)目的是用來簡化新Spring應(yīng)用的初始搭建以及開發(fā)過程。該框架使用了特定的方式來進(jìn)行配置,從而使開發(fā)人員不再需要定義樣板化的配置。通過這種方式,Spring Boot致力于在蓬勃發(fā)展的快速應(yīng)用開發(fā)領(lǐng)域成為領(lǐng)導(dǎo)者2021-10-10