Java十大經(jīng)典排序算法的實(shí)現(xiàn)圖解
前言
本文章主要是講解我個(gè)人在學(xué)習(xí)Java開發(fā)環(huán)境的排序算法時(shí)做的一些準(zhǔn)備，以及個(gè)人的心得體會(huì)，匯集成本篇文章，作為自己對排序算法理解的總結(jié)與筆記。
內(nèi)容主要是關(guān)于十大經(jīng)典排序算法的簡介、原理、動(dòng)靜態(tài)圖解和源碼實(shí)現(xiàn)的分析。
對于一名程序員來講，我們都知道數(shù)據(jù)結(jié)構(gòu)與算法起初是用于C語言居多，然而在Java語言下使用算法的案例卻很少，因此，特別整理了在Java開發(fā)環(huán)境的排序算法，供大家一起學(xué)習(xí)探討。
一、排序算法
1.排序算法概述（百度百科）
所謂排序算法，即通過特定的算法因式將一組或多組數(shù)據(jù)按照既定模式進(jìn)行重新排序。這種新序列遵循著一定的規(guī)則，體現(xiàn)出一定的規(guī)律，因此，經(jīng)處理后的數(shù)據(jù)便于篩選和計(jì)算，大大提高了計(jì)算效率。對于排序，我們首先要求其具有一定的穩(wěn)定性，即當(dāng)兩個(gè)相同的元素同時(shí)出現(xiàn)于某個(gè)序列之中，則經(jīng)過一定的排序算法之后，兩者在排序前后的相對位置不發(fā)生變化。換言之，即便是兩個(gè)完全相同的元素，它們在排序過程中也是各有區(qū)別的，不允許混淆不清。
2.《數(shù)據(jù)結(jié)構(gòu)與算法》中的排序算法
常見的排序算法有：插入排序、希爾排序、選擇排序、冒泡排序、歸并排序、快速排序、堆排序、基數(shù)排序等。
算法圖解（菜鳥教程借圖）：
圖解分析：
3.算法分析
時(shí)間復(fù)雜度
平方階 (O(n2)) 排序 各類簡單排序：直接插入、直接選擇和冒泡排序。
線性對數(shù)階 (O(nlog2n)) 排序 快速排序、堆排序和歸并排序；
O(n1+§)) 排序，§ 是介于 0 和 1 之間的常數(shù)。 希爾排序
線性階 (O(n)) 排序 基數(shù)排序，此外還有桶、箱排序。
關(guān)于穩(wěn)定性
穩(wěn)定的排序算法：冒泡排序、插入排序、歸并排序和基數(shù)排序。
不是穩(wěn)定的排序算法：選擇排序、快速排序、希爾排序、堆排序。
名詞解釋：
- n：數(shù)據(jù)規(guī)模
- k："桶"的個(gè)數(shù)
- In-place：占用常數(shù)內(nèi)存，不占用額外內(nèi)存
- Out-place：占用額外內(nèi)存
- 穩(wěn)定性：排序后 2 個(gè)相等鍵值的順序和排序之前它們的順序相同
平均時(shí)間復(fù)雜度是指所有可能的輸入實(shí)例均以等概率的出現(xiàn)情況下得到算法的運(yùn)行時(shí)間
最壞時(shí)間復(fù)雜度，一般討論的時(shí)間復(fù)雜度均是最壞情況下的時(shí)間復(fù)雜度，這樣做的原因是最壞情況下的時(shí)間復(fù)雜度是算法在任何輸入實(shí)例上運(yùn)行的界限，這就保證了算法的運(yùn)行時(shí)間不會(huì)比最壞情況更長。
平均時(shí)間復(fù)雜度和最壞時(shí)間復(fù)雜度是否一樣，這就需要根據(jù)算法不同而不同了。
二、十大經(jīng)典排序算法（Java開發(fā)版）
PS：案例均以數(shù)組{15，63，97，12，235，66}排序?yàn)槔?/p>
1.冒泡排序
冒泡排序（Bubble Sort），是一種計(jì)算機(jī)科學(xué)領(lǐng)域的較簡單的排序算法。
它重復(fù)地走訪過要排序的元素列，依次比較兩個(gè)相鄰的元素，如果順序（如從大到小、首字母從Z到A）錯(cuò)誤就把他們交換過來。走訪元素的工作是重復(fù)地進(jìn)行直到?jīng)]有相鄰元素需要交換，也就是說該元素列已經(jīng)排序完成。
這個(gè)算法的名字由來是因?yàn)樵叫〉脑貢?huì)經(jīng)由交換慢慢“浮”到數(shù)列的頂端（升序或降序排列），就如同碳酸飲料中二氧化碳的氣泡最終會(huì)上浮到頂端一樣，故名“冒泡排序”。
1.1實(shí)現(xiàn)原理
- 比較相鄰的元素。如果第一個(gè)比第二個(gè)大，就交換他們兩個(gè)。
- 對每一對相鄰元素做同樣的工作，從開始第一對到結(jié)尾的最后一對。在這一點(diǎn)，最后的元素應(yīng)該會(huì)是最大的數(shù)。
- 針對所有的元素重復(fù)以上的步驟，除了最后一個(gè)。
- 持續(xù)每次對越來越少的元素重復(fù)上面的步驟，直到?jīng)]有任何一對數(shù)字需要比較。
1.2動(dòng)圖演示
1.3實(shí)例展示
import java.util.Arrays;
public class BubbleSort {
public static void main(String[] args) {
int[] arrays =new int[]{15,63,97,12,235,66};
for (int i=0;i<arrays.length-1;i++){
// 控制比較次數(shù),三者交換，實(shí)現(xiàn)排序
for(int j=0;j<arrays.length-1-i;j++){
if (arrays[j] > arrays[j+1]){
int temp = 0;//類似空桶
temp = arrays[j]; //A桶中水倒入空桶C中
arrays[j] = arrays[j+1];//把B桶的水倒入A桶中
arrays[j+1] = temp;//把C桶的水倒入B桶中
}
}
}
System.out.println(Arrays.toString(arrays));
}
}排序結(jié)果展示：
2.快速排序
快速排序（Quicksort），計(jì)算機(jī)科學(xué)詞匯，適用領(lǐng)域Pascal，c++等語言，是對冒泡排序算法的一種改進(jìn)。
2.1實(shí)現(xiàn)原理
快速排序是對冒泡排序的一種改進(jìn)。通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另一部分所有的數(shù)據(jù)都要小，然后再按此方法對這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個(gè)排序過程可以遞歸進(jìn)行，以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列
2.2 動(dòng)圖演示
2.3實(shí)例展示
import java.util.Arrays;
public class QuickSort {
public static void main(String[] args) {
int[] arrays = new int[]{15,63,97,12,235,66};
sort(arrays,0,arrays.length-1);
System.out.println(Arrays.toString(arrays));
}
public static void sort(int[] arrays,int left,int right){
int l = left;
int r = right;
int pivot = arrays[(left+right)/2];
int temp = 0;
while (l<r){
//在左邊查找小于中間值的
while(arrays[l]<pivot){
l++;
}
//查詢右邊小于中間值
while (arrays[r]>pivot){
r--;
}
if (l>=r){
break;
}
temp = arrays[l];
arrays[l] = arrays[r];
arrays[r] = temp;
// 交換完數(shù)據(jù)arrays[l] = pivot
if (arrays[l]==pivot){
r--;
}
if (arrays[r]==pivot){
l++;
}
if (r==l){
l++;
r--;
}
if (left<r){
sort(arrays,left,r);
}
if (right>l){
sort(arrays,l,right);
}
}
}
}排序結(jié)果展示：
3.基數(shù)排序
基數(shù)排序（radix sort）屬于“分配式排序”（distribution sort），又稱“桶子法”（bucket sort）或bin sort，顧名思義，它是透過鍵值的部份資訊，將要排序的元素分配至某些“桶”中，藉以達(dá)到排序的作用，基數(shù)排序法是屬于穩(wěn)定性的排序，其時(shí)間復(fù)雜度為O (nlog(r)m)，其中r為所采取的基數(shù)，而m為堆數(shù)，在某些時(shí)候，基數(shù)排序法的效率高于其它的穩(wěn)定性排序法。
基數(shù)排序是1887年赫爾曼、何樂禮發(fā)明的。思想是講整數(shù)按位數(shù)切割成不同的數(shù)字，然后按每個(gè)位數(shù)分別比較。
3.1實(shí)現(xiàn)原理
講所有的待比較數(shù)值統(tǒng)一設(shè)置為同樣的數(shù)位長度，位數(shù)比較短的數(shù)前面補(bǔ)零，然后從最地位開始依次進(jìn)行一次排序，這樣從最低位排序一直到最高位排序完成以后，數(shù)列就變成一個(gè)有序序列。
3.2 動(dòng)圖演示
3.3實(shí)例展示
import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;
public class BasicSort {
public static void main(String[] args) {
int[] arrays = new int[]{15,63,97,12,235,66};
SimpleDateFormat simpleDateFormat =new SimpleDateFormat("yyyy-mm-dd HH:MM:ss:SS");
System.out.println("開始排序前:"+simpleDateFormat.format(new Date()));
sort(arrays);
System.out.println("排序結(jié)束:"+simpleDateFormat.format(new Date()));
}
// 1.獲取原序列的最大位多少
// @param arrays
public static void sort(int[] arrays){
// 獲取最大位數(shù)
int max = 0;
for(int i=0;i<arrays.length;i++){
if (arrays[i]>max){
max = arrays[i];
}
}
// 獲取字符串長度，所以把int類型轉(zhuǎn)字符串類型
int maxLength = (max+"").length();
// 定義二維數(shù)組，大小10，表示10個(gè)桶，每一個(gè)桶則是一個(gè)數(shù)組
// [[],[],[],[],[]...]
int[][] bucket = new int[10][arrays.length];
// 輔助數(shù)組
int[] bucketElementCount = new int[10];
// 循環(huán)獲取無序數(shù)列
for (int j=0;j<arrays.length;j++){
int locationElement = arrays[j]%10;
// 放入桶中
bucket[locationElement][bucketElementCount[locationElement]] = arrays[j] ;
bucketElementCount[locationElement]++;
}
// 遍歷每一個(gè)桶，講元素存放原數(shù)組中
int index = 0;
for (int k = 0;k<bucketElementCount.length;k++){
if (bucketElementCount[k] !=0){
for (int l = 0;l<bucketElementCount[k];l++){
arrays[index++] = bucket[k][l];
}
}
bucketElementCount[k] = 0;
}
System.out.println(Arrays.toString(arrays));
// 第一輪針對個(gè)位數(shù)進(jìn)行比較
for (int j = 0;j<arrays.length;j++){
int locationElement = arrays[j]/1%10;
bucket[locationElement][bucketElementCount[locationElement]] = arrays[j];
bucketElementCount[locationElement]++;
}
// 取出來按照桶的順序放回原數(shù)組中
int indx = 0;
for (int k = 0;k<bucketElementCount.length;k++){
if (bucketElementCount[k] !=0){
for (int l=0;l<bucketElementCount[k];l++){
arrays[indx++] = bucket[k][l];
}
}
bucketElementCount[k] = 0;
}
// 判斷十位數(shù)
for (int j = 0;j<arrays.length;j++){
int locationElement = arrays[j]/10%10;
bucket[locationElement][bucketElementCount[locationElement]] = arrays[j];
bucketElementCount[locationElement]++;
}
// 取出來按照桶的順序放回原數(shù)組中
indx = 0;
for (int k = 0;k<bucketElementCount.length;k++){
if (bucketElementCount[k] !=0){
for (int l=0;l<bucketElementCount[k];l++){
arrays[indx++] = bucket[k][l];
}
}
bucketElementCount[k] = 0;
}
// 獲取百位數(shù)比較
for (int j = 0;j<arrays.length;j++){
int locationElement = arrays[j]/100%10;
bucket[locationElement][bucketElementCount[locationElement]] = arrays[j];
bucketElementCount[locationElement]++;
}
// 取出來按照桶的順序放回原數(shù)組中
indx = 0;
for (int k = 0;k<bucketElementCount.length;k++){
if (bucketElementCount[k] !=0){
for (int l=0;l<bucketElementCount[k];l++){
arrays[indx++] = bucket[k][l];
}
}
bucketElementCount[k] = 0;
}
System.out.println("基數(shù)排序后的順序:"+Arrays.toString(arrays));
}
}排序結(jié)果展示：
4.插入排序
插入排序，一般也被稱為直接插入排序。對于少量元素的排序，它是一個(gè)有效的算法 。插入排序是一種最簡單的排序方法，它的基本思想是將一個(gè)記錄插入到已經(jīng)排好序的有序表中，從而一個(gè)新的、記錄數(shù)增1的有序表。在其實(shí)現(xiàn)過程使用雙層循環(huán)，外層循環(huán)對除了第一個(gè)元素之外的所有元素，內(nèi)層循環(huán)對當(dāng)前元素前面有序表進(jìn)行待插入位置查找，并進(jìn)行移動(dòng) 。
4.1實(shí)現(xiàn)原理
插入排序的工作方式像許多人排序一手撲克牌。開始時(shí)，我們的左手為空并且桌子上的牌面向下。然后，我們每次從桌子上拿走一張牌并將它插入左手中正確的位置。為了找到一張牌的正確位置，我們從右到左將它與已在手中的每張牌進(jìn)行比較。拿在左手上的牌總是排序好的，原來這些牌是桌子上牌堆中頂部的牌。
插入排序是指在待排序的元素中，假設(shè)前面n-1(其中n>=2)個(gè)數(shù)已經(jīng)是排好順序的，現(xiàn)將第n個(gè)數(shù)插到前面已經(jīng)排好的序列中，然后找到合適自己的位置，使得插入第n個(gè)數(shù)的這個(gè)序列也是排好順序的。按照此法對所有元素進(jìn)行插入，直到整個(gè)序列排為有序的過程，稱為插入排序。
4.2 動(dòng)圖演示
4.3實(shí)例展示
public class InsertSort {
public static void main(String[] args) {
int[] array = new int[]{15,63,97,12,235,66};
//控制拿去每一個(gè)元素
for(int i=1;i<array.length;i++){
//比較次數(shù)
for (int j=i;j>=1;j--){
//是否小于前面的元素
if (array[j]<array[j-1]){
int temp = 0;
temp = array[j];
array[j] = array[j-1];
array[j-1] = temp;
}else {
//continue 與 break
break;
}
}
}
System.out.println("排序后的結(jié)果："+ Arrays.toString(array));
}
}排序結(jié)果展示：
5.選擇排序
選擇排序（Selection sort）是一種簡單直觀的排序算法。它的工作原理是：第一次從待排序的數(shù)據(jù)元素中選出最?。ɑ蜃畲螅┑囊粋€(gè)元素，存放在序列的起始位置，然后再從剩余的未排序元素中尋找到最?。ù螅┰?，然后放到已排序的序列的末尾。以此類推，直到全部待排序的數(shù)據(jù)元素的個(gè)數(shù)為零。選擇排序是不穩(wěn)定的排序方法。
5.1實(shí)現(xiàn)原理
第一次從待排序的數(shù)據(jù)元素中選出最?。ɑ蜃畲螅┑囊粋€(gè)元素，存放在序列的起始位置，然后再從剩余的未排序元素中尋找到最?。ù螅┰兀缓蠓诺揭雅判虻男蛄械哪┪?。以此類推，直到全部待排序的數(shù)據(jù)元素的個(gè)數(shù)為零。選擇排序是不穩(wěn)定的排序方法。
5.2 動(dòng)圖演示
5.3實(shí)例展示
import java.util.Arrays;
public class SelectSort {
public static void main(String[] args) {
int[] arr = new int[]{15,63,97,12,235,66};
for (int i=0;i<arr.length;i++){
for (int j=arr.length-1;j>i;j--){
if (arr[j]<arr[i]){
int temp = 0;
temp = arr[j];
arr[j] = arr[i];
arr[i] = temp;
}
}
}
System.out.println("選擇排序后的結(jié)果:"+ Arrays.toString(arr));
}
}排序結(jié)果展示：
6.希爾排序
希爾排序(Shell's Sort)是插入排序的一種又稱“縮小增量排序”（Diminishing Increment Sort），是插入排序算法的一種更高效的改進(jìn)版本。希爾排序是非穩(wěn)定排序算法。該方法因 D.L.Shell 于 1959 年提出而得名。
希爾排序是把記錄按下標(biāo)的一定增量分組，對每組使用直接插入排序算法排序；隨著增量逐漸減少，每組包含的關(guān)鍵詞越來越多，當(dāng)增量減至 1 時(shí)，整個(gè)文件恰被分成一組，算法便終止。
6.1實(shí)現(xiàn)原理
先取一個(gè)小于n的整數(shù)d1作為第一個(gè)增量，把文件的全部記錄分組。所有距離為d1的倍數(shù)的記錄放在同一個(gè)組中。先在各組內(nèi)進(jìn)行直接插入排序；然后，取第二個(gè)增量d2
般的初次取序列的一半為增量，以后每次減半，直到增量為1。
6.2 動(dòng)圖演示
6.3實(shí)例展示
import java.util.Arrays;
public class ShellSort {
public static void main(String[] args) {
int[] array = new int[]{15,63,97,12,235,66};
// 實(shí)現(xiàn)增量變化
for (int gap = array.length/2;gap>0;gap/=2){
for (int i=gap;i<array.length;i++){
for (int j=i-gap;j>=0;j-=gap){
if (array[j]>array[j+gap]){
int temp = 0;
temp = array[j];
array[j] = array[j+gap];
array[j+gap] = temp;
}
}
}
}
System.out.println(Arrays.toString(array));
}
}排序結(jié)果展示：
7.歸并排序
歸并排序（Merge Sort）是建立在歸并操作上的一種有效，穩(wěn)定的排序算法，該算法是采用分治法（Divide and Conquer）的一個(gè)非常典型的應(yīng)用。將已有序的子序列合并，得到完全有序的序列；即先使每個(gè)子序列有序，再使子序列段間有序。若將兩個(gè)有序表合并成一個(gè)有序表，稱為二路歸并。
7.1實(shí)現(xiàn)原理
- 第一步：申請空間，使其大小為兩個(gè)已經(jīng)排序序列之和，該空間用來存放合并后的序列
- 第二步：設(shè)定兩個(gè)指針，最初位置分別為兩個(gè)已經(jīng)排序序列的起始位置
- 第三步：比較兩個(gè)指針?biāo)赶虻脑?，選擇相對小的元素放入到合并空間，并移動(dòng)指針到下一位置重復(fù)步驟3直到某一指針超出序列尾將另一序列剩下的所有元素直接復(fù)制到合并序列尾
我們需要將兩個(gè)已經(jīng)有序的子序列合并成一個(gè)有序序列，比如上圖最后一次合并，將[2,4,5,6]和[1,3,7,8]已經(jīng)有序的子序列合并最終序列[1,2,3,4,5,6,7,8]
7.2 動(dòng)圖演示
7.3實(shí)例展示
import java.util.Arrays;
public class MSort {
public static void main(String[] args) {
int[] array = new int[]{15,63,97,12,235,66};
//臨時(shí)數(shù)組
int[] temp = new int[array.length];
sort(array,0,array.length-1,temp);
System.out.println(Arrays.toString(array));
}
public static void sort(int[] array,int left,int right,int[] temp){
if (left<right){
// 求出中間值
int mid = (left+right)/2;
// 向左邊分解
sort(array,left,mid,temp);
// 向右邊分解
sort(array,mid+1,right,temp);
// 合并數(shù)據(jù)
sum(array,left,right,mid,temp);
}
}
/**
* 合并元素
* @param array
* @param left
* @param right
* @param mid
* @param temp
*/
public static void sum(int[] array,int left,int right,int mid,int[] temp){
int i = left;
int j = mid+1;
// 指向臨時(shí)數(shù)組下標(biāo)
int t = 0;
// 開始循環(huán)比較左右兩遍數(shù)組元素比較
while (i<=mid && j<=right){
if (array[i]<=array[j]){
temp[t] = array[i];
t++;
i++;
}else {
temp[t] = array[j];
t++;
j++;
}
}
// 把剩余的元素直接存放在臨時(shí)數(shù)組中
while(i<=mid){
temp[t] = array[i];
t++;
i++;
}
while (j<=right){
temp[t] = array[j];
t++;
j++;
}
// 臨時(shí)數(shù)組中的元素拷貝至原數(shù)組中
int tempIndex = left;
int k = 0;
while (tempIndex<=right){
array[tempIndex] = temp[k];
k++;
tempIndex++;
}
}
75 }排序結(jié)果展示：
8.計(jì)數(shù)排序
計(jì)數(shù)排序是一個(gè)非基于比較的排序算法，該算法于1954年由 Harold H. Seward 提出。它的優(yōu)勢在于在對一定范圍內(nèi)的整數(shù)排序時(shí)，它的復(fù)雜度為Ο(n+k)（其中k是整數(shù)的范圍），快于任何比較排序算法。 當(dāng)然這是一種犧牲空間換取時(shí)間的做法，而且當(dāng)O(k)>O(n*log(n))的時(shí)候其效率反而不如基于比較的排序（基于比較的排序的時(shí)間復(fù)雜度在理論上的下限是O(n*log(n)), 如歸并排序，堆排序）
8.1實(shí)現(xiàn)原理
假設(shè)輸入的線性表L的長度為n，L=L1,L2,..,Ln；線性表的元素屬于有限偏序集S，|S|=k且k=O(n)，S={S1,S2,..Sk}；則計(jì)數(shù)排序可以描述如下：
- 掃描整個(gè)集合S，對每一個(gè)Si∈S，找到在線性表L中小于等于Si的元素的個(gè)數(shù)T(Si)；
- 掃描整個(gè)線性表L，對L中的每一個(gè)元素Li，將Li放在輸出線性表的第T(Li)個(gè)位置上，并將T(Li)減1。
8.2 動(dòng)圖演示
8.3實(shí)例展示
public class CountSort {
public static void main(String[]args){
//排序的數(shù)組
int a[]={15,63,97,12,235,66};
int b[]=countSort(a);
for(int i:b){
System.out.print( i+",");
}
System.out.println();
}
public static int[] countSort(int[]a){
int b[] = new int[a.length];
int max = a[0],min = a[0];
for(int i:a){
if(i>max){
max=i;
}
if(i<min){
min=i;
}
}//這里k的大小是要排序的數(shù)組中，元素大小的極值差+1
int k=max-min+1;
int c[]=new int[k];
for(int i=0;i<a.length;++i){
c[a[i]-min]+=1;//優(yōu)化過的地方，減小了數(shù)組c的大小
}
for(int i=1;i<c.length;++i){
c[i]=c[i]+c[i-1];
}
for(int i=a.length-1;i>=0;--i){
b[--c[a[i]-min]]=a[i];//按存取的方式取出c的元素
}
return b;
}
}排序結(jié)果展示：
9.堆排序
堆排序（英語:Heapsort）是指利用堆這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計(jì)的一種排序算法。堆是一個(gè)近似完全二叉樹的結(jié)構(gòu)，并同時(shí)滿足堆積的性質(zhì)：即子結(jié)點(diǎn)的鍵值或索引總是小于（或者大于）它的父節(jié)點(diǎn)。
9.1實(shí)現(xiàn)原理
- 創(chuàng)建一個(gè)堆 H[0……n-1]；
- 把堆首（最大值）和堆尾互換；
- 把堆的尺寸縮小 1，并調(diào)用 shift_down(0)，目的是把新的數(shù)組頂端數(shù)據(jù)調(diào)整到相應(yīng)位置；
- 重復(fù)步驟 2，直到堆的尺寸為 1。
9.2 動(dòng)圖演示
9.3實(shí)例展示
public static int[] heapSort(int[] array) {
//這里元素的索引是從0開始的,所以最后一個(gè)非葉子結(jié)點(diǎn)array.length/2 - 1
for (int i = array.length / 2 - 1; i >= 0; i--) {
adjustHeap(array, i, array.length); //調(diào)整堆
}
// 上述邏輯，建堆結(jié)束
// 下面，開始排序邏輯
for (int j = array.length - 1; j > 0; j--) {
// 元素交換,作用是去掉大頂堆
// 把大頂堆的根元素，放到數(shù)組的最后；換句話說，就是每一次的堆調(diào)整之后，都會(huì)有一個(gè)元素到達(dá)自己的最終位置
swap(array, 0, j);
// 元素交換之后，毫無疑問，最后一個(gè)元素?zé)o需再考慮排序問題了。
// 接下來我們需要排序的，就是已經(jīng)去掉了部分元素的堆了，這也是為什么此方法放在循環(huán)里的原因
// 而這里，實(shí)質(zhì)上是自上而下，自左向右進(jìn)行調(diào)整的
adjustHeap(array, 0, j);
}
return array;
}
/**
* 整個(gè)堆排序最關(guān)鍵的地方
* @param array 待組堆
* @param i 起始結(jié)點(diǎn)
* @param length 堆的長度
*/
public static void adjustHeap(int[] array, int i, int length) {
// 先把當(dāng)前元素取出來，因?yàn)楫?dāng)前元素可能要一直移動(dòng)
int temp = array[i];
for (int k = 2 * i + 1; k < length; k = 2 * k + 1) { //2*i+1為左子樹i的左子樹(因?yàn)閕是從0開始的),2*k+1為k的左子樹
// 讓k先指向子節(jié)點(diǎn)中最大的節(jié)點(diǎn)
if (k + 1 < length && array[k] < array[k + 1]) { //如果有右子樹,并且右子樹大于左子樹
k++;
}
//如果發(fā)現(xiàn)結(jié)點(diǎn)(左右子結(jié)點(diǎn))大于根結(jié)點(diǎn)，則進(jìn)行值的交換
if (array[k] > temp) {
swap(array, i, k);
// 如果子節(jié)點(diǎn)更換了，那么，以子節(jié)點(diǎn)為根的子樹會(huì)受到影響,所以，循環(huán)對子節(jié)點(diǎn)所在的樹繼續(xù)進(jìn)行判斷
i = k;
} else { //不用交換，直接終止循環(huán)
break;
}
}
}
/**
* 交換元素
* @param arr
* @param a 元素的下標(biāo)
* @param b 元素的下標(biāo)
*/
public static void swap(int[] arr, int a, int b) {
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}排序結(jié)果展示：
10.桶排序
桶排序 (Bucket sort)或所謂的箱排序，是一個(gè)排序算法，工作的原理是將數(shù)組分到有限數(shù)量的桶子里。每個(gè)桶子再個(gè)別排序（有可能再使用別的排序算法或是以遞歸方式繼續(xù)使用桶排序進(jìn)行排序）。桶排序是鴿巢排序的一種歸納結(jié)果。當(dāng)要被排序的數(shù)組內(nèi)的數(shù)值是均勻分配的時(shí)候，桶排序使用線性時(shí)間（Θ（n））。但桶排序并不是 比較排序，他不受到 O(n log n) 下限的影響。
10.1實(shí)現(xiàn)原理
假定：輸入是由一個(gè)隨機(jī)過程產(chǎn)生的[0, 1)區(qū)間上均勻分布的實(shí)數(shù)。將區(qū)間[0, 1)劃分為n個(gè)大小相等的子區(qū)間（桶），每桶大小1/n：[0, 1/n)， [1/n, 2/n)， [2/n, 3/n)，…，[k/n, (k+1)/n )，…將n個(gè)輸入元素分配到這些桶中，對桶中元素進(jìn)行排序，然后依次連接桶輸入0 ≤A[1..n] <1輔助數(shù)組B[0..n-1]是一指針數(shù)組，指向桶（鏈表）。
10.2 動(dòng)圖演示
然后，元素在每個(gè)桶中排序：
10.3實(shí)例展示
public static void basket(int data[])//data為待排序數(shù)組
{
int n=data.length;
int bask[][]=new int[10][n];
int index[]=new int[10];
int max=Integer.MIN_VALUE;
for(int i=0;i<n;i++)
{
max=max>(Integer.toString(data[i]).length())?max:(Integer.toString(data[i]).length());
}
String str;
for(int i=max-1;i>=0;i--)
{
for(int j=0;j<n;j++)
{
str="";
if(Integer.toString(data[j]).length()<max)
{
for(int k=0;k<max-Integer.toString(data[j]).length();k++)
str+="0";
}
str+=Integer.toString(data[j]);
bask[str.charAt(i)-'0'][index[str.charAt(i)-'0']++]=data[j];
}
int pos=0;
for(int j=0;j<10;j++)
{
for(int k=0;k<index[j];k++)
{
data[pos++]=bask[j][k];
}
}
for(intx=0;x<10;x++)index[x]=0;
}
}排序結(jié)果展示：
以上就是Java十大經(jīng)典排序算法的實(shí)現(xiàn)圖解的詳細(xì)內(nèi)容，更多關(guān)于Java排序算法的資料請關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
今天小編就為大家分享一篇關(guān)于Java算法之串的簡單處理，小編覺得內(nèi)容挺不錯(cuò)的，現(xiàn)在分享給大家，具有很好的參考價(jià)值，需要的朋友一起跟隨小編來看看吧2019-03-03
這篇文章主要介紹了Java 遍歷 String 字符串所有字符的操作，具有很好的參考價(jià)值，希望對大家有所幫助。一起跟隨小編過來看看吧2020-10-10
Java二維數(shù)組查找功能代碼實(shí)現(xiàn)
這篇文章主要介紹了Java二維數(shù)組查找功能代碼實(shí)現(xiàn),文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2020-06-06
這篇文章主要介紹了MyBatis-Plus代碼生成器的使用詳解，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-11-11
這篇文章主要為大家介紹了Netty實(shí)戰(zhàn)源碼解析NIO編程的核心組件及關(guān)系詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2022-12-12
java實(shí)現(xiàn)多線程的兩種方式繼承Thread類和實(shí)現(xiàn)Runnable接口的方法
下面小編就為大家?guī)硪黄猨ava實(shí)現(xiàn)多線程的兩種方式繼承Thread類和實(shí)現(xiàn)Runnable接口的方法。小編覺得挺不錯(cuò)的，現(xiàn)在就分享給大家，也給大家做個(gè)參考。一起跟隨小編過來看看吧2016-09-09
OPENCV+JAVA實(shí)現(xiàn)人臉識(shí)別
這篇文章主要為大家詳細(xì)介紹了OPENCV+JAVA實(shí)現(xiàn)人臉識(shí)別，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2018-02-02
詳解Java是如何通過接口來創(chuàng)建代理并進(jìn)行http請求
今天給大家?guī)淼闹R(shí)是關(guān)于Java的,文章圍繞Java是如何通過接口來創(chuàng)建代理并進(jìn)行http請求展開,文中有非常詳細(xì)的介紹及代碼示例,需要的朋友可以參考下2021-06-06
這篇文章主要介紹了IDEA代碼規(guī)范插件P3C+代碼注釋模板配置方法,本文通過圖文并茂的形式給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2021-01-01
SpringBoot Mybatis如何配置多數(shù)據(jù)源并分包
這篇文章主要介紹了SpringBoot Mybatis如何配置多數(shù)據(jù)源并分包,文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2020-05-05