Java中常見(jiàn)的查找算法與排序算法總結(jié)
數(shù)據(jù)結(jié)構(gòu)是數(shù)據(jù)存儲(chǔ)的方式,算法是數(shù)據(jù)計(jì)算的方式。所以在開(kāi)發(fā)中,算法和數(shù)據(jù)結(jié)構(gòu)息息相關(guān)。今天的講義中會(huì)涉及部分?jǐn)?shù)據(jù)結(jié)構(gòu)的專業(yè)名詞,如果各位鐵粉有疑惑,可以先看一下哥們后面錄制的數(shù)據(jù)結(jié)構(gòu),再回頭看算法。
1. 基本查找
也叫做順序查找
說(shuō)明:順序查找適合于存儲(chǔ)結(jié)構(gòu)為數(shù)組或者鏈表。
基本思想:順序查找也稱為線形查找,屬于無(wú)序查找算法。從數(shù)據(jù)結(jié)構(gòu)線的一端開(kāi)始,順序掃描,依次將遍歷到的結(jié)點(diǎn)與要查找的值相比較,若相等則表示查找成功;若遍歷結(jié)束仍沒(méi)有找到相同的,表示查找失敗。
示例代碼:
public class A01_BasicSearchDemo1 { public static void main(String[] args) { //基本查找/順序查找 //核心: //從0索引開(kāi)始挨個(gè)往后查找 //需求:定義一個(gè)方法利用基本查找,查詢某個(gè)元素是否存在 //數(shù)據(jù)如下:{131, 127, 147, 81, 103, 23, 7, 79} int[] arr = {131, 127, 147, 81, 103, 23, 7, 79}; int number = 82; System.out.println(basicSearch(arr, number)); } //參數(shù): //一:數(shù)組 //二:要查找的元素 //返回值: //元素是否存在 public static boolean basicSearch(int[] arr, int number){ //利用基本查找來(lái)查找number在數(shù)組中是否存在 for (int i = 0; i < arr.length; i++) { if(arr[i] == number){ return true; } } return false; } }
2. 二分查找
也叫做折半查找
說(shuō)明:元素必須是有序的,從小到大,或者從大到小都是可以的。
如果是無(wú)序的,也可以先進(jìn)行排序。但是排序之后,會(huì)改變?cè)袛?shù)據(jù)的順序,查找出來(lái)元素位置跟原來(lái)的元素可能是不一樣的,所以排序之后再查找只能判斷當(dāng)前數(shù)據(jù)是否在容器當(dāng)中,返回的索引無(wú)實(shí)際的意義。
基本思想:也稱為是折半查找,屬于有序查找算法。用給定值先與中間結(jié)點(diǎn)比較。比較完之后有三種情況:
相等
說(shuō)明找到了
要查找的數(shù)據(jù)比中間節(jié)點(diǎn)小
說(shuō)明要查找的數(shù)字在中間節(jié)點(diǎn)左邊
要查找的數(shù)據(jù)比中間節(jié)點(diǎn)大
說(shuō)明要查找的數(shù)字在中間節(jié)點(diǎn)右邊
代碼示例:
package com.itheima.search; public class A02_BinarySearchDemo1 { public static void main(String[] args) { //二分查找/折半查找 //核心: //每次排除一半的查找范圍 //需求:定義一個(gè)方法利用二分查找,查詢某個(gè)元素在數(shù)組中的索引 //數(shù)據(jù)如下:{7, 23, 79, 81, 103, 127, 131, 147} int[] arr = {7, 23, 79, 81, 103, 127, 131, 147}; System.out.println(binarySearch(arr, 150)); } public static int binarySearch(int[] arr, int number){ //1.定義兩個(gè)變量記錄要查找的范圍 int min = 0; int max = arr.length - 1; //2.利用循環(huán)不斷的去找要查找的數(shù)據(jù) while(true){ if(min > max){ return -1; } //3.找到min和max的中間位置 int mid = (min + max) / 2; //4.拿著mid指向的元素跟要查找的元素進(jìn)行比較 if(arr[mid] > number){ //4.1 number在mid的左邊 //min不變,max = mid - 1; max = mid - 1; }else if(arr[mid] < number){ //4.2 number在mid的右邊 //max不變,min = mid + 1; min = mid + 1; }else{ //4.3 number跟mid指向的元素一樣 //找到了 return mid; } } } }
3. 插值查找
在介紹插值查找之前,先考慮一個(gè)問(wèn)題:
為什么二分查找算法一定要是折半,而不是折四分之一或者折更多呢?
其實(shí)就是因?yàn)榉奖悖?jiǎn)單,但是如果我能在二分查找的基礎(chǔ)上,讓中間的mid點(diǎn),盡可能靠近想要查找的元素,那不就能提高查找的效率了嗎?
二分查找中查找點(diǎn)計(jì)算如下:
mid=(low+high)/2, 即mid=low+1/2*(high-low);
我們可以將查找的點(diǎn)改進(jìn)為如下:
mid=low+(key-a[low])/(a[high]-a[low])*(high-low),
這樣,讓mid值的變化更靠近關(guān)鍵字key,這樣也就間接地減少了比較次數(shù)。
基本思想:基于二分查找算法,將查找點(diǎn)的選擇改進(jìn)為自適應(yīng)選擇,可以提高查找效率。當(dāng)然,差值查找也屬于有序查找。
細(xì)節(jié):對(duì)于表長(zhǎng)較大,而關(guān)鍵字分布又比較均勻的查找表來(lái)說(shuō),插值查找算法的平均性能比折半查找要好的多。反之,數(shù)組中如果分布非常不均勻,那么插值查找未必是很合適的選擇。
代碼跟二分查找類似,只要修改一下mid的計(jì)算方式即可。
4. 斐波那契查找
在介紹斐波那契查找算法之前,我們先介紹一下很它緊密相連并且大家都熟知的一個(gè)概念——黃金分割。
黃金比例又稱黃金分割,是指事物各部分間一定的數(shù)學(xué)比例關(guān)系,即將整體一分為二,較大部分與較小部分之比等于整體與較大部分之比,其比值約為1:0.618或1.618:1。
0.618被公認(rèn)為最具有審美意義的比例數(shù)字,這個(gè)數(shù)值的作用不僅僅體現(xiàn)在諸如繪畫、雕塑、音樂(lè)、建筑等藝術(shù)領(lǐng)域,而且在管理、工程設(shè)計(jì)等方面也有著不可忽視的作用。因此被稱為黃金分割。
在數(shù)學(xué)中有一個(gè)非常有名的數(shù)學(xué)規(guī)律:斐波那契數(shù)列:1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89…….
(從第三個(gè)數(shù)開(kāi)始,后邊每一個(gè)數(shù)都是前兩個(gè)數(shù)的和)。
然后我們會(huì)發(fā)現(xiàn),隨著斐波那契數(shù)列的遞增,前后兩個(gè)數(shù)的比值會(huì)越來(lái)越接近0.618,利用這個(gè)特性,我們就可以將黃金比例運(yùn)用到查找技術(shù)中。
基本思想:也是二分查找的一種提升算法,通過(guò)運(yùn)用黃金比例的概念在數(shù)列中選擇查找點(diǎn)進(jìn)行查找,提高查找效率。同樣地,斐波那契查找也屬于一種有序查找算法。
斐波那契查找也是在二分查找的基礎(chǔ)上進(jìn)行了優(yōu)化,優(yōu)化中間點(diǎn)mid的計(jì)算方式即可
代碼示例:
public class FeiBoSearchDemo { public static int maxSize = 20; public static void main(String[] args) { int[] arr = {1, 8, 10, 89, 1000, 1234}; System.out.println(search(arr, 1234)); } public static int[] getFeiBo() { int[] arr = new int[maxSize]; arr[0] = 1; arr[1] = 1; for (int i = 2; i < maxSize; i++) { arr[i] = arr[i - 1] + arr[i - 2]; } return arr; } public static int search(int[] arr, int key) { int low = 0; int high = arr.length - 1; //表示斐波那契數(shù)分割數(shù)的下標(biāo)值 int index = 0; int mid = 0; //調(diào)用斐波那契數(shù)列 int[] f = getFeiBo(); //獲取斐波那契分割數(shù)值的下標(biāo) while (high > (f[index] - 1)) { index++; } //因?yàn)閒[k]值可能大于a的長(zhǎng)度,因此需要使用Arrays工具類,構(gòu)造一個(gè)新法數(shù)組,并指向temp[],不足的部分會(huì)使用0補(bǔ)齊 int[] temp = Arrays.copyOf(arr, f[index]); //實(shí)際需要使用arr數(shù)組的最后一個(gè)數(shù)來(lái)填充不足的部分 for (int i = high + 1; i < temp.length; i++) { temp[i] = arr[high]; } //使用while循環(huán)處理,找到key值 while (low <= high) { mid = low + f[index - 1] - 1; if (key < temp[mid]) {//向數(shù)組的前面部分進(jìn)行查找 high = mid - 1; /* 對(duì)k--進(jìn)行理解 1.全部元素=前面的元素+后面的元素 2.f[k]=k[k-1]+f[k-2] 因?yàn)榍懊嬗衚-1個(gè)元素沒(méi)所以可以繼續(xù)分為f[k-1]=f[k-2]+f[k-3] 即在f[k-1]的前面繼續(xù)查找k-- 即下次循環(huán),mid=f[k-1-1]-1 */ index--; } else if (key > temp[mid]) {//向數(shù)組的后面的部分進(jìn)行查找 low = mid + 1; index -= 2; } else {//找到了 //需要確定返回的是哪個(gè)下標(biāo) if (mid <= high) { return mid; } else { return high; } } } return -1; } }
5. 分塊查找
當(dāng)數(shù)據(jù)表中的數(shù)據(jù)元素很多時(shí),可以采用分塊查找。
汲取了順序查找和折半查找各自的優(yōu)點(diǎn),既有動(dòng)態(tài)結(jié)構(gòu),又適于快速查找
分塊查找適用于數(shù)據(jù)較多,但是數(shù)據(jù)不會(huì)發(fā)生變化的情況,如果需要一邊添加一邊查找,建議使用哈希查找
分塊查找的過(guò)程:
- 需要把數(shù)據(jù)分成N多小塊,塊與塊之間不能有數(shù)據(jù)重復(fù)的交集。
- 給每一塊創(chuàng)建對(duì)象單獨(dú)存儲(chǔ)到數(shù)組當(dāng)中
- 查找數(shù)據(jù)的時(shí)候,先在數(shù)組查,當(dāng)前數(shù)據(jù)屬于哪一塊
- 再到這一塊中順序查找
代碼示例:
package com.itheima.search; public class A03_BlockSearchDemo { public static void main(String[] args) { /* 分塊查找 核心思想: 塊內(nèi)無(wú)序,塊間有序 實(shí)現(xiàn)步驟: 1.創(chuàng)建數(shù)組blockArr存放每一個(gè)塊對(duì)象的信息 2.先查找blockArr確定要查找的數(shù)據(jù)屬于哪一塊 3.再單獨(dú)遍歷這一塊數(shù)據(jù)即可 */ int[] arr = {16, 5, 9, 12,21, 18, 32, 23, 37, 26, 45, 34, 50, 48, 61, 52, 73, 66}; //創(chuàng)建三個(gè)塊的對(duì)象 Block b1 = new Block(21,0,5); Block b2 = new Block(45,6,11); Block b3 = new Block(73,12,17); //定義數(shù)組用來(lái)管理三個(gè)塊的對(duì)象(索引表) Block[] blockArr = {b1,b2,b3}; //定義一個(gè)變量用來(lái)記錄要查找的元素 int number = 37; //調(diào)用方法,傳遞索引表,數(shù)組,要查找的元素 int index = getIndex(blockArr,arr,number); //打印一下 System.out.println(index); } //利用分塊查找的原理,查詢number的索引 private static int getIndex(Block[] blockArr, int[] arr, int number) { //1.確定number是在那一塊當(dāng)中 int indexBlock = findIndexBlock(blockArr, number); if(indexBlock == -1){ //表示number不在數(shù)組當(dāng)中 return -1; } //2.獲取這一塊的起始索引和結(jié)束索引 --- 30 // Block b1 = new Block(21,0,5); ---- 0 // Block b2 = new Block(45,6,11); ---- 1 // Block b3 = new Block(73,12,17); ---- 2 int startIndex = blockArr[indexBlock].getStartIndex(); int endIndex = blockArr[indexBlock].getEndIndex(); //3.遍歷 for (int i = startIndex; i <= endIndex; i++) { if(arr[i] == number){ return i; } } return -1; } //定義一個(gè)方法,用來(lái)確定number在哪一塊當(dāng)中 public static int findIndexBlock(Block[] blockArr,int number){ //100 //從0索引開(kāi)始遍歷blockArr,如果number小于max,那么就表示number是在這一塊當(dāng)中的 for (int i = 0; i < blockArr.length; i++) { if(number <= blockArr[i].getMax()){ return i; } } return -1; } } class Block{ private int max;//最大值 private int startIndex;//起始索引 private int endIndex;//結(jié)束索引 public Block() { } public Block(int max, int startIndex, int endIndex) { this.max = max; this.startIndex = startIndex; this.endIndex = endIndex; } /** * 獲取 * @return max */ public int getMax() { return max; } /** * 設(shè)置 * @param max */ public void setMax(int max) { this.max = max; } /** * 獲取 * @return startIndex */ public int getStartIndex() { return startIndex; } /** * 設(shè)置 * @param startIndex */ public void setStartIndex(int startIndex) { this.startIndex = startIndex; } /** * 獲取 * @return endIndex */ public int getEndIndex() { return endIndex; } /** * 設(shè)置 * @param endIndex */ public void setEndIndex(int endIndex) { this.endIndex = endIndex; } public String toString() { return "Block{max = " + max + ", startIndex = " + startIndex + ", endIndex = " + endIndex + "}"; } }
6. 哈希查找
哈希查找是分塊查找的進(jìn)階版,適用于數(shù)據(jù)一邊添加一邊查找的情況。
一般是數(shù)組 + 鏈表的結(jié)合體或者是數(shù)組+鏈表 + 紅黑樹(shù)的結(jié)合體
在課程中,為了讓大家方便理解,所以規(guī)定:
- 數(shù)組的0索引處存儲(chǔ)1~100
- 數(shù)組的1索引處存儲(chǔ)101~200
- 數(shù)組的2索引處存儲(chǔ)201~300
- 以此類推
但是實(shí)際上,我們一般不會(huì)采取這種方式,因?yàn)檫@種方式容易導(dǎo)致一塊區(qū)域添加的元素過(guò)多,導(dǎo)致效率偏低。
更多的是先計(jì)算出當(dāng)前數(shù)據(jù)的哈希值,用哈希值跟數(shù)組的長(zhǎng)度進(jìn)行計(jì)算,計(jì)算出應(yīng)存入的位置,再掛在數(shù)組的后面形成鏈表,如果掛的元素太多而且數(shù)組長(zhǎng)度過(guò)長(zhǎng),我們也會(huì)把鏈表轉(zhuǎn)化為紅黑樹(shù),進(jìn)一步提高效率。
具體的過(guò)程,大家可以參見(jiàn)B站阿瑋講解課程:從入門到起飛。在集合章節(jié)詳細(xì)講解了哈希表的數(shù)據(jù)結(jié)構(gòu)。全程采取動(dòng)畫形式講解,讓大家一目了然。
在此不多做闡述。
7. 樹(shù)表查找
本知識(shí)點(diǎn)涉及到數(shù)據(jù)結(jié)構(gòu):樹(shù)。
建議先看一下后面阿瑋講解的數(shù)據(jù)結(jié)構(gòu),再回頭理解。
基本思想:二叉查找樹(shù)是先對(duì)待查找的數(shù)據(jù)進(jìn)行生成樹(shù),確保樹(shù)的左分支的值小于右分支的值,然后在就行和每個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)比較大小,查找最適合的范圍。 這個(gè)算法的查找效率很高,但是如果使用這種查找方法要首先創(chuàng)建樹(shù)。
二叉查找樹(shù)(BinarySearch Tree,也叫二叉搜索樹(shù),或稱二叉排序樹(shù)Binary Sort Tree),具有下列性質(zhì)的二叉樹(shù):
1)若任意節(jié)點(diǎn)左子樹(shù)上所有的數(shù)據(jù),均小于本身;
2)若任意節(jié)點(diǎn)右子樹(shù)上所有的數(shù)據(jù),均大于本身;
二叉查找樹(shù)性質(zhì):對(duì)二叉查找樹(shù)進(jìn)行中序遍歷,即可得到有序的數(shù)列。
不同形態(tài)的二叉查找樹(shù)如下圖所示:
基于二叉查找樹(shù)進(jìn)行優(yōu)化,進(jìn)而可以得到其他的樹(shù)表查找算法,如平衡樹(shù)、紅黑樹(shù)等高效算法。
具體細(xì)節(jié)大家可以參見(jiàn)B站阿瑋講解課程:從入門到起飛。在集合章節(jié)詳細(xì)講解了樹(shù)數(shù)據(jù)結(jié)構(gòu)。全程采取動(dòng)畫形式講解,讓大家一目了然。
在此不多做闡述。
不管是二叉查找樹(shù),還是平衡二叉樹(shù),還是紅黑樹(shù),查找的性能都比較高
十大排序算法
1. 冒泡排序
冒泡排序(Bubble Sort)也是一種簡(jiǎn)單直觀的排序算法。
它重復(fù)的遍歷過(guò)要排序的數(shù)列,一次比較相鄰的兩個(gè)元素,如果他們的順序錯(cuò)誤就把他們交換過(guò)來(lái)。
這個(gè)算法的名字由來(lái)是因?yàn)樵酱蟮脑貢?huì)經(jīng)由交換慢慢"浮"到最后面。
當(dāng)然,大家可以按照從大到小的方式進(jìn)行排列。
1.1 算法步驟
- 相鄰的元素兩兩比較,大的放右邊,小的放左邊
- 第一輪比較完畢之后,最大值就已經(jīng)確定,第二輪可以少循環(huán)一次,后面以此類推
- 如果數(shù)組中有n個(gè)數(shù)據(jù),總共我們只要執(zhí)行n-1輪的代碼就可以
1.2 動(dòng)圖演示
1.3 代碼示例
public class A01_BubbleDemo { public static void main(String[] args) { /* 冒泡排序: 核心思想: 1,相鄰的元素兩兩比較,大的放右邊,小的放左邊。 2,第一輪比較完畢之后,最大值就已經(jīng)確定,第二輪可以少循環(huán)一次,后面以此類推。 3,如果數(shù)組中有n個(gè)數(shù)據(jù),總共我們只要執(zhí)行n-1輪的代碼就可以。 */ //1.定義數(shù)組 int[] arr = {2, 4, 5, 3, 1}; //2.利用冒泡排序?qū)?shù)組中的數(shù)據(jù)變成 1 2 3 4 5 //外循環(huán):表示我要執(zhí)行多少輪。 如果有n個(gè)數(shù)據(jù),那么執(zhí)行n - 1 輪 for (int i = 0; i < arr.length - 1; i++) { //內(nèi)循環(huán):每一輪中我如何比較數(shù)據(jù)并找到當(dāng)前的最大值 //-1:為了防止索引越界 //-i:提高效率,每一輪執(zhí)行的次數(shù)應(yīng)該比上一輪少一次。 for (int j = 0; j < arr.length - 1 - i; j++) { //i 依次表示數(shù)組中的每一個(gè)索引:0 1 2 3 4 if(arr[j] > arr[j + 1]){ int temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } } printArr(arr); } private static void printArr(int[] arr) { //3.遍歷數(shù)組 for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } System.out.println(); } }
2. 選擇排序
2.1 算法步驟
- 從0索引開(kāi)始,跟后面的元素一一比較
- 小的放前面,大的放后面
- 第一次循環(huán)結(jié)束后,最小的數(shù)據(jù)已經(jīng)確定
- 第二次循環(huán)從1索引開(kāi)始以此類推
- 第三輪循環(huán)從2索引開(kāi)始以此類推
- 第四輪循環(huán)從3索引開(kāi)始以此類推。
2.2 動(dòng)圖演示
public class A02_SelectionDemo { public static void main(String[] args) { /* 選擇排序: 1,從0索引開(kāi)始,跟后面的元素一一比較。 2,小的放前面,大的放后面。 3,第一次循環(huán)結(jié)束后,最小的數(shù)據(jù)已經(jīng)確定。 4,第二次循環(huán)從1索引開(kāi)始以此類推。 */ //1.定義數(shù)組 int[] arr = {2, 4, 5, 3, 1}; //2.利用選擇排序讓數(shù)組變成 1 2 3 4 5 /* //第一輪: //從0索引開(kāi)始,跟后面的元素一一比較。 for (int i = 0 + 1; i < arr.length; i++) { //拿著0索引跟后面的數(shù)據(jù)進(jìn)行比較 if(arr[0] > arr[i]){ int temp = arr[0]; arr[0] = arr[i]; arr[i] = temp; } }*/ //最終代碼: //外循環(huán):幾輪 //i:表示這一輪中,我拿著哪個(gè)索引上的數(shù)據(jù)跟后面的數(shù)據(jù)進(jìn)行比較并交換 for (int i = 0; i < arr.length -1; i++) { //內(nèi)循環(huán):每一輪我要干什么事情? //拿著i跟i后面的數(shù)據(jù)進(jìn)行比較交換 for (int j = i + 1; j < arr.length; j++) { if(arr[i] > arr[j]){ int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } } } printArr(arr); } private static void printArr(int[] arr) { //3.遍歷數(shù)組 for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } System.out.println(); } }
3. 插入排序
插入排序的代碼實(shí)現(xiàn)雖然沒(méi)有冒泡排序和選擇排序那么簡(jiǎn)單粗暴,但它的原理應(yīng)該是最容易理解的了,因?yàn)橹灰蜻^(guò)撲克牌的人都應(yīng)該能夠秒懂。插入排序是一種最簡(jiǎn)單直觀的排序算法,它的工作原理是通過(guò)創(chuàng)建有序序列和無(wú)序序列,然后再遍歷無(wú)序序列得到里面每一個(gè)數(shù)字,把每一個(gè)數(shù)字插入到有序序列中正確的位置。
插入排序在插入的時(shí)候,有優(yōu)化算法,在遍歷有序序列找正確位置時(shí),可以采取二分查找
3.1 算法步驟
將0索引的元素到N索引的元素看做是有序的,把N+1索引的元素到最后一個(gè)當(dāng)成是無(wú)序的。
遍歷無(wú)序的數(shù)據(jù),將遍歷到的元素插入有序序列中適當(dāng)?shù)奈恢茫缬龅较嗤瑪?shù)據(jù),插在后面。
N的范圍:0~最大索引
3.2 動(dòng)圖演示
package com.itheima.mysort; public class A03_InsertDemo { public static void main(String[] args) { /* 插入排序: 將0索引的元素到N索引的元素看做是有序的,把N+1索引的元素到最后一個(gè)當(dāng)成是無(wú)序的。 遍歷無(wú)序的數(shù)據(jù),將遍歷到的元素插入有序序列中適當(dāng)?shù)奈恢茫缬龅较嗤瑪?shù)據(jù),插在后面。 N的范圍:0~最大索引 */ int[] arr = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48}; //1.找到無(wú)序的哪一組數(shù)組是從哪個(gè)索引開(kāi)始的。 2 int startIndex = -1; for (int i = 0; i < arr.length; i++) { if(arr[i] > arr[i + 1]){ startIndex = i + 1; break; } } //2.遍歷從startIndex開(kāi)始到最后一個(gè)元素,依次得到無(wú)序的哪一組數(shù)據(jù)中的每一個(gè)元素 for (int i = startIndex; i < arr.length; i++) { //問(wèn)題:如何把遍歷到的數(shù)據(jù),插入到前面有序的這一組當(dāng)中 //記錄當(dāng)前要插入數(shù)據(jù)的索引 int j = i; while(j > 0 && arr[j] < arr[j - 1]){ //交換位置 int temp = arr[j]; arr[j] = arr[j - 1]; arr[j - 1] = temp; j--; } } printArr(arr); } private static void printArr(int[] arr) { //3.遍歷數(shù)組 for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } System.out.println(); } }
4. 快速排序
快速排序是由東尼·霍爾所發(fā)展的一種排序算法。
快速排序又是一種分而治之思想在排序算法上的典型應(yīng)用。
快速排序的名字起的是簡(jiǎn)單粗暴,因?yàn)橐宦?tīng)到這個(gè)名字你就知道它存在的意義,就是快,而且效率高!
它是處理大數(shù)據(jù)最快的排序算法之一了。
4.1 算法步驟
- 從數(shù)列中挑出一個(gè)元素,一般都是左邊第一個(gè)數(shù)字,稱為 "基準(zhǔn)數(shù)";
- 創(chuàng)建兩個(gè)指針,一個(gè)從前往后走,一個(gè)從后往前走。
- 先執(zhí)行后面的指針,找出第一個(gè)比基準(zhǔn)數(shù)小的數(shù)字
- 再執(zhí)行前面的指針,找出第一個(gè)比基準(zhǔn)數(shù)大的數(shù)字
- 交換兩個(gè)指針指向的數(shù)字
- 直到兩個(gè)指針相遇
- 將基準(zhǔn)數(shù)跟指針指向位置的數(shù)字交換位置,稱之為:基準(zhǔn)數(shù)歸位。
- 第一輪結(jié)束之后,基準(zhǔn)數(shù)左邊的數(shù)字都是比基準(zhǔn)數(shù)小的,基準(zhǔn)數(shù)右邊的數(shù)字都是比基準(zhǔn)數(shù)大的。
- 把基準(zhǔn)數(shù)左邊看做一個(gè)序列,把基準(zhǔn)數(shù)右邊看做一個(gè)序列,按照剛剛的規(guī)則遞歸排序
4.2 動(dòng)圖演示
package com.itheima.mysort; import java.util.Arrays; public class A05_QuickSortDemo { public static void main(String[] args) { System.out.println(Integer.MAX_VALUE); System.out.println(Integer.MIN_VALUE); /* 快速排序: 第一輪:以0索引的數(shù)字為基準(zhǔn)數(shù),確定基準(zhǔn)數(shù)在數(shù)組中正確的位置。 比基準(zhǔn)數(shù)小的全部在左邊,比基準(zhǔn)數(shù)大的全部在右邊。 后面以此類推。 */ int[] arr = {1,1, 6, 2, 7, 9, 3, 4, 5, 1,10, 8}; //int[] arr = new int[1000000]; /* Random r = new Random(); for (int i = 0; i < arr.length; i++) { arr[i] = r.nextInt(); }*/
以上就是Java中常見(jiàn)的查找算法與排序算法總結(jié)的詳細(xì)內(nèi)容,更多關(guān)于Java查找 排序算法的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章!
相關(guān)文章
java線程之用Thread類創(chuàng)建線程的方法
本篇文章介紹了,Thread類創(chuàng)建線程的方法。需要的朋友參考下2013-05-05java 進(jìn)制轉(zhuǎn)換實(shí)例詳解
這篇文章主要介紹了java 進(jìn)制轉(zhuǎn)換實(shí)例詳解的相關(guān)資料,需要的朋友可以參考下2017-04-04SpringCloud Gateway HttpWebHandlerAdapter鏈路調(diào)用請(qǐng)求流程介
Spring Cloud Gateway旨在為微服務(wù)架構(gòu)提供一種簡(jiǎn)單有效的、統(tǒng)一的 API 路由管理方式。Spring Cloud Gateway 作為 Spring Cloud 生態(tài)系中的網(wǎng)關(guān),它不僅提供統(tǒng)一的路由方式,并且基于 Filter 鏈的方式提供了網(wǎng)關(guān)基本的功能,例如:安全、監(jiān)控/埋點(diǎn)和限流等2022-10-10java 中Executor, ExecutorService 和 Executors 間的不同
這篇文章主要介紹了java 中Executor, ExecutorService 和 Executors 間的不同的相關(guān)資料,需要的朋友可以參考下2017-06-06Java實(shí)現(xiàn)在不同線程中運(yùn)行的代碼實(shí)例
這篇文章主要介紹了Java實(shí)現(xiàn)在不同線程中運(yùn)行的代碼,結(jié)合具體實(shí)例形式分析了java多線程操作的相關(guān)實(shí)現(xiàn)技巧,需要的朋友可以參考下2017-04-04