十大经典排序算法动画与解析,看我就够了!(配代码完全版) (2)

从头到尾依次扫描未排序序列,将扫描到的每个元素插入有序序列的适当位置。(如果待插入的元素与有序序列中的某个元素相等,则将待插入元素插入到相等元素的后面。)

3.2 动画演示

image

image

3.3 参考代码 1//Java 代码实现
2public class InsertSort implements IArraySort {
3
4    @Override
5    public int[] sort(int[] sourceArray) throws Exception {
6        // 对 arr 进行拷贝,不改变参数内容
7        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
8
9        // 从下标为1的元素开始选择合适的位置插入,因为下标为0的只有一个元素,默认是有序的
10        for (int i = 1; i < arr.length; i++) {
11
12            // 记录要插入的数据
13            int tmp = arr[i];
14
15            // 从已经排序的序列最右边的开始比较,找到比其小的数
16            int j = i;
17            while (j > 0 && tmp < arr[j - 1]) {
18                arr[j] = arr[j - 1];
19                j--;
20            }
21
22            // 存在比其小的数,插入
23            if (j != i) {
24                arr[j] = tmp;
25            }
26
27        }
28        return arr;
29    }
30}
4. 希尔排序 4.1 算法步骤

选择一个增量序列 t1,t2,……,tk,其中 ti > tj, tk = 1;

按增量序列个数 k,对序列进行 k 趟排序;

每趟排序,根据对应的增量 ti,将待排序列分割成若干长度为 m 的子序列,分别对各子表进行直接插入排序。仅增量因子为 1 时,整个序列作为一个表来处理,表长度即为整个序列的长度。

4.2 动画演示

image

image

4.3 参考代码 1//Java 代码实现
2public class ShellSort implements IArraySort {
3
4    @Override
5    public int[] sort(int[] sourceArray) throws Exception {
6        // 对 arr 进行拷贝,不改变参数内容
7        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
8
9        int gap = 1;
10        while (gap < arr.length) {
11            gap = gap * 3 + 1;
12        }
13
14        while (gap > 0) {
15            for (int i = gap; i < arr.length; i++) {
16                int tmp = arr[i];
17                int j = i - gap;
18                while (j >= 0 && arr[j] > tmp) {
19                    arr[j + gap] = arr[j];
20                    j -= gap;
21                }
22                arr[j + gap] = tmp;
23            }
24            gap = (int) Math.floor(gap / 3);
25        }
26
27        return arr;
28    }
29}
5. 归并排序 5.1 算法步骤

申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列;

设定两个指针,最初位置分别为两个已经排序序列的起始位置;

比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置;

重复步骤 3 直到某一指针达到序列尾;

将另一序列剩下的所有元素直接复制到合并序列尾。

5.2 动画演示

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/wsfpsj.html