数据结构与算法——选择排序和插入排序

鱼天翱 2019-07-01

1. 回顾

前面说到了冒泡排序,这是一种时间复杂度为 O(n2) 、是原地排序和稳定的的排序算法,具体思路是:根据相邻两个元素之间比较大小,然后交换位置,得出最后排序的结果。具体可参考我写的这一篇文章:数据结构与算法——冒泡排序,今天来看看另外两种基础的排序算法:选择排序和插入排序。

2. 选择排序

先来看看选择排序,选择排序的思路其实很简单,将排序的数据分为已排序区间和未排序区间,一般是以第一个元素为已排序区间,然后依次遍历未排序区间,找到其最小值,和未排序区间的最后一个值进行比较,交换位置。未排序区间遍历完毕,则排序结束。光说可能有点抽象,我画了一张图来帮助你理解:

数据结构与算法——选择排序和插入排序

是不是很简单呢?下面是它的代码实现:

public class SelectionSort {
    public static void selectionSort(int[] data){
        int length = data.length;
        //如果只有一个元素,或者数组为空,则直接退出
        if (length <= 1) return;

        for (int i = 0; i < length - 1; i++) {
            int min = i + 1;
            //找到最小值
            for (int j = i + 1; j < length; j++) {
                if (data[j] < data[min]) min = j;
            }
            //交换位置
            if (data[min] < data[i]){
                int temp = data[min];
                data[min] = data[i];
                data[i] = temp;
            }
        }
    }
}

结合代码分析,选择排序在最好、最坏和平均情况下的时间复杂度都是 O(n2),并且没有借助额外的存储空间,是一种原地排序算法。那么选择排序是稳定的吗?答案是否定的,举个例子:排序的数组为 data[2, 2, 1, 3, 5, 4, 8],第一次遍历未排序的数组,找到最小值为 1,和第一个 2 交换位置,那么这两个 2 的前后顺序就被打乱了,所以稳定性被破坏。正因如此,选择排序比起冒泡排序和插入排序就显得逊色很多了。

3. 插入排序

我们再来看看插入排序,其实思路和上面的选择排序非常的类似,也是将排序数据分为已排序区间和未排序区间,依次遍历未排序区间,和已排序区间的值进行比较,将其插入到合适的位置上,直至将未排序的区间数据遍历完。

你可以结合下面的图来理解:

数据结构与算法——选择排序和插入排序

可以看到,和选择排序一样,将第一个数据作为已排序区间,第一次遍历到 2 ,将其插入到 4 后面,然后再依次遍历。
下面是代码实现:

public class InsertionSort {
    public static void insertionSort(int[] data){
        int length = data.length;
        if (length <= 1) return;

        for (int i = 1; i < length; i++) {
            int value = data[i];
            int j = i - 1;
            for (; j >= 0; j --){
                if (data[j] > value) data[j + 1] = data[j];
                else break;
            }
            data[j + 1] = value;
        }
    }
}

很显然,插入排序也是稳定的,因为我们是在 data[j] > da[j + 1] 的时候,才进行数据交换,不会影响到相同元素的前后位置。并且,插入排序是原地排序,最好情况下,数组本来就是有序的,所以我们只需要遍历一次数组就可以了,时间复杂度是 O(n),最坏情况和平均情况下,时间复杂度都是 O(n2)。

最后还有个问题,为什么在实际中,插入排序的比冒泡排序使用的更加广泛呢?虽然这两个排序算法的平均时间复杂度都是 O(n2),但是结合代码,不难发现,它们涉及到的数据交换操作时略有差别的。

冒泡排序在交换数据的时候,需要进行三次赋值操作,而插入排序只需要一次。

//插入排序的赋值操作            
for (; j >= 0; j --){
    if (data[j] > value) data[j + 1] = data[j];
    else break;
}

//冒泡排序的赋值操作        
for (int j = 0; j < n - i - 1; j++) {
    //如果data[j] > data[j + 1],交换两个数据的位置
    if (data[j] > data[j + 1]){
       int temp = data[j];
       data[j] = data[j + 1];
       data[j + 1] = temp;
    }

在数据规模小的时候,这样的差别没什么影响,但是如果我们要排序的是一组较大的数据,那么两种排序算法的执行时间的差别就会很明显了。

相关推荐

yuanran0 / 0评论 2020-04-20
闫新宇 / 0评论 2015-02-06