ToB企服应用市场:ToB评测及商务社交产业平台

标题: Java数组算法(二分、冒泡、选择、快排) [打印本页]
作者: 八卦阵    时间: 2022-9-17 08:40
标题: 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. }
复制代码
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！



欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/) Powered by Discuz! X3.4