小蓝xlanll

这个屌丝很懒，什么也没留下！

热门标签

数据结构与算法系列第六篇——排序算法_《数据结构与算法》专栏收录该内容

作者：小蓝xlanll | 2024-04-30 04:23:40

踩

《数据结构与算法》专栏收录该内容

简单排序

对数据排序可能是检索的一个初始步骤，例如：二分查找法比线性查找法要快的多，然而它只能应用于有序的数据。
先介绍三种简单排序：冒泡，选择，插入。算法比较简单，执行速度也就慢一些，在某些情况下比那些复杂的算法实际上还好一些。比如小规模的文件以及基本有序的文件，插入排序算法能比快速排序算法更为有效，实际上，插入排序通常也作为快速排序算法实现的一部分。
简单排序算法大致上都包含如下操作：

1.比较两个数据项
2.交换两个数据项，或复制其中一项

一般来说，数组中有N个数据项，则第一遍排序中有N-1次比较，第二遍有N-2次，如此类推
（N-1）+(N-2)+(N-3)+…+1=N*(N-1)/2
这样算法做了约N²/2次比较。
当比较的两个元素，左边大于右边时，需要交换，否则不交换。
如果数据是随机的，大约有一半的元素可能需要交换，则交换的次数为N²/4
交换和比较的次数都和N²成正比，使用大O表示法可知冒泡排序法的时间复杂度为O(N²)

选择排序

对冒泡排序法进行改进，将交换次数从O(N²)减少到O(N)，而比较次数仍然是O(N²)

算法描述（以数组为例，从小到大排序）

从数组最左边开始，以第一个元素为基准（设为最小值），把数组中所有的元素扫描一遍和最小值比较，一轮比较结束之后，找到了数组中最小的元素。
然后最小元素和基准位置的数据进行交换
从左侧第二个元素开始，继续此操作。。。

案例

package test31;

/**
 * 选择排序
 */
public class ArraySelect {
    private int[] a;
    //记录数组的实际长度
    private int nElems;

    public ArraySelect(int max) {
        a = new int[max];
        nElems = 0;
    }

    /**
     * 插入操作
     *
     * @param value
     */
    public void insert(int value) {
        a[nElems] = value;
        nElems++;
    }

    /**
     * 展示
     */
    public void display() {
        for (int i = 0; i < nElems; i++) {
            System.out.print(a[i] + " ");
        }
        System.out.println();
    }

    public void selectionSort() {
        int out, in, min;
        int temp;
        for (out = 0; out < nElems-1; out++) {
            //每次以out索引记为最小
            min = out;
            for (in = out+1; in < nElems; in++) {
                //每次找到最小的
                if (a[in] < a[min]) {
                    min = in;
                }
            }
            //里层循环完毕，将最小值的索引位置上的数据和out索引位置的数据进行交换
            //因此交换的次数成了O(N)，这就是比冒泡排序优越的地方
            temp = a[out];
            a[out] = a[min];
            a[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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

package test31;

/**
 *  选择排序
 */
public class SelectionSortApp {
    public static void main(String[] args) {
        int maxSize = 100;
        ArraySelect arr = new ArraySelect(maxSize);
        arr.insert(99);
        arr.insert(88);
        arr.insert(77);
        arr.insert(66);
        arr.insert(55);
        arr.insert(44);
        arr.insert(33);
        arr.insert(22);
        arr.insert(11);
        arr.insert(00);

        arr.display();
        arr.selectionSort();
        arr.display();
    }
}

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

在这里插入图片描述

特点

左侧的数据总是有序的，即下标小于或等于out的位置的数据项总是有序的

效率

选择排序和冒泡排序执行了相同次数的比较：N*(N-1)/2.但选择排序更快，因为它进行的交换次数少的多。
使用大O表示法可知选择排序法的时间复杂度为O(N²)

插入排序

算法描述（以数组为例，从小到大排序）

标记变量，一般标记数组中的第二个数据，标记变量左边的数据有序，右边的无序。
将标记变量存储到一个临时变量中，并将标记变量与其左侧的数据进行比较，插入到适当的位置。
每一轮过后，标记变量向右移动一个位置

案例

package test32;

/**
 * 插入排序
 */
public class ArrayInsert {
    private int[] a;
    //记录数组的实际长度
    private int nElems;

    public ArrayInsert(int max) {
        a = new int[max];
        nElems = 0;
    }

    /**
     * 插入操作
     *
     * @param value
     */
    public void insert(int value) {
        a[nElems] = value;
        nElems++;
    }

    /**
     * 展示
     */
    public void display() {
        for (int i = 0; i < nElems; i++) {
            System.out.print(a[i] + " ");
        }
        System.out.println();
    }

    public void insertionSort() {
        int out, in;
        int temp;
        //out变量从1开始，向右移动，他标记了未排序部分的最左端的数据
        for (out = 1; out < nElems; out++) {
            temp = a[out];
            in = out;
            //in变量从out变量开始，向左移动，直到temp变量小于in所指的数组数据项
            //或者它已经不能向左移动为止。
            //while循环的每一趟都向右移动了一个已排序的数据项
            while (in > 0 && a[in - 1] >= temp) {
                a[in] = a[in - 1];
                --in;
            }
            a[in] = 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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

package test32;

/**
 *  插入排序
 */
public class InsertionSortApp {
    public static void main(String[] args) {
        int maxSize = 100;
        ArrayInsert arr = new ArrayInsert(maxSize);
        arr.insert(99);
        arr.insert(88);
        arr.insert(77);
        arr.insert(66);
        arr.insert(55);
        arr.insert(44);
        arr.insert(33);
        arr.insert(22);
        arr.insert(11);
        arr.insert(00);

        arr.display();
        arr.insertionSort();
        arr.display();
    }
}

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

在这里插入图片描述

特点

每一趟结束后，在将temp位置的项插入后，比outer变量下标小的数据项都是局部有序的。

效率

在第一趟排序中，它比较1次，第二趟比较2次，以此类推，第N趟，比较N-1次，因此N*(N-1)/2
实际情况下，如果是随机的数据，平均有一半的需要比较，所以N*(N-1)/4。
复制的次数大致等于比较的次数。但是，一次复制与一次交换的时间耗费不同，所以相对于随机数据，这个算法比冒泡排序快一倍，比选择排序略快。
时间复杂度也是O(N²)
对于已经有序或基本有序的数据来说，插入排序要好得多。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小蓝xlanll/article/detail/511408

数据结构与算法系列第六篇——排序算法_《 数据结构与算法 》专栏收录该内容

排序算法

简单排序

冒泡排序

算法描述（以数组为例，从小到大排序）

案例

特点

效率

选择排序

算法描述（以数组为例，从小到大排序）

案例

特点

效率

插入排序

算法描述（以数组为例，从小到大排序）

案例

特点

效率

数据结构与算法系列第六篇——排序算法_《数据结构与算法》专栏收录该内容