十大经典排序算法2（Python版本）

小灰灰 2022-12-11 12:24 109阅读 0赞

### 文章目录 ###

*   *   *  二、选择排序
         *  三、插入排序

### 二、选择排序 ###

**1、选择介绍**  
选择排序是一种简单直观的排序算法，无论什么数据进去都是 O(n²) 的时间复杂度。所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。

**2、算法步骤**

*  首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置
 *  再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
 *  重复第二步，直到所有元素均排序完毕。

**3、动图演示**  
![01][]

**4、Python练习**

def selectionSort(arr):
        for i in range(len(arr) - 1):
            minIndex = i  # 记录最小数的索引
            for j in range(i + 1, len(arr)):
                if arr[j] < arr[minIndex]:
                    minIndex = j
            if i != minIndex:  # i 不是最小数时，将 i 和最小数进行交换
                arr[i], arr[minIndex] = arr[minIndex], arr[i]
        return arr
    a = [3,5,15,2,26,27,4,19,36,47,28,50,19,48,44]
    selectionSort(a)
    print(a)

--------------------

### 三、插入排序 ###

**1、插入理解**  
插入排序的代码实现虽然没有冒泡排序和选择排序那么简单粗暴，但它的原理应该是最容易理解的了，因为只要打过扑克牌的人都应该能够秒懂。插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

插入排序和冒泡排序一样，也有一种优化算法，叫做拆半插入。

**2、算法步骤**

*  将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
 *  从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）

**3、动图演示**  
![02][]

**4、Python演示**

def insertionSort(arr):
        for i in range(len(arr)):  # 第一层遍历每个数字，一次选中一个
            preIndex = i-1  # 记录需要进行插入的数的下标
            current = arr[i]  # 记录需要进行插入的数的值
            while preIndex >= 0 and arr[preIndex] > current:  # 遍历未排序的数，找到位置在需要插入的数后面且比需要插入的数大的数
                arr[preIndex+1] = arr[preIndex]
                preIndex-=1
            arr[preIndex+1] = current
        return arr
    a = [3,5,15,2,26,27,4,19,36,47,28,50,19,48,44]
    insertionSort(a)
    print(a)

文章转载于：  
[十大经典排序算法（Python）][Python]

[01]: /images/20221123/0e0f9047b17d47e4b32f5d45432f36a0.png
[02]: /images/20221123/73eef9f477b745628017dcff6e9d010e.png
[Python]: https://mp.weixin.qq.com/s?__biz=MzI0MzU2NzQ1OA==&mid=2247489169&idx=1&sn=5d4c64225010e4b6e333cf962412d239&chksm=e96a489cde1dc18a092840dd40e45251c705a8bddbcb1fbdf6791c754de75cc2ace439587180&mpshare=1&scene=23&srcid=09221Zfx2rypvHYFTttont6W&sharer_sharetime=1600761961411&sharer_shareid=b2a2e30106bb801eb92a67be762689dd#rd