Java数组算法(二分、冒泡、选择、快排)

查找

二分查找

时间复杂度：O (logN)
说明：取数组中间的值和查找值进行比较、如果 中间的值大于要查找的值、则高位索引往中间索引-1、小于则是低位索引往上提、即中间索引+1、一直循环直至找到值、最后没有找到则返回-1

1. /**
2.   * 二分查找法
3.   * @return 返回查找的索引、没有则返回-1
4.   */
5. public static int binarySearch(int[] arrs, int key) {
6.     // 定义了低位索引和高位索引
7.     int lowIndex = 0, highIndex = arrs.length - 1;
8.     // 一直循环、直至低位索引和高位索引值一致
9.     while (lowIndex <= highIndex) {
10.         // 取中间索引、即低位索引+高位索引的和除以2、正数右移n位相当于除以2的n次方
11.         int midIndex = (lowIndex + highIndex) >>> 1,
12.         midValue = arrs[midIndex];
13.         if (midValue > key)
14.             highIndex = midIndex - 1;
15.         else if (midValue < key)
16.             lowIndex = midIndex + 1;
17.         else
18.             return midIndex;
19.     }
20.     return -1;
21. }

复制代码

排序

冒泡排序

时间复杂度：O (n)

1. /**
2.   * 冒泡排序
3.   */
4. public static void sort(int[] arr) {
5.     for (int i = 1; i < arr.length; i++) {
6.         for (int j = 0; j < arr.length - i; j++) {
7.             if (arr[j] > arr[j + 1]) {
8.                 // 交换
9.                 arr[j] = arr[j] ^ arr[j + 1];
10.                 arr[j + 1] = arr[j] ^ arr[j + 1];
11.                 arr[j] = arr[j] ^ arr[j + 1];
12.             }
13.         }
14.     }
15. }

复制代码

选择排序

时间复杂度：O（n²）
选择排序是一种简单直观的排序算法，无论什么数据进去都是 O(n²) 的时间复杂度。所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。

1. /**
2.   * 选择排序
3.   */
4. public static void sort(int[] arr) {
5.     // 总共要经过 N-1 轮比较
6.     for (int i = 0; i < arr.length - 1; i++) {
7.         int min = i;
9.         // 每轮需要比较的次数 N-i
10.         for (int j = i + 1; j < arr.length; j++) {
11.             if (arr[j] < arr[min]) {
12.                 // 记录目前能找到的最小值元素的下标
13.                 min = j;
14.             }
15.         }
17.         // 将找到的最小值和i位置所在的值进行交换
18.         if (i != min) {
19.             arr[i] = arr[i] ^ arr[min];
20.             arr[min] = arr[i] ^ arr[min];
21.             arr[i] = arr[i] ^ arr[min];
22.         }
23.     }
24. }

复制代码

快速排序

时间复杂度：O(nlogn)  速度最快

1. /**
2.   * 快速排序
3.   * @param src 数组
4.   * @param begin 起始索引
5.   * @param end 尾部索引
6.   */
7. public static void sort(int[] src, int begin, int end) {
8.     if (begin < end) {
9.         int key = src[begin];
10.         int i = begin;
11.         int j = end;
12.         while (i < j) {
13.             while (i < j && src[j] > key) {
14.                 j--;
15.             }
16.             if (i < j) {
17.                 src[i] = src[j];
18.                 i++;
19.             }
20.             while (i < j && src[i] < key) {
21.                 i++;
22.             }
23.             if (i < j) {
24.                 src[j] = src[i];
25.                 j--;
26.             }
27.         }
28.         src[i] = key;
29.         sort(src, begin, i - 1);
30.         sort(src, i + 1, end);
31.     }
32. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！