溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
這篇文章主要介紹了Java中常見的查找算法與排序算法怎么使用的相關知識，內容詳細易懂，操作簡單快捷，具有一定借鑒價值，相信大家閱讀完這篇Java中常見的查找算法與排序算法怎么使用文章都會有所收獲，下面我們一起來看看吧。
也叫做順序查找
說明：順序查找適合于存儲結構為數組或者鏈表。
基本思想：順序查找也稱為線形查找，屬于無序查找算法。從數據結構線的一端開始，順序掃描，依次將遍歷到的結點與要查找的值相比較，若相等則表示查找成功；若遍歷結束仍沒有找到相同的，表示查找失敗。
示例代碼：
public class A01_BasicSearchDemo1 {
public static void main(String[] args) {
//基本查找/順序查找
//核心：
//從0索引開始挨個往后查找
//需求：定義一個方法利用基本查找，查詢某個元素是否存在
//數據如下：{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));
}
//參數：
//一：數組
//二：要查找的元素
//返回值：
//元素是否存在
public static boolean basicSearch(int[] arr, int number){
//利用基本查找來查找number在數組中是否存在
for (int i = 0; i < arr.length; i++) {
if(arr[i] == number){
return true;
}
}
return false;
}
}也叫做折半查找
說明：元素必須是有序的，從小到大，或者從大到小都是可以的。
如果是無序的，也可以先進行排序。但是排序之后，會改變原有數據的順序，查找出來元素位置跟原來的元素可能是不一樣的，所以排序之后再查找只能判斷當前數據是否在容器當中，返回的索引無實際的意義。
基本思想：也稱為是折半查找，屬于有序查找算法。用給定值先與中間結點比較。比較完之后有三種情況：
相等
說明找到了
要查找的數據比中間節點小
說明要查找的數字在中間節點左邊
要查找的數據比中間節點大
說明要查找的數字在中間節點右邊
代碼示例：
package com.itheima.search;
public class A02_BinarySearchDemo1 {
public static void main(String[] args) {
//二分查找/折半查找
//核心：
//每次排除一半的查找范圍
//需求：定義一個方法利用二分查找，查詢某個元素在數組中的索引
//數據如下：{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.定義兩個變量記錄要查找的范圍
int min = 0;
int max = arr.length - 1;
//2.利用循環不斷的去找要查找的數據
while(true){
if(min > max){
return -1;
}
//3.找到min和max的中間位置
int mid = (min + max) / 2;
//4.拿著mid指向的元素跟要查找的元素進行比較
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;
}
}
}
}在介紹插值查找之前，先考慮一個問題：
為什么二分查找算法一定要是折半，而不是折四分之一或者折更多呢？
其實就是因為方便，簡單，但是如果我能在二分查找的基礎上，讓中間的mid點，盡可能靠近想要查找的元素，那不就能提高查找的效率了嗎？
二分查找中查找點計算如下：
mid=(low+high)/2, 即mid=low+1/2*(high-low);
我們可以將查找的點改進為如下：
mid=low+(key-a[low])/(a[high]-a[low])*(high-low)，
這樣，讓mid值的變化更靠近關鍵字key，這樣也就間接地減少了比較次數。
基本思想：基于二分查找算法，將查找點的選擇改進為自適應選擇，可以提高查找效率。當然，差值查找也屬于有序查找。
細節：對于表長較大，而關鍵字分布又比較均勻的查找表來說，插值查找算法的平均性能比折半查找要好的多。反之，數組中如果分布非常不均勻，那么插值查找未必是很合適的選擇。
代碼跟二分查找類似，只要修改一下mid的計算方式即可。
在介紹斐波那契查找算法之前，我們先介紹一下很它緊密相連并且大家都熟知的一個概念——黃金分割。
黃金比例又稱黃金分割，是指事物各部分間一定的數學比例關系，即將整體一分為二，較大部分與較小部分之比等于整體與較大部分之比，其比值約為1:0.618或1.618:1。
0.618被公認為最具有審美意義的比例數字，這個數值的作用不僅僅體現在諸如繪畫、雕塑、音樂、建筑等藝術領域，而且在管理、工程設計等方面也有著不可忽視的作用。因此被稱為黃金分割。
在數學中有一個非常有名的數學規律：斐波那契數列：1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89…….
（從第三個數開始，后邊每一個數都是前兩個數的和）。
然后我們會發現，隨著斐波那契數列的遞增，前后兩個數的比值會越來越接近0.618，利用這個特性，我們就可以將黃金比例運用到查找技術中。
基本思想：也是二分查找的一種提升算法，通過運用黃金比例的概念在數列中選擇查找點進行查找，提高查找效率。同樣地，斐波那契查找也屬于一種有序查找算法。
斐波那契查找也是在二分查找的基礎上進行了優化，優化中間點mid的計算方式即可
代碼示例：
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;
//表示斐波那契數分割數的下標值
int index = 0;
int mid = 0;
//調用斐波那契數列
int[] f = getFeiBo();
//獲取斐波那契分割數值的下標
while (high > (f[index] - 1)) {
index++;
}
//因為f[k]值可能大于a的長度，因此需要使用Arrays工具類，構造一個新法數組，并指向temp[],不足的部分會使用0補齊
int[] temp = Arrays.copyOf(arr, f[index]);
//實際需要使用arr數組的最后一個數來填充不足的部分
for (int i = high + 1; i < temp.length; i++) {
temp[i] = arr[high];
}
//使用while循環處理，找到key值
while (low <= high) {
mid = low + f[index - 1] - 1;
if (key < temp[mid]) {//向數組的前面部分進行查找
high = mid - 1;
/*
對k--進行理解
1.全部元素=前面的元素+后面的元素
2.f[k]=k[k-1]+f[k-2]
因為前面有k-1個元素沒所以可以繼續分為f[k-1]=f[k-2]+f[k-3]
即在f[k-1]的前面繼續查找k--
即下次循環,mid=f[k-1-1]-1
*/
index--;
} else if (key > temp[mid]) {//向數組的后面的部分進行查找
low = mid + 1;
index -= 2;
} else {//找到了
//需要確定返回的是哪個下標
if (mid <= high) {
return mid;
} else {
return high;
}
}
}
return -1;
}
}當數據表中的數據元素很多時，可以采用分塊查找。
汲取了順序查找和折半查找各自的優點，既有動態結構，又適于快速查找
分塊查找適用于數據較多，但是數據不會發生變化的情況，如果需要一邊添加一邊查找，建議使用哈希查找
分塊查找的過程：
需要把數據分成N多小塊，塊與塊之間不能有數據重復的交集。
給每一塊創建對象單獨存儲到數組當中
查找數據的時候，先在數組查，當前數據屬于哪一塊
再到這一塊中順序查找
代碼示例：
package com.itheima.search;
public class A03_BlockSearchDemo {
public static void main(String[] args) {
/*
分塊查找
核心思想：
塊內無序，塊間有序
實現步驟：
1.創建數組blockArr存放每一個塊對象的信息
2.先查找blockArr確定要查找的數據屬于哪一塊
3.再單獨遍歷這一塊數據即可
*/
int[] arr = {16, 5, 9, 12,21, 18,
32, 23, 37, 26, 45, 34,
50, 48, 61, 52, 73, 66};
//創建三個塊的對象
Block b1 = new Block(21,0,5);
Block b2 = new Block(45,6,11);
Block b3 = new Block(73,12,17);
//定義數組用來管理三個塊的對象（索引表）
Block[] blockArr = {b1,b2,b3};
//定義一個變量用來記錄要查找的元素
int number = 37;
//調用方法，傳遞索引表，數組，要查找的元素
int index = getIndex(blockArr,arr,number);
//打印一下
System.out.println(index);
}
//利用分塊查找的原理，查詢number的索引
private static int getIndex(Block[] blockArr, int[] arr, int number) {
//1.確定number是在那一塊當中
int indexBlock = findIndexBlock(blockArr, number);
if(indexBlock == -1){
//表示number不在數組當中
return -1;
}
//2.獲取這一塊的起始索引和結束索引 --- 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;
}
//定義一個方法，用來確定number在哪一塊當中
public static int findIndexBlock(Block[] blockArr,int number){ //100
//從0索引開始遍歷blockArr，如果number小于max，那么就表示number是在這一塊當中的
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;//結束索引
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;
}
/**
* 設置
* @param max
*/
public void setMax(int max) {
this.max = max;
}
/**
* 獲取
* @return startIndex
*/
public int getStartIndex() {
return startIndex;
}
/**
* 設置
* @param startIndex
*/
public void setStartIndex(int startIndex) {
this.startIndex = startIndex;
}
/**
* 獲取
* @return endIndex
*/
public int getEndIndex() {
return endIndex;
}
/**
* 設置
* @param endIndex
*/
public void setEndIndex(int endIndex) {
this.endIndex = endIndex;
}
public String toString() {
return "Block{max = " + max + ", startIndex = " + startIndex + ", endIndex = " + endIndex + "}";
}
}哈希查找是分塊查找的進階版，適用于數據一邊添加一邊查找的情況。
一般是數組 + 鏈表的結合體或者是數組+鏈表 + 紅黑樹的結合體
在課程中，為了讓大家方便理解，所以規定：
數組的0索引處存儲1~100
數組的1索引處存儲101~200
數組的2索引處存儲201~300
以此類推
但是實際上，我們一般不會采取這種方式，因為這種方式容易導致一塊區域添加的元素過多，導致效率偏低。
更多的是先計算出當前數據的哈希值，用哈希值跟數組的長度進行計算，計算出應存入的位置，再掛在數組的后面形成鏈表，如果掛的元素太多而且數組長度過長，我們也會把鏈表轉化為紅黑樹，進一步提高效率。
具體的過程，大家可以參見B站阿瑋講解課程：從入門到起飛。在集合章節詳細講解了哈希表的數據結構。全程采取動畫形式講解，讓大家一目了然。
在此不多做闡述。
本知識點涉及到數據結構：樹。
建議先看一下后面阿瑋講解的數據結構，再回頭理解。
基本思想：二叉查找樹是先對待查找的數據進行生成樹，確保樹的左分支的值小于右分支的值，然后在就行和每個節點的父節點比較大小，查找最適合的范圍。 這個算法的查找效率很高，但是如果使用這種查找方法要首先創建樹。
二叉查找樹（BinarySearch Tree，也叫二叉搜索樹，或稱二叉排序樹Binary Sort Tree），具有下列性質的二叉樹：
1）若任意節點左子樹上所有的數據，均小于本身；
2）若任意節點右子樹上所有的數據，均大于本身；
二叉查找樹性質：對二叉查找樹進行中序遍歷，即可得到有序的數列。
不同形態的二叉查找樹如下圖所示：
基于二叉查找樹進行優化，進而可以得到其他的樹表查找算法，如平衡樹、紅黑樹等高效算法。
具體細節大家可以參見B站阿瑋講解課程：從入門到起飛。在集合章節詳細講解了樹數據結構。全程采取動畫形式講解，讓大家一目了然。
在此不多做闡述。
不管是二叉查找樹，還是平衡二叉樹，還是紅黑樹，查找的性能都比較高
冒泡排序（Bubble Sort）也是一種簡單直觀的排序算法。
它重復的遍歷過要排序的數列，一次比較相鄰的兩個元素，如果他們的順序錯誤就把他們交換過來。
這個算法的名字由來是因為越大的元素會經由交換慢慢"浮"到最后面。
當然，大家可以按照從大到小的方式進行排列。
1.1 算法步驟
相鄰的元素兩兩比較，大的放右邊，小的放左邊
第一輪比較完畢之后，最大值就已經確定，第二輪可以少循環一次，后面以此類推
如果數組中有n個數據，總共我們只要執行n-1輪的代碼就可以
1.2 動圖演示
1.3 代碼示例
public class A01_BubbleDemo {
public static void main(String[] args) {
/*
冒泡排序：
核心思想：
1，相鄰的元素兩兩比較，大的放右邊，小的放左邊。
2，第一輪比較完畢之后，最大值就已經確定，第二輪可以少循環一次，后面以此類推。
3，如果數組中有n個數據，總共我們只要執行n-1輪的代碼就可以。
*/
//1.定義數組
int[] arr = {2, 4, 5, 3, 1};
//2.利用冒泡排序將數組中的數據變成 1 2 3 4 5
//外循環：表示我要執行多少輪。 如果有n個數據，那么執行n - 1 輪
for (int i = 0; i < arr.length - 1; i++) {
//內循環：每一輪中我如何比較數據并找到當前的最大值
//-1：為了防止索引越界
//-i：提高效率，每一輪執行的次數應該比上一輪少一次。
for (int j = 0; j < arr.length - 1 - i; j++) {
//i 依次表示數組中的每一個索引：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.遍歷數組
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
}2.1 算法步驟
從0索引開始，跟后面的元素一一比較
小的放前面，大的放后面
第一次循環結束后，最小的數據已經確定
第二次循環從1索引開始以此類推
第三輪循環從2索引開始以此類推
第四輪循環從3索引開始以此類推。
2.2 動圖演示
public class A02_SelectionDemo {
public static void main(String[] args) {
/*
選擇排序：
1，從0索引開始，跟后面的元素一一比較。
2，小的放前面，大的放后面。
3，第一次循環結束后，最小的數據已經確定。
4，第二次循環從1索引開始以此類推。
*/
//1.定義數組
int[] arr = {2, 4, 5, 3, 1};
//2.利用選擇排序讓數組變成 1 2 3 4 5
/* //第一輪：
//從0索引開始，跟后面的元素一一比較。
for (int i = 0 + 1; i < arr.length; i++) {
//拿著0索引跟后面的數據進行比較
if(arr[0] > arr[i]){
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
}
}*/
//最終代碼：
//外循環：幾輪
//i:表示這一輪中，我拿著哪個索引上的數據跟后面的數據進行比較并交換
for (int i = 0; i < arr.length -1; i++) {
//內循環：每一輪我要干什么事情？
//拿著i跟i后面的數據進行比較交換
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.遍歷數組
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
}插入排序的代碼實現雖然沒有冒泡排序和選擇排序那么簡單粗暴，但它的原理應該是最容易理解的了，因為只要打過撲克牌的人都應該能夠秒懂。插入排序是一種最簡單直觀的排序算法，它的工作原理是通過創建有序序列和無序序列，然后再遍歷無序序列得到里面每一個數字，把每一個數字插入到有序序列中正確的位置。
插入排序在插入的時候，有優化算法，在遍歷有序序列找正確位置時，可以采取二分查找
3.1 算法步驟
將0索引的元素到N索引的元素看做是有序的，把N+1索引的元素到最后一個當成是無序的。
遍歷無序的數據，將遍歷到的元素插入有序序列中適當的位置，如遇到相同數據，插在后面。
N的范圍：0~最大索引
3.2 動圖演示
package com.itheima.mysort;
public class A03_InsertDemo {
public static void main(String[] args) {
/*
插入排序：
將0索引的元素到N索引的元素看做是有序的，把N+1索引的元素到最后一個當成是無序的。
遍歷無序的數據，將遍歷到的元素插入有序序列中適當的位置，如遇到相同數據，插在后面。
N的范圍：0~最大索引
*/
int[] arr = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};
//1.找到無序的哪一組數組是從哪個索引開始的。 2
int startIndex = -1;
for (int i = 0; i < arr.length; i++) {
if(arr[i] > arr[i + 1]){
startIndex = i + 1;
break;
}
}
//2.遍歷從startIndex開始到最后一個元素，依次得到無序的哪一組數據中的每一個元素
for (int i = startIndex; i < arr.length; i++) {
//問題：如何把遍歷到的數據，插入到前面有序的這一組當中
//記錄當前要插入數據的索引
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.遍歷數組
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
}快速排序是由東尼·霍爾所發展的一種排序算法。
快速排序又是一種分而治之思想在排序算法上的典型應用。
快速排序的名字起的是簡單粗暴，因為一聽到這個名字你就知道它存在的意義，就是快，而且效率高！
它是處理大數據最快的排序算法之一了。
4.1 算法步驟
從數列中挑出一個元素，一般都是左邊第一個數字，稱為 "基準數";
創建兩個指針，一個從前往后走，一個從后往前走。
先執行后面的指針，找出第一個比基準數小的數字
再執行前面的指針，找出第一個比基準數大的數字
交換兩個指針指向的數字
直到兩個指針相遇
將基準數跟指針指向位置的數字交換位置，稱之為：基準數歸位。
第一輪結束之后，基準數左邊的數字都是比基準數小的，基準數右邊的數字都是比基準數大的。
把基準數左邊看做一個序列，把基準數右邊看做一個序列，按照剛剛的規則遞歸排序
4.2 動圖演示
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索引的數字為基準數，確定基準數在數組中正確的位置。
比基準數小的全部在左邊，比基準數大的全部在右邊。
后面以此類推。
*/
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中常見的查找算法與排序算法怎么使用”這篇文章的內容就介紹到這里，感謝各位的閱讀！相信大家對“Java中常見的查找算法與排序算法怎么使用”知識都有一定的了解，大家如果還想學習更多知識，歡迎關注億速云行業資訊頻道。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
