java排序算法圖文詳解
一、直接插入排序
基本思想：
將一個(gè)記錄插入到已排序的有序表中，使插入后的表仍然有序
對(duì)初始關(guān)鍵字{49 38 65 97 76 13 27 49}進(jìn)行直接插入排序
package Sort;
//插入排序
public class InsertSort {
public static void main(String[] args) {
int [] arr={49,38,65,97,76,13,27,49};
sort(arr);
print(arr);
}
private static void sort(int [] arr) {
for (int i = 1; i < arr.length; i++) {
for(int j=i;j>0;j--){
if(arr[j]<arr[j-1]){
swap(arr,j,j-1);
}
}
}
}
private static void swap(int [] arr,int i,int j){
int temp=0;
temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
private static void print(int [] arr) {
for (int i = 0; i <arr.length ; i++) {
System.out.print(arr[i]+" ");
}
}
}
13 27 38 49 49 65 76 97
Process finished with exit code 0
二、 希爾排序
希爾排序又稱“縮小增量排序”（Diminishing Increment Sort)）屬于插入排序類。
基本思想：
先將整個(gè)待排序的記錄分割成若干子序列分別進(jìn)行“直接插入排序”，待整個(gè)序列中的記錄”基本有序“時(shí)，再對(duì)全體記錄進(jìn)行一次直接插入排序。
package Sort;
//希爾排序是插入排序的改良
public class ShellSort {
public static void main(String[] args) {
int [] arr={16,25,12,30,47,11,23,36,9,18,31};
sort(arr);
print(arr);
}
private static void sort(int [] arr) {
//gap設(shè)置優(yōu)化
int h=1;
while(h<arr.length/3){
h=h*3+1;
}
for(int gap=h;gap>0;gap=(gap-1)/3) {//gap:希爾排序的間距
for (int i = gap; i < arr.length; i++) {
for (int j = i; j >gap-1; j-=gap) {
if (arr[j] < arr[j - gap]) {
swap(arr, j, j - gap);
}
}
}
}
}
private static void swap(int [] arr,int i,int j){
int temp=0;
temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
private static void print(int [] arr) {
for (int i = 0; i <arr.length ; i++) {
System.out.print(arr[i]+" ");
}
}
}
9 11 12 16 18 23 25 30 31 36 47
Process finished with exit code 0
三、冒泡排序
四、快速排序
對(duì)冒泡排序的一種改進(jìn)
基本思想：
通過一趟排序?qū)⒋判蛴涗浄指畛瑟?dú)立的兩部分，其中一部分的關(guān)鍵字均比另一部分的關(guān)鍵字小，則可分別對(duì)這兩部分記錄繼續(xù)分別進(jìn)行排序，以達(dá)到整個(gè)序列有序。
package Sort;
import java.util.Arrays;
//快速排序
public class QuickSort {
public static void main(String[] args) {
int[] arr={49,38,65,97,76,13,27,49};
sort(arr,0,arr.length-1);
System.out.println(Arrays.toString(arr));
}
private static void sort(int [] arr,int start,int end) {
if(start<end){
//把數(shù)組的第0個(gè)數(shù)作為標(biāo)準(zhǔn)數(shù)
int stared=arr[start];
//記錄要排序的下標(biāo)
int low=start;
int height=end;
//循環(huán)找出比標(biāo)準(zhǔn)數(shù)大和比標(biāo)準(zhǔn)數(shù)小的數(shù)
while(low<height){
//右邊數(shù)字比標(biāo)準(zhǔn)數(shù)大
while(low<height&&stared<=arr[height]){
height--;
}
//用右邊的數(shù)字替換左邊的數(shù)字
arr[low]=arr[height];
//左邊數(shù)字比標(biāo)準(zhǔn)數(shù)小
while(low<height&&stared>=arr[low]){
low++;
}
//用左邊的數(shù)字替換右邊的數(shù)字
arr[height]=arr[low];
}
arr[low]=stared;
sort(arr,start,low);
sort(arr,low+1,height);
}
}
}
[13, 27, 38, 49, 76, 97, 65, 49]
Process finished with exit code 0
五、選擇排序(Selection Sort)
六、堆排序
堆排序是利用堆這種數(shù)據(jù)結(jié)構(gòu)而設(shè)計(jì)的一種排序算法，堆排序是一種選擇排序，它的最壞，最好，平均時(shí)間復(fù)雜度均為O(nlogn)，它也是不穩(wěn)定排序。
堆是具有以下性質(zhì)的完全二叉樹：每個(gè)結(jié)點(diǎn)的值都大于或等于其左右孩子結(jié)點(diǎn)的值，稱為大頂堆, 注意 : 沒有要求結(jié)點(diǎn)的左孩子的值和右孩子的值的大小關(guān)系。
每個(gè)結(jié)點(diǎn)的值都小于或等于其左右孩子結(jié)點(diǎn)的值，稱為小頂堆
1、大頂堆舉例說明：
我們對(duì)堆中的結(jié)點(diǎn)按層進(jìn)行編號(hào)，映射到數(shù)組中就是下面這個(gè)樣子:
大頂堆特點(diǎn)：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2] // i 對(duì)應(yīng)第幾個(gè)節(jié)點(diǎn)，i從0開始編號(hào)
2、小頂堆舉例說明
小頂堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2] // i 對(duì)應(yīng)第幾個(gè)節(jié)點(diǎn)，i從0開始編號(hào)
一般升序采用大頂堆，降序采用小頂堆
堆排序基本思想
一、堆排序的基本思想是：
將待排序序列構(gòu)造成一個(gè)大頂堆
此時(shí)，整個(gè)序列的最大值就是堆頂?shù)母?jié)點(diǎn)。
將其與末尾元素進(jìn)行交換，此時(shí)末尾就為最大值。
然后將剩余n-1個(gè)元素重新構(gòu)造成一個(gè)堆，這樣會(huì)得到n個(gè)元素的次小值。如此反復(fù)執(zhí)行，便能得到一個(gè)有序序列了。
二、代碼示例
package Sort;
import java.util.Arrays;
/**構(gòu)造大頂堆
* 1、原順序二叉樹 非葉子節(jié)點(diǎn)在數(shù)組中的索引i=1時(shí)；arr[i]=6 i=0時(shí)
* 4 i的右節(jié)點(diǎn)值比它大，交換得 ： 9
* /\ 4 /\
* 6 8 /\ 6 8
* /\ 9 8 /\
* 5 9 /\ 5 4
* 5 6
*/
public class HeapSort {
public static void main(String[] args) {
int [] arr={4,6,8,5,9};
heapSort(arr);
}
//編寫一個(gè)堆排序的方法
public static void heapSort(int[] arr){
int temp=0;
for(int i=arr.length/2-1;i>=0;i--){
adjustHeap(arr,i,arr.length);
}
//將堆頂元素與末尾元素進(jìn)行交換，此時(shí)末尾就為最大值，將最大值全放在數(shù)組最后
//重新調(diào)整結(jié)構(gòu)，使其滿足堆定義，繼續(xù)交換堆頂元素與當(dāng)前末尾元素，反復(fù)執(zhí)行調(diào)整交換步驟，使整個(gè)序列達(dá)到有序
for(int j=arr.length-1;j>0;j--) {
//交換
temp = arr[j];
arr[j] = arr[0];
arr[0] = temp;
adjustHeap(arr, 0, j);
}
System.out.println("數(shù)組"+Arrays.toString(arr));
}
//將數(shù)組調(diào)整為一個(gè)大頂堆
/**
* 功能：完成將以i對(duì)應(yīng)的非葉子節(jié)點(diǎn)的樹調(diào)整成大頂堆
* 舉例：int[]arr={4,6,8,5,9};=>i=1=>adjustHeap=>得到{4，9，8，5，6}
* 如果再次調(diào)整adjustHeap傳入i=0,{4，9，8，5，6}=>得到{9，6，8，5，4}
* @param arr 表示要調(diào)整的數(shù)組
* @param i 表示非葉子節(jié)點(diǎn)在數(shù)組中的索引
* @param length 表示對(duì)多少個(gè)元素進(jìn)行調(diào)整，length在逐漸減少
*/
public static void adjustHeap(int[]arr,int i,int length){
int temp=arr[i];//先取出當(dāng)前元素的值，保存在臨時(shí)變量中
//開始調(diào)整
//k=i*2+1;k是i節(jié)點(diǎn)的左子節(jié)點(diǎn)
for(int k=i*2+1;k<length;k=k*2+1){
if(k+1<length&&arr[k]<arr[k+1]){//說明左子節(jié)點(diǎn)的值小于右子節(jié)點(diǎn)的值
k++;//k指向右子節(jié)點(diǎn)
}
if(arr[k]>temp){//如果子節(jié)點(diǎn)大于父節(jié)點(diǎn)
arr[i]=arr[k];//把較大的值賦給當(dāng)前節(jié)點(diǎn)
i=k;//!!!i指向k，繼續(xù)循環(huán)比較
}else{
break;
}
}
//當(dāng)for循環(huán)結(jié)束后，已經(jīng)將以i為父結(jié)點(diǎn)的最大值放在了堆頂上（局部）
arr[i]=temp;//將temp的值放在調(diào)整后的位置
}
}
堆排序結(jié)果：
數(shù)組[4, 5, 6, 8, 9]
七、歸并排序
定義：
又一類不同的排序方法，將兩個(gè)或兩個(gè)以上的有序表合并成一個(gè)新的有序表。
需要輔助空間：O(n)
整個(gè)歸并需要 [log2n] 趟
時(shí)間復(fù)雜度：O(nlog2n)
缺點(diǎn)：歸并排序占用附加存儲(chǔ)較多, 需要另外一個(gè)與原待排序?qū)ο髷?shù)組同樣大小的輔助數(shù)組。
優(yōu)點(diǎn)：歸并排序是一個(gè)穩(wěn)定的排序方法
思路可以推廣到“多路歸并”
常用于外部排序
package Sort;
//歸并排序
public class MergeSort {
public static void main(String[] args) {
int [] arr={4,5,7,8,1,2,3,6};
sort(arr);
print(arr);
}
private static void sort(int [] arr) {
int mid=arr.length/2;
int[]temp=new int[arr.length];
int i=0;//標(biāo)記左邊數(shù)組
int j=mid+1;//標(biāo)記右邊數(shù)組起始點(diǎn)
int k=0;
while(i<=mid&&j<arr.length){
if(arr[i]<=arr[j]){
temp[k]=arr[i];
i++;
k++;
}else{
temp[k]=arr[j];
j++;
k++;
}
}
while(i<=mid){temp[k++]=arr[i++];}//將左邊剩余的，復(fù)制到數(shù)組
while(j<arr.length){temp[k++]=arr[j++];}//將右邊剩余的，復(fù)制到數(shù)組
}
private static void print(int [] arr) {
for (int i = 0; i <arr.length ; i++) {
System.out.print(arr[i]+" ");
}
}
}
1 2 3 4 5 6 7 8
Process finished with exit code 0
總結(jié)
本篇文章就到這里了，希望可以給你帶來一些幫助，也希望您能夠多多關(guān)注腳本之家的更多內(nèi)容！
相關(guān)文章
Java 8 Lambda 表達(dá)式比較器使用示例代碼
這篇文章主要介紹了Java 8 Lambda 表達(dá)式比較器使用示例代碼，非常不錯(cuò)，具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2019-08-08
這篇文章主要為大家詳細(xì)介紹了Java中Stream流去除List重復(fù)元素的方法，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2022-03-03
這篇文章主要介紹了了解java中的session的相關(guān)問題，什么是session，session怎么用等，具有一定參考價(jià)值，需要的朋友可以了解下。2017-11-11
工廠類的目的是將對(duì)象的創(chuàng)建邏輯封裝在一個(gè)類中,以便客戶端代碼無需了解具體的實(shí)現(xiàn)細(xì)節(jié),本文主要介紹了MyBatis工廠類封裝與簡化實(shí)現(xiàn),具有一定的參考價(jià)值,感興趣的可以了解一下2024-01-01
Junit Mockito實(shí)現(xiàn)單元測(cè)試方法介紹
JUnit是用于編寫和運(yùn)行可重復(fù)的自動(dòng)化測(cè)試開源測(cè)試項(xiàng)目框架，這樣可以保證我們的代碼按與其工作。JUnit可廣泛用于工業(yè)和作為支架（從命令行）或IDE（如IDE）內(nèi)單獨(dú)的java程序2022-09-09
一篇文章帶你了解jdk1.8新特性--為什么使用lambda表達(dá)式
Lambda是一個(gè)匿名函數(shù)，我們可以把Lambda表達(dá)式理解為是一段可以傳遞的代碼，本篇文章就帶你了解，希望能給你帶來幫助2021-08-08
javaweb圖書商城設(shè)計(jì)之分類模塊(2)
這篇文章主要為大家詳細(xì)介紹了javaweb圖書商城設(shè)計(jì)之分類模塊的相關(guān)資料,具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2016-11-11
Elasticsearch?Recovery索引分片分配詳解
這篇文章主要為大家介紹了關(guān)于Elasticsearch的Recovery索引分片分配詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪<BR>2022-04-04
這篇文章主要介紹了idea日志亂碼和tomcat日志亂碼問題的解決方法,本文給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2020-08-08
JVM內(nèi)存管理之JAVA語言的內(nèi)存管理詳解
下面小編就為大家?guī)硪黄狫VM內(nèi)存管理之JAVA語言的內(nèi)存管理詳解。小編覺得挺不錯(cuò)的，現(xiàn)在就分享給大家，也給大家做個(gè)參考。一起跟隨小編過來看看吧2017-08-08