玩蛇(Python) - 排序算法:冒泡排序、选择排序、插入排序

一、排序算法

排序算法可以分为内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。

1.1 时间复杂度

算法的时间复杂度（Time complexity）是一个函数，它定性描述该算法的运行时间，具体来说就是对排序数据的总的操作次数。反映当n变化时，操作次数呈现什么规律。

平方阶 (O(n2)) 排序：各类简单排序，直接插入、直接选择和冒泡排序。

线性对数阶 (O(nlog2n)) 排序：快速排序、堆排序和归并排序。

线性阶 (O(n)) 排序：基数排序，此外还有桶、箱排序。

1.2 空间复杂度

算法的空间复杂度是指算法在计算机内执行时所需存储空间的度量，它也是数据规模n的函数。

1.3 稳定性

排序后 2 个相等键值的顺序和排序之前它们的顺序相同。

稳定的排序算法：冒泡排序、插入排序、归并排序和基数排序。

不是稳定的排序算法：选择排序、快速排序、希尔排序、堆排序。

1.4 排序方式

In-place：占用常数内存，不占用额外内存。

Out-place：占用额外内存。

1.5 排序的类型

非线性时间比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此称为非线性时间比较类排序。 包括：冒泡排序，快速排序 ，插入排序，希尔排序，选择排序，堆排序，归并排序。

线性时间非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此称为线性时间非比较类排序。包括：计数排序，桶排序，基数排序。

本文先介绍冒泡排序(Bubble Sort)，选择排序(Selection Sort)，插入排序(Insertion Sort)。

二、算法详解

2.1 冒泡排序算法原理

冒泡排序(Bubble Sort)是一种简单直观的排序算法。一次比较两个元素，较大的元素会经由交换慢慢“冒”出来（交换）的一种排序方法。

走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。

基本流程如下：

1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。

2) 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。

3) 针对所有的元素重复以上的步骤，直到没有任何一对数字需要比较。

2.2 选择排序(Selection Sort)算法原理

选择排序(Selection Sort)也是一种简单直观的排序算法，无论什么数据进去都是 O(n2) 的时间复杂度。

所以用到此排序的时候，数据规模越小越好。唯一的好处可能就是不占用额外的空间了。

基本流程如下：

1) 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。

2) 再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。

3) 重复第二步，直到所有元素均排序完毕。

2.3插入排序(Insertion Sort)算法原理

插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

基本流程如下：

1) 从第一个元素开始，该元素可以认为已经被排序。

2) 取出下一个元素，在已经排序的元素序列中从后向前扫描。

3) 如果该元素（已排序）大于新元素，将该元素移到下一位置，直到找到已排序的元素小于或者等于新元素的位置。

4) 将新元素插入到该位置后, 重复步骤2~3。

2.4 算法实例

1) 源码

#-*- coding:utf-8 -*-
import time
import random
#冒泡排序
def bubble_sort(raw_list:list):
    #记录开始时间，用于计算排序时长
    start_time = time.time()*1000
    print('bubble_sort sorting start time: ', start_time)
    # print('raw_list : ', raw_list)
    raw_list_length = len(raw_list)
    #从第一个元素开始，一次遍历
    for i in range(1, raw_list_length):
        #i表示第i个选出的最大值，(i, raw_list_length)是依次已排序好的元素
        for j in range(0, raw_list_length - i):
            if raw_list[j] > raw_list[j+1]:
                raw_list[j], raw_list[j+1] = raw_list[j+1],raw_list[j]
   
    end_time = time.time()*1000
    print('bubble_sort sorting end time: ', end_time)
    # print('sorted_list : ', raw_list)
   
   
    print('bubble_sort耗费时长(MS): ', (end_time - start_time))
    print('------------------------------------------------------------')
#选择排序
def selection_sort(raw_list:list):
    #记录开始时间，用于计算排序时长
    start_time = time.time()*1000
    print('selection_sort sorting start time: ', start_time)
    # print('raw_list : ', raw_list)
    raw_list_length = len(raw_list)
    #从第一个元素开始，一次遍历；剩余最后一个元素的时候，肯定是最值，无需进一步处理
    for i in range(raw_list_length-1):
        min_index = i
        #（0,i）表示一次已经选择出来的最小值，不再重复看
        for j in range(i+1, raw_list_length):
            if raw_list[j] < raw_list[min_index]:
                min_index = j
           
            if i != min_index:
                raw_list[i], raw_list[min_index] = raw_list[min_index],raw_list[i]
    end_time = time.time()*1000
    print('selection_sort sorting end time: ', end_time)
    # print('sorted_list : ', raw_list)
   
   
    print('selection_sort(MS): ', (end_time - start_time))
    print('------------------------------------------------------------')
   
#插入排序
def insertion_sort(raw_list:list):
    #记录开始时间，用于计算排序时长
    start_time = time.time()*1000
    print('insertion_sort sorting start time: ', start_time)
    # print('raw_list : ', raw_list)
    raw_list_length = len(raw_list)
   
    for i in range(1, raw_list_length):
        #已排序和未排序分解点，索引标识；默认第1个元素是已经排序的，从第二个元素开始
        sorted_flag = i - 1
        #设置一个临时值，用于交换存储位置
        current_element = raw_list[i]    
        #扫描已经排序的序列，将新元素插入到合适的位置  
        while True:
            if (sorted_flag < 0):
                break
            #从排序序列的最大值开始对比，如果大于目标值，那么存储位置向后延续1位
            if raw_list[sorted_flag] > current_element:
                raw_list[sorted_flag + 1],raw_list[sorted_flag] = raw_list[sorted_flag],raw_list[sorted_flag + 1]
                sorted_flag -= 1
            #如果遇到了小于等于目标值的位置，那么直接将空闲值设置为当前值
            else:
                raw_list[sorted_flag + 1] = current_element
                break        
    end_time = time.time()*1000
    print('insertion_sort sorting end time: ', end_time)
    # print('sorted_list : ', raw_list)
   
   
    print('insertion_sort(MS): ', (end_time - start_time))
if __name__ == '__main__':
    #实例
    #输入参数生成
    raw_list1 = []
    raw_list2 = []
    raw_list3 = []
    for i in range(2000):
        raw_list1.append(i)
        raw_list2.append(i)
        raw_list3.append(i)
    random.shuffle(raw_list1)
    random.shuffle(raw_list2)
    random.shuffle(raw_list3)
    bubble_sort(raw_list1)
    selection_sort(raw_list2)
    insertion_sort(raw_list3)

2) 结果验证

PS D:\Shangouxuehui_Git\PythonAlgorithm-main> & D:/Python312/python.exe d:/Shangouxuehui_Git/PythonAlgorithm-main/sgxh_sort_1.py
bubble_sort sorting start time: 1712233752263.818
bubble_sort sorting end time: 1712233752399.7727
bubble_sort耗费时长(MS): 135.95458984375
------------------------------------------------------------
selection_sort sorting start time: 1712233752399.7727
selection_sort sorting end time: 1712233752516.7822
selection_sort(MS): 117.009521484375
------------------------------------------------------------
insertion_sort sorting start time: 1712233752516.7822
insertion_sort sorting end time: 1712233752597.4563
insertion_sort(MS): 80.674072265625

##山狗学会 License Start##

转载请注明出处，"今日头条"创作者"山狗学会“ ，注明出处即授权，未注明出处罚款100万元

主页链接：山狗学会主页

##山狗学会 License End##