文章首发于：clawhub.club

冒泡排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
    * 冒泡排序的基本思想是对比相邻的元素值，
    * 如果满足条件就交换元素值，
    * 把较小的元素值移到数组前面，
    * 大的元素值移到数组后面，
    * 这样较小的元素就像气泡一样从底部上升到顶部。
    *
    * @param array the array
    */
   private static void bubbleSort(int[] array) {
       for (int i = 0; i < array.length; i++) {
           for (int j = 1; j < array.length; j++) {
               if (array[i] > array[j]) {
                   int temp = array[i];
                   array[i] = array[j];
                   array[j] = temp;
               }
           }
       }
   }

####选择排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
 * Select sort.
 * 从待排序序列中，找到关键字最小的元素
 * 如果最小元素不是待排序序列的第一个元素，将其和第一个元素互换
 * 从余下的 N - 1 个元素中，找出关键字最小的元素，重复以上操作，直到排序结束
 *
 * @param array the array
 */
private static void selectSort(int[] array) {
    //总共要比较数组数量减一次
    for (int i = 0; i < array.length - 1; i++) {
        //本轮第一个元素下表
        int min = i;
        //每轮要比较的次数
        for (int j = i + 1; j < array.length; j++) {
            //当前元素小于初始元素
            if (array[j] < array[min]) {
                //找到关键字最小的元素,记录目前最小元素下标
                min = j;
            }
        }
        //本轮比较完毕，如果最小元素不是待排序序列的第一个元素，将其和第一个元素互换
        if (i != min) {
            int temp = array[i];
            array[i] = array[min];
            array[min] = temp;
        }
    }
}

插入排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * Insert sort.
 * 直接插入排序基本思想是每一步将一个待排序的记录，
 * 插入到前面已经排好序的有序序列中去，直到插完所有元素为止
 *
 * @param array the array
 */
private static void insertSort(int[] array) {
    //第一位默认有序，所以从第二个开始
    for (int i = 1; i < array.length; i++) {
        //等待插入数据
        int temp = array[i];
        //从已经排好序的数组右边开始，往左比较，找到比自己小的元素，放到这个元素的后面
        //也就是说，碰到比自己大的元素就要向后移动一位
        int j = i;
        while (j > 0 && temp < array[j - 1]) {
            //array[j - 1]向后移动
            array[j] = array[j - 1];
            j--;
        }
        //存在比自己小的元素，插入
        array[j] = temp;
    }
}

####折半查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/**
   * 折半查找元素在数组中的位置
   * 假设数组是升序的，取数组的中间下标作为基准：
   * 如果查找的元素等于中间下标对应的元素，则已经找到；
   * 如果查找的元素大于中间下标对应的元素，说明要查找的元素在数组的右半边，此时用中间下标对应的元素代替查找范围的最小值，再在新的范围内折半查找。
   * 如果查找的元素小于中间下标的元素，说明查找的元素在数组的左半边，此时将中间下标对应的元素代替查找范围的最大值，在新的范围内进行查找。
   * 如果查找范围最大值的下标小于查找范围的最小值的下标，说明数组内没有要查询的元素。
   * 很显然对于在大量数据里的查找，我们可以将待查找的数据进行排序，然后再用折半查找进行查找，会提高查找的效率。
   * 折半查找的时间复杂度为O(logn)。
   *
   * @param array     the array
   * @param target    the target
   * @param fromIndex the from index
   * @param toIndex   the to index
   * @return the int
   */
  private static int binarySearch(int[] array, int target, int fromIndex, int toIndex) {
      //假设为升序排列，如：1，2，3，4，5。
      int low = fromIndex;
      int high = toIndex - 1;
      while (low <= high) {
          //无符号右移， 除以二。
          int mid = (low + high) >>> 1;
          int midVal = array[mid];
          if (target > midVal) {
              //如果目标值大于中间值，则目标值在中间值的右侧。
              low = mid + 1;
          } else if (target < midVal) {
              //如果目标值小于中间值，则目标值在中间值的左侧。
              high = mid - 1;
          } else {
              //找到元素位置。
              return mid;
          }
      }
      //未找到目标值
      return -(low + 1);
  }

数组逆序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
  * 数组反转，
  * 数组第一个元素与倒数第一个元素交换，第二个元素与倒数第二个元素交换，
  * 偶数则全部交换完毕
  * 奇数则中间位置元素不变
  *
  * @param array the array
  */
 private static void reversal(int[] array) {
     int middle = array.length >>> 1;
     for (int i = 0; i < middle; i++) {
         int temp = array[i];
         array[i] = array[array.length - 1 - i];
         array[array.length - 1 - i] = temp;
     }
 }