Java實現(xiàn)快速排序和堆排序的示例代碼
更新時間：2022年12月22日 10:55:13 作者：程序小猿2
這篇文章主要為大家詳細介紹了快速排序和堆排序的多種語言的實現(xiàn)（JavaScript、Python、Go語言、Java、C++），感興趣的小伙伴可以了解一下
快速排序
快速排序是由東尼·霍爾所發(fā)展的一種排序算法。在平均狀況下，排序 n 個項目要 Ο(nlogn) 次比較。在最壞狀況下則需要 Ο(n2) 次比較，但這種狀況并不常見。事實上，快速排序通常明顯比其他 Ο(nlogn) 算法更快，因為它的內部循環(huán)（inner loop）可以在大部分的架構上很有效率地被實現(xiàn)出來。
快速排序使用分治法（Divide and conquer）策略來把一個串行（list）分為兩個子串行（sub-lists）。
快速排序又是一種分而治之思想在排序算法上的典型應用。本質上來看，快速排序應該算是在冒泡排序基礎上的遞歸分治法。
快速排序的名字起的是簡單粗暴，因為一聽到這個名字你就知道它存在的意義，就是快，而且效率高！它是處理大數(shù)據(jù)最快的排序算法之一了。雖然 Worst Case 的時間復雜度達到了 O(n²)，但是人家就是優(yōu)秀，在大多數(shù)情況下都比平均時間復雜度為 O(n logn) 的排序算法表現(xiàn)要更好，可是這是為什么呢，我也不知道。好在我的強迫癥又犯了，查了 N 多資料終于在《算法藝術與信息學競賽》上找到了滿意的答案：
快速排序的最壞運行情況是 O(n²)，比如說順序數(shù)列的快排。但它的平攤期望時間是 O(nlogn)，且 O(nlogn) 記號中隱含的常數(shù)因子很小，比復雜度穩(wěn)定等于 O(nlogn) 的歸并排序要小很多。所以，對絕大多數(shù)順序性較弱的隨機數(shù)列而言，快速排序總是優(yōu)于歸并排序。
算法步驟
- 從數(shù)列中挑出一個元素，稱為 “基準”（pivot）;
- 重新排序數(shù)列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的后面（相同的數(shù)可以到任一邊）。在這個分區(qū)退出之后，該基準就處于數(shù)列的中間位置。這個稱為分區(qū)（partition）操作；
- 遞歸地（recursive）把小于基準值元素的子數(shù)列和大于基準值元素的子數(shù)列排序；
遞歸的最底部情形，是數(shù)列的大小是零或一，也就是永遠都已經(jīng)被排序好了。雖然一直遞歸下去，但是這個算法總會退出，因為在每次的迭代（iteration）中，它至少會把一個元素擺到它最后的位置去。
動圖演示
JavaScript代碼實現(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, //設定基準值（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代碼實現(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代碼實現(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++代碼實現(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代碼實現(xiàn)
public class QuickSort implements IArraySort{
@Override
public int[] sort(int[] sourceArray) throws Exception{
//對arr進行拷貝，不改變參數(shù)內容
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){
//設定基準值(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é)點。堆排序可以說是一種利用堆的概念來排序的選擇排序。分為兩種方法：
- 大頂堆：每個節(jié)點的值都大于或等于其子節(jié)點的值，在堆排序算法中用于升序排列；
- 小頂堆：每個節(jié)點的值都小于或等于其子節(jié)點的值，在堆排序算法中用于降序排列；
堆排序的平均時間復雜度為 Ο(nlogn)。
算法步驟
1.將待排序序列構建成一個堆 H[0……n-1]，根據(jù)（升序降序需求）選擇大頂堆或小頂堆；
2.把堆首（最大值）和堆尾互換；
3.把堆的尺寸縮小 1，并調用 shift_down(0)，目的是把新的數(shù)組頂端數(shù)據(jù)調整到相應位置；
4.重復步驟 2，直到堆的尺寸為 1。
動圖演示
JavaScript代碼實現(xiàn)
var len; //因為聲明的多個函數(shù)都需要數(shù)據(jù)長度，所以把len設置成為全局變量
function buildMaxHeap(arr){ //建立大頂堆
len = arr.length;
for(var i = Math.floor(len/2);i>=0;i--){
heapify(arr,i);
}
}
function heapify(arr,i){ //堆調整
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代碼實現(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代碼實現(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代碼實現(xiàn)
public class HeapSort implements IArraySort{
@Override
public int[] sort(int[] sourceArray) throws Exception{
//對arr進行拷貝，不改變參數(shù)內容
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;
}
} 到此這篇關于Java實現(xiàn)快速排序和堆排序的示例代碼的文章就介紹到這了,更多相關Java 排序內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
spring cloud gateway中如何讀取請求參數(shù)
這篇文章主要介紹了spring cloud gateway中如何讀取請求參數(shù)的操作，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2021-07-07
reduce()是Java Stream API中的一個重要終端操作,用于將流中的元素通過二元運算符結合起來,生成單一結果,它主要用于計算總和、乘積、最大值、最小值和字符串連接等,本文給大家介紹Java Stream reduce(),感興趣的朋友一起看看吧2024-10-10
SpringBoot+Vue+Redis實現(xiàn)單點登錄(一處登錄另一處退出登錄)
小編接到一個需求，需要實現(xiàn)用戶在瀏覽器登錄后，跳轉到其他頁面，當用戶在其它地方又登錄時，前面用戶登錄的頁面退出登錄，這篇文章主要介紹了SpringBoot+Vue+Redis實現(xiàn)單點登錄,需要的朋友可以參考下2019-12-12
本文主要介紹了SpringBoot+OCR 實現(xiàn)圖片文字識別，文中通過示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-12-12
這篇文章主要介紹了java中線程掛起的幾種方式詳解,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下2019-08-08
現(xiàn)在很多的項目server端返回client端的數(shù)據(jù)多數(shù)以JSON格式返回，同時結合其它需要，通常加一下狀態(tài)碼和信息之類，給前端處理帶來很大的方便，這篇文章就用Java設計了通用的返回數(shù)據(jù)格式，感興趣的同學可以參考下文2023-05-05
這篇文章主要介紹了使用maven實現(xiàn)有關Jsoup簡單爬蟲的步驟，文中附含詳細示例代碼，有需要的朋友可以借鑒參考下，希望能夠有所幫助2021-09-09
這片文章介紹了如何使用Java模擬實現(xiàn)百度文檔在線瀏覽，文章思路清晰,需要的朋友可以參考下2015-07-07
今天小編就為大家分享一篇關于Java內部類及其特點的講解，小編覺得內容挺不錯的，現(xiàn)在分享給大家，具有很好的參考價值，需要的朋友一起跟隨小編來看看吧2019-01-01
一分鐘入門Java Spring Boot徹底解決SSM配置問題
Spring Boot是由Pivotal團隊提供的全新框架，其設計目的是用來簡化新Spring應用的初始搭建以及開發(fā)過程。該框架使用了特定的方式來進行配置，從而使開發(fā)人員不再需要定義樣板化的配置。通過這種方式，Spring Boot致力于在蓬勃發(fā)展的快速應用開發(fā)領域成為領導者2021-10-10