Java的查找算法和排序算法

一、查找算法

1. 基本查找

• 基本查找也叫顺序查找。
  
• 核心：从0索引开始挨个往后查找。
  

a. 示例

• 需求：界说一个方法，查询元素在数组中的索引值。
  

1. import java.util.ArrayList;
3. public class Demo2 {
4.     public static void main(String[] args) {
5.         int[] arr = {131, 127, 147, 81, 103, 23, 7, 79, 81};
6.         System.out.println(searchNumber(arr, 81));
7.     }
8.     public static ArrayList<Integer> searchNumber(int[] arr, int number){
9.         ArrayList<Integer> list = new ArrayList<>();
10.         for (int i = 0; i < arr.length; i++) {
11.             if (arr[i] == number) {
12.                 list.add(i);
13.             }
14.         }
15.         return list;
16.     }
17. }

复制代码

2. 二分查找

• 二分查找又称折半查找。
  
• 前提条件：数组中的数据必须是有序的。
  
  
  
  • 如果数据是乱的，必须先排序。
    
  • 只能确定当前key在数组中是否存在，不能确定其索引值。
    
  
  
• 核心：每次清除一半的查找范围。
  
• 过程：
  
  
  
  • 界说min和max表示当前要查找的范围
    
  • 界说中心索引mid（min和max中心的索引）
    
  • 如果key在mid的左边，缩小范围时，min稳定，max等于mid减1
    
  • 如果key在mid的右边，缩小范围时，max稳定，min等于mid加1
    
  
  

a. 示例

1. public class Demo3 {
2.     public static void main(String[] args) {
3.         int[] arr = {7, 23, 79, 81, 103, 127, 131, 147};
4.         System.out.println(BinarySearch(arr, 127));
5.     }
6.     public static int BinarySearch(int[] arr, int number){
7.         // 定义范围
8.         int min = 0;
9.         int max = arr.length;
10.         while (true) {
11.             if (min > max) {
12.                 return -1;
13.             }
14.             // 定义中间索引
15.             int mid = (min + max) / 2;
16.             // 核心代码
17.             if (arr[mid] > number) {
18.                 max = mid - 1;
19.             } else if (arr[mid] < number) {
20.                 min = mid + 1;
21.             } else if (arr[mid] == number) {
22.                 return mid;
23.             }
24.         }
25.     }
26. }

复制代码

3. 插值查找

• 插值查找在二分查找的底子上改进。
  
• 前提条件：数据尽可能的分布匀称。
  
• 核心：                                             m                               i                               d                               =                               m                               i                               n                               +                                                                      k                                        e                                        y                                        −                                        a                                        r                                        r                                        [                                        m                                        i                                        n                                        ]                                                                a                                        r                                        r                                        [                                        m                                        a                                        x                                        ]                                        −                                        a                                        r                                        r                                        [                                        m                                        i                                        n                                        ]                                                                   ×                               (                               m                               a                               x                               −                               m                               i                               n                               )                                      mid = min + \dfrac{key-arr[min]}{arr[max]-arr[min]}\times(max-min)                        mid=min+arr[max]−arr[min]key−arr[min]​×(max−min)
  
  
  
  • mid值是key在数组中的百分比位置。
    
  • mid = 偏移量 + 左隔断 ÷ 总隔断 × (最大值-最小值)
    
  
  

4. 斐波那契查找

• 斐波那契查找在二分查找的底子上改进。
  
• 根据黄金分割点来盘算mid索引。
  
• mid = min + 黄金分割点左半边长度 - 1。
  

5. 分块查找

• 原则
  
  
  
  • 前一块中的最大数据，小于后一块中所有的数据（块内无序，块间有序）
    
  • 块数数量一般等于元素个数开根号。比如：16个元素一般分为4块左右。
    
  
  
• 核心：先确定要查找的元素在哪一块，然后再块内挨个查找。
  
  
  
  

a. 示例

• 界说一个数组 {16, 5, 9, 12, 21, 18, 32, 23, 37, 26, 45, 34, 50, 48, 61, 52, 73, 66}，查询数字是否在数组中。
  

1. package day18.search;
3. public class Demo4 {
4.     public static void main(String[] args) {
5.         int[] arr = {16, 5, 9, 12, 21, 18, 32, 23, 37, 26, 45, 34, 50, 48, 61, 52, 73, 66};
7.         // 块对象
8.         Block b1 = new Block(21, 0, 5);
9.         Block b2 = new Block(45, 6, 11);
10.         Block b3 = new Block(73, 12, 17);
12.         Block[] blockArr = {b1, b2, b3};
13.         int number = 66;
14.         // 现确定在哪一块
15.         int index = getIndex(blockArr, arr, number);
16.         // 在块中查找
17.         System.out.println(index);
18.     }
20.     private static int getIndex(Block[] blockArr, int[] arr, int number) {
21.         int indexBlock = findIndexBlock(blockArr, number);
22.         if (indexBlock == -1) {
23.             return -1;
24.         }
25.         int startIndex = blockArr[indexBlock].getStartIndex();
26.         int endIndex = blockArr[indexBlock].getEndIndex();
27.         for (int i = startIndex; i <= endIndex; i++) {
28.             if (arr[i] == number) {
29.                 return i;
30.             }
31.         }
32.         return -1;
33.     }
35.     public static int findIndexBlock(Block[] blockArr, int number){
36.         for (int i = 0; i < blockArr.length; i++) {
37.             if (number <= blockArr[i].getMax()) {
38.                 return i;
39.             }
40.         }
41.         return -1;
42.     }
43. }
45. class Block{
46.     private int max;  // 块中最大值
47.     private int startIndex;  // 起始索引
48.     private int endIndex;  // 结束索引
50.     public Block() {
51.     }
53.     public Block(int max, int startIndex, int endIndex) {
54.         this.max = max;
55.         this.startIndex = startIndex;
56.         this.endIndex = endIndex;
57.     }
59.     public int getMax() {
60.         return max;
61.     }
63.     public void setMax(int max) {
64.         this.max = max;
65.     }
67.     public int getStartIndex() {
68.         return startIndex;
69.     }
71.     public void setStartIndex(int startIndex) {
72.         this.startIndex = startIndex;
73.     }
75.     public int getEndIndex() {
76.         return endIndex;
77.     }
79.     public void setEndIndex(int endIndex) {
80.         this.endIndex = endIndex;
81.     }
82. }

复制代码

二、排序算法

1. 冒泡排序

• 步骤：
  
  
  • 相邻的元素两两比较，大的放反面，小的放前面；
    
  • 第一轮比较完毕之后，最大值就已经确定，第二轮可以少循环一次，反面以此类推；
    
  • 如果数组中有n个数据，总共要实行n-1轮。
    
  
  

a. 示例

• 界说一个数组{2, 1, 4, 5, 3}，并排序。
  

1. import java.util.Arrays;
3. public class Demo1 {
4.     public static void main(String[] args) {
5.         int[] arr = {2, 1, 4, 5, 3};
6.         // 循环多少轮
7.         for (int i = 0; i < arr.length-1; i++) {
8.             // 每一轮排序
9.             for (int j = 0; j < arr.length - 1 - i; j++) {
10.                 if (arr[j] > arr[j + 1]) {
11.                     int temp = arr[j];
12.                     arr[j] = arr[j + 1];
13.                     arr[j + 1] = temp;
14.                 }
15.             }
16.         }
17.         System.out.println(Arrays.toString(arr));
18.     }
19. }

复制代码

2. 选择排序

• 步骤：
  
  
  • 从0索引开始，与每一个索引上的元素依次比较。
    
  • 小的放前面，大的放反面。
    
  
  

a. 示例

• 界说一个数组{2, 1, 6, 8, 3}，并排序。
  

1. import java.util.Arrays;
3. public class Demo2 {
4.     public static void main(String[] args) {
5.         int[] arr = {2, 1, 6, 8, 3};
7.         // 进行比较的索引值
8.         for (int i = 0; i < arr.length; i++) {
9.             // 拿每个索引值对应的元素与后面的每个元素进行比较
10.             // 每完成一轮，索引值加1
11.             for (int j = i + 1; j < arr.length; j++) {
12.                 if (arr[i] > arr[j]) {
13.                     int temp = arr[i];
14.                     arr[i] = arr[j];
15.                     arr[j] = temp;
16.                 }
17.             }
18.         }
20.         System.out.println(Arrays.toString(arr));
21.     }
22. }

复制代码

3、插入排序

• 步骤：
  
  
  • 将索引在[0, N]的元素看作有序的，把[N+1, arr.length-1]的元素当成无序的。
    
  • 遍历无序的数据，将遍历到的元素插入到有序序列中适当的位置，如遇到相同数据，插在反面。
    
  
  
• N的范围：0～arr.length-1
  

a. 示例

• 界说数组：{3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48}
  

1. import java.util.Arrays;
3. public class Demo3 {
4.     public static void main(String[] args) {
5.         int[] arr = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};
7.         // 找到无序的那一组数据从哪个索引开始
8.         int startIndex = -1;
9.         for (int i = 0; i < arr.length; i++) {
10.             if (arr[i] > arr[i + 1]) {
11.                 startIndex = i + 1;
12.                 break;
13.             }
14.         }
16.         // 遍历从startIndex开始到最后一个元素
17.         for (int i = startIndex; i < arr.length; i++) {
18.             // 记录索引，以防被修改
19.             int j = i;
20.             // 遍历交换位置
21.             while (j > 0 && arr[j] < arr[j - 1]) {
22.                 int temp = arr[j];
23.                 arr[j] = arr[j - 1];
24.                 arr[j - 1] = temp;
25.                 j--;
26.             }
27.         }
28.         System.out.println(Arrays.toString(arr));
29.     }
30. }

复制代码

4. 快速排序（效率最高）

• 步骤：
  
  
  • 将排序范围内的第一个数字作为基准数，在界说两个索引变量start、end
    
  • 索引start从前往后找比基准数大的，索引end从后往前找比基准数小的。
    
  • start、end都找到一个数后，替换两个数。
    
  • 循环上面三步，直到start和end指向同一个索引。让基准数与这个索引的元素替换（基准数归位）。
    
    
    
    • 归位后的效果：基准数左边的，比基准数小；基准数右边的，比基准数大。
      
    
    
  • 对基准数两边的数据重复上面四步，直到要求范围的开始索引大于竣事索引。
    
  
  

a. 示例

• 界说一个长度为100万的数组，为数组随机添补数字，给数组举行排序。
  

1. import java.util.Random;
3. public class Demo6 {
4.     public static void main(String[] args) {
5.         Random random = new Random();
6.         int[] arr = new int[1000000];
7.         for (int i = 0; i < arr.length; i++) {
8.             arr[i] = random.nextInt();
9.         }
10.         
11.         long start = System.currentTimeMillis();
12.         quickSort(arr, 0, arr.length - 1);
13.         long end = System.currentTimeMillis();
15.         System.out.println("共用时: " + (end-start));
16.     }
19.     public static void quickSort(int[] arr, int startIndex, int endIndex) {
20.         if (startIndex > endIndex) return;
21.         // 记录索引值，防止被修改
22.         int start = startIndex;
23.         int end = endIndex;
24.         // 记录基准数
25.         int baseNumber = arr[startIndex];
26.         // 利用循环找到要交换的数
27.         while (start != end) {
28.             // 从end往前找
29.             while (end > start && arr[end] >= baseNumber) end--;
30.             // 从start往后找
31.             while (end > start && arr[start] <= baseNumber) start++;
32.             // 交换start和end
33.             int temp = arr[end];
34.             arr[end] = arr[start];
35.             arr[start] = temp;
36.         }
37.         // 基准数归位
38.         int temp = arr[startIndex];
39.         arr[startIndex] = arr[end];
40.         arr[end] = temp;
41.         // 确定6左边的范围
42.         quickSort(arr, startIndex, start - 1);
43.         // 确定6右边的范围
44.         quickSort(arr, end + 1, endIndex);
45.     }
46. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。