今天学习了一下 Java 数组的相关操作,包含排序和查找,现在先将排序记录巩固一下。
常用并且比较重要的几种排序:插入排序希尔排序快速排序归并排序冒泡排序选择排序

一、插入排序

1. 插入排序算法思想

1) 普遍思想
插入排序的算法是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序的数据,在已排序的序列中从后向前扫描,找到相应位置并插入。插入排序在实现上,在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间。

2) 我的理解与分析
我最初看到上面的思想,就是一脸懵逼,读都读不懂,又去找了很多资料,才能理解那么一点点,所以这里用通俗一点的话来解释:

假设有一个数组:

1
int[] arr = { 22, 11, 10, 55, 44 };

  • 第 0 个元素 22 看作已经排好序;
  • 取出第 1 个元素 11,在已经排序的元素序列中(第一步的 22)从后向前扫描;
  • 如果新元素 11 比已排序的元素 22 小,就把 22 往后挪,并将 11 插入到前面。这个时候数组应该如下:

    1
    int[] arr = { 11, 22, 10, 55, 44 }
  • 接着在取出第 2 个元素 10,与第一个元素 22 相比,如果比第一个元素小,就插入到 22 之前。这个时候数组应该如下:

    1
    int[] arr = { 11, 10, 22, 55, 44 }
  • 10 插入后继续与前面的元素相比,小则插入,大则不动。这个时候数组应该如下:

    1
    int[] arr = { 10, 11, 22, 55, 44 }
  • 取出第 3 个元素继续比较……

插入排序的特点:越有序,操作的次数越少,效率越高。

2. 算法图解附视频

插入排序图解

视频 点此查看

3. 算法代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import java.util.Arrays;

public class InsertSort {
public static void main(String[] args) {
int[] arr = { 11, 22, 10, 55, 44 };
sort(arr);
System.out.println(Arrays.toString(arr));
}

public static void sort(int[] arr) {
for (int i = 1; i < arr.length; i++) { // 从第一个元素开始遍历
for (int j = i; (j > 0) && (arr[j] < arr[j - 1]); j--) { // 条件:是否比前一个元素小,j-- 是为了挪位后再次与前一个元素比较
int temp = arr[j]; // 把移动的元素暂时存起来
arr[j] = arr[j - 1]; // 把大的元素往后挪
arr[j - 1] = temp; // 把小的元素放到前面
}
}
}
}

二、希尔排序

1. 算法简介

希尔排序 是插入排序的改进版本。为什么是插入排序的改进版本呢?上面说过的插入排序,它是取出一个元素然后从后向前比较,如果小于就放到前面来,并且它的特点是 越有序,效率越高。对于插入排序,序列数据少的话还行,要是序列数据特别多,并且是无序,那么插入排序的效率就会很慢,所以就出现了一个希尔排序,使序列更 接近有序,这样的话,相对于插入排序操作数据较大的时候要快一点,不过它最终属于插入排序类中。

2. 算法分析

希尔排序,先将要排序的一组数据按某个增量 d(n/2,n 为排序数的个数) 分成若干组(把相隔 d 的数据分为一组),并在各组内进行直接插入排序,然后再用一个较小的增量 (d/2) 对它进行分组,在每组中再进行插入排序,当增量减到 1 时,进行插入排序后,排序完成。

假设有一个数组:

1
int[] arr = { 49, 38, 65, 97, 76, 13, 27, 49, 55, 04 };

  • 先取一个增量 d = n/2 = 5,把每相隔 5 的数据分为一组,如下:

    1
    2
    3
    4
    5
    第一组 ---> 49 -- 13
    第二组 ---> 38 -- 27
    第三组 ---> 65 -- 49
    第四组 ---> 97 -- 55
    第五组 ---> 76 -- 04
  • 每一组进行插入排序,如下:

    1
    2
    3
    4
    5
    第一组 ---> 13 -- 49
    第二组 ---> 27 -- 38
    第三组 ---> 49 -- 65
    第四组 ---> 55 -- 97
    第五组 ---> 04 -- 76
  • 第一次的结果为:

    1
    { 13, 27, 49, 55, 04, 49, 38, 65, 97, 76 };
  • 取第二个增量 d2 = d/2 = 3,把每相隔 3 的数据分为一组,如下:

    1
    2
    3
    第一组 ---> 13 -- 55 -- 38 -- 76
    第二组 ---> 27 -- 04 -- 65
    第三组 ---> 49 -- 49 -- 97
  • 每一组进行插入排序,如下:

    1
    2
    3
    第一组 ---> 13 -- 38 -- 55 -- 76
    第二组 ---> 04 -- 27 -- 65
    第三组 ---> 49 -- 49 -- 97
  • 第二次的结果为:

    1
    { 13, 04, 49, 38, 27, 49, 55, 65, 97, 76 };
  • 取第三个增量 d3 = d2/2 = 1,把每相隔 1 的数据分为一组,这时开始直接插入排序即可,结果如下:

    1
    { 04, 13, 27, 38, 49, 49, 55, 65, 76, 97 };

增量 d 取值为奇数。

3. 算法图解附视频

希尔排序图解

视频 点此查看

4. 算法代码

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
import java.util.Arrays;

public class ShellSort {
public static void main(String[] args) {
int[] arr = { 49, 38, 65, 97, 76, 13, 27, 49, 55, 04 };
sort(arr);
System.out.println(Arrays.toString(arr));
}

public static void sort(int[] arr) {
for (int d = arr.length / 2; d > 2; d /= 2) {
for (int i = 0; i < d; i++) {
insertSort(arr, i, d);
}
}
insertSort(arr, 0, 1);
}

// 插入排序
public static void insertSort(int[] arr, int i, int d) {
for (int a = i + d; a < arr.length; a += d) { // a += d
for (int j = a; (j >= d) && (arr[j] < arr[j - d]); j -= d) {
int temp = arr[j];
arr[j] = arr[j - d];
arr[j - d] = temp;
}
}
}
}