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

rockswang 发布于2019-08-16 15:54 / 1460人阅读

摘要：具体可参考我写的这一篇文章数据结构与算法冒泡排序，今天来看看另外两种基础的排序算法选择排序和插入排序。正因如此，选择排序比起冒泡排序和插入排序就显得逊色很多了。冒泡排序在交换数据的时候，需要进行三次赋值操作，而插入排序只需要一次。

1. 回顾

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

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(n²)，并且没有借助额外的存储空间，是一种原地排序算法。那么选择排序是稳定的吗？答案是否定的，举个例子：排序的数组为 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(n²)。

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

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

//插入排序的赋值操作            
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;
    }

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

云服务器 GPU云服务器插入排序算法 java插入排序算法选择排序的算法过程字符串选择排序算法

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/73773.html

JavaScript 数据结构与算法之美 - 冒泡排序、插入排序、选择排序

摘要：之所以把冒泡排序选择排序插入排序放在一起比较，是因为它们的平均时间复杂度都为。其中，冒泡排序就是原地排序算法。所以冒泡排序是稳定的排序算法。选择排序思路选择排序算法的实现思路有点类似插入排序，也分已排序区间和未排序区间。 showImg(https://segmentfault.com/img/bVbuvnj?w=900&h=250); 1. 前言算法为王。想学好前端，先练好内功，...

canger 2019-08-26 10:15 评论0 收藏0
JavaScript 数据结构与算法之美 - 十大经典排序算法汇总

摘要：笔者写的数据结构与算法之美系列用的语言是，旨在入门数据结构与算法和方便以后复习。这应该是目前较为简单的十大经典排序算法的文章讲解了吧。比如原本在的前面，而，排序之后，在的后面十大经典排序算法冒泡排序思想冒泡排序只会操作相邻的两个数据。 showImg(https://segmentfault.com/img/bVbvHet); 1. 前言算法为王。想学好前端，先练好内功，内功不行，就...

zsy888 2019-08-26 10:27 评论0 收藏0
排序算法（Java）——那些年面试常见的排序算法

摘要：下面会介绍的一种排序算法快速排序甚至被誉为世纪科学和工程领域的十大算法之一。我们将讨论比较排序算法的理论基础并中借若干排序算法和优先队列的应用。为了展示初级排序算法性质的价值，我们来看一下基于插入排序的快速的排序算法希尔排序。前言　　排序就是将一组对象按照某种逻辑顺序重新排列的过程。比如信用卡账单中的交易是按照日期排序的——这种排序很可能使用了某种排序算法。在计算时代早期，大家普遍...

Harpsichord1207 2019-08-15 14:50 评论0 收藏0
常用排序算法之JavaScript实现

摘要：代码实现六堆排序算法简介堆排序是指利用堆这种数据结构所设计的一种排序算法。九计数排序算法简介计数排序是一种稳定的排序算法。计数排序不是比较排序，排序的速度快于任何比较排序算法。赞助我以写出更好的文章，give me a cup of coffee? 2017最新最全前端面试题 1、插入排序 1）算法简介插入排序（Insertion-Sort）的算法描述是一种简单直观的排序算法。它...

jerry 2019-08-21 12:27 评论0 收藏0