python算法技巧——排序算法训练及讲解

素颜马尾好姑娘i 2023-09-29 05:56 19阅读 0赞

**目录**

一. 泡沫排序（bubble sort）

二. 鸡尾酒排序（cocktail sort）

三. 选择排序（selection sort）

四. 插入排序（insertion sort）

五. 堆积树排序（heap sort）

六. 快速排序（quick sort）

七. 合并排序（merge sort）

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

## 一. 泡沫排序**（bubble sort）** ##

> 在排序中最著名的也是最简单的算法就是**泡沫排序（bubble sort）**，也被称为**冒泡排序**或**气泡排序**，这个方法的**基本工作原理**是将相邻的数字做比较，如果前一个数字大于后一个数字，将彼此交换，这样经过一个循环后最大的数字会经由交换出现在最右边，数字移动过程中很像泡泡的移动，所以称为泡沫排序；

**1.1 代码如下：**

# 泡沫排序(bubble sort)-------------------------------------------------------------
    def bubble_sort(nlist):
        length = len(nlist)
        for i in range(length-1):
            print('第 '+str(i+1)+' 次循环')
            for j in range(length-1-i):
                if nlist[j] > nlist[j+1]:
                    nlist[j], nlist[j+1] = nlist[j+1], nlist[j]
                print('第 '+str(i+1)+' 次循环'+'第 '+str(j+1)+' 次内层排序:', nlist)
            print('\n')
        return nlist
    
    data = [42,62,4,26,98,6,1,27]
    print('原始列表：', data)
    print('排序后的列表：', bubble_sort(data))

**1.2 代码讲解**

> 下面跟大家一起走一遍排序的过程（**黑色代表比较不换位，红色代表比较后换位**）：

> 原始列表： \[42, 62, 4, 26, 98, 6, 1, 27\]

*  第 1 次循环

> 第 1 次循环第 1 次内层排序: \[**42, 62**, 4, 26, 98, 6, 1, 27\]  
> 第 1 次循环第 2 次内层排序: \[42, **4, 62**, 26, 98, 6, 1, 27\]  
> 第 1 次循环第 3 次内层排序: \[42, 4, **26, 62**, 98, 6, 1, 27\]  
> 第 1 次循环第 4 次内层排序: \[42, 4, 26, **62, 98**, 6, 1, 27\]  
> 第 1 次循环第 5 次内层排序: \[42, 4, 26, 62, **6, 98**, 1, 27\]  
> 第 1 次循环第 6 次内层排序: \[42, 4, 26, 62, 6, **1, 98**, 27\]  
> 第 1 次循环第 7 次内层排序: \[42, 4, 26, 62, 6, 1, **27, 98**\]

*  第 2 次循环

> 第 2 次循环第 1 次内层排序: \[**4, 42**, 26, 62, 6, 1, 27, 98\]  
> 第 2 次循环第 2 次内层排序: \[4, **26, 42**, 62, 6, 1, 27, 98\]  
> 第 2 次循环第 3 次内层排序: \[4, 26, **42, 62**, 6, 1, 27, 98\]  
> 第 2 次循环第 4 次内层排序: \[4, 26, 42, **6, 62**, 1, 27, 98\]  
> 第 2 次循环第 5 次内层排序: \[4, 26, 42, 6, **1, 62**, 27, 98\]  
> 第 2 次循环第 6 次内层排序: \[4, 26, 42, 6, 1, **27, 62**, 98\]

*  第 3 次循环

> 第 3 次循环第 1 次内层排序: \[**4, 26**, 42, 6, 1, 27, 62, 98\]  
> 第 3 次循环第 2 次内层排序: \[4, **26, 42**, 6, 1, 27, 62, 98\]  
> 第 3 次循环第 3 次内层排序: \[4, 26, **6, 42**, 1, 27, 62, 98\]  
> 第 3 次循环第 4 次内层排序: \[4, 26, 6, **1, 42**, 27, 62, 98\]  
> 第 3 次循环第 5 次内层排序: \[4, 26, 6, 1, **27, 42**, 62, 98\]

*  第 4 次循环

> 第 4 次循环第 1 次内层排序: \[**4, 26**, 6, 1, 27, 42, 62, 98\]  
> 第 4 次循环第 2 次内层排序: \[4, **6, 26**, 1, 27, 42, 62, 98\]  
> 第 4 次循环第 3 次内层排序: \[4, 6, **1, 26**, 27, 42, 62, 98\]  
> 第 4 次循环第 4 次内层排序: \[4, 6, 1, **26, 27**, 42, 62, 98\]

*  第 5 次循环

> 第 5 次循环第 1 次内层排序: \[**4, 6**, 1, 26, 27, 42, 62, 98\]  
> 第 5 次循环第 2 次内层排序: \[4, **1, 6**, 26, 27, 42, 62, 98\]  
> 第 5 次循环第 3 次内层排序: \[4, 1, **6, 26**, 27, 42, 62, 98\]

*  第 6 次循环

> 第 6 次循环第 1 次内层排序: \[**1, 4**, 6, 26, 27, 42, 62, 98\]  
> 第 6 次循环第 2 次内层排序: \[1, **4, 6**, 26, 27, 42, 62, 98\]

*  第 7 次循环

> 第 7 次循环第 1 次内层排序: \[**1, 4**, 6, 26, 27, 42, 62, 98\]

**1.3 算法分析**

>  泡沫排序的第一次循环的比较次数是n-1次，第二次循环的比较次数是n-2次，到n-1次循环的时候是1次，所以比较总次数计算方式为：(n-1)+(n-2)+···+1
> 
> 整体所需时间（时间复杂度）是O(![n^\{2\}][n_2])。

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

## 二. 鸡尾酒排序**（cocktail sort）** ##

> **鸡尾酒排序（cocktail sort）又称双向冒泡排序**，泡沫排序算法(冒泡排序)的概念是每次皆从左到右比较，每次循环比较n-1次，须执行n-1个循环。而**鸡尾酒排序法是泡沫排序法的改良**，会先从左到右比较，经过一个循环最右边可以得到最大值，同时此值将在最右边的索引位置，然后从次右边的索引从右到左比较，经过一个循环可以得到尚未排序的最小值，此值将在最左索引。然后接着再从下一个尚未排序的索引值往右比较，如此循环，当有一个循环没有更换任何值的位置是，就代表排序完成。

**2.1 代码如下：**

# 鸡尾酒排序(cocktail sort)-------------------------------------------------------------
    def cocktail_sort(nlist):
        n = len(nlist)
        is_sorted = True
        start = 0
        end = n-1
        time = 1
        while is_sorted:
            is_sorted = False
            for i in range(start, end):
                if nlist[i] > nlist[i+1]:
                    nlist[i], nlist[i+1] = nlist[i+1], nlist[i]
                    is_sorted = True
                print('第 '+str(time)+' 次往右排序'+'第 '+str(i+1-start)+' 次内层排序:', nlist)
            if not is_sorted:
                break
            print('\n')
    
            end -= 1
            for i in range(end-1, start-1, -1):
                if nlist[i] > nlist[i+1]:
                    nlist[i], nlist[i+1] = nlist[i+1], nlist[i]
                    is_sorted = True
                print('第 '+str(time)+' 次往左排序'+'第 '+str(end-i)+' 次内层排序:', nlist)
            start += 1
            time += 1
            print('\n')
        return nlist
    
    data = [42,62,4,26,98,6,1,27]
    print('原始列表：', data)
    print('排序后的列表：', cocktail_sort(data))

**2.2 代码讲解**

> 下面跟大家一起走一遍排序的过程（**黑色代表比较不换位，红色代表比较后换位**）：

> 原始列表： \[42, 62, 4, 26, 98, 6, 1, 27\]

*  第 1 次往右排序

> 第 1 次往右排序第 1 次内层排序: \[**42, 62**, 4, 26, 98, 6, 1, 27\]  
> 第 1 次往右排序第 2 次内层排序: \[42, **4, 62**, 26, 98, 6, 1, 27\]  
> 第 1 次往右排序第 3 次内层排序: \[42, 4, **26, 62**, 98, 6, 1, 27\]  
> 第 1 次往右排序第 4 次内层排序: \[42, 4, 26, **62, 98**, 6, 1, 27\]  
> 第 1 次往右排序第 5 次内层排序: \[42, 4, 26, 62, **6, 98,** 1, 27\]  
> 第 1 次往右排序第 6 次内层排序: \[42, 4, 26, 62, 6, **1, 98**, 27\]  
> 第 1 次往右排序第 7 次内层排序: \[42, 4, 26, 62, 6, 1, **27, 98**\]

*  第 1 次往左排序

> 第 1 次往左排序第 1 次内层排序: \[42, 4, 26, 62, 6, **1, 27**, 98\]  
> 第 1 次往左排序第 2 次内层排序: \[42, 4, 26, 62, **1, 6**, 27, 98\]  
> 第 1 次往左排序第 3 次内层排序: \[42, 4, 26, **1, 62**, 6, 27, 98\]  
> 第 1 次往左排序第 4 次内层排序: \[42, 4, **1, 26**, 62, 6, 27, 98\]  
> 第 1 次往左排序第 5 次内层排序: \[42, **1, 4**, 26, 62, 6, 27, 98\]  
> 第 1 次往左排序第 6 次内层排序: \[**1, 42**, 4, 26, 62, 6, 27, 98\]

*  第 2 次往右排序

> 第 2 次往右排序第 1 次内层排序: \[1, **4, 42**, 26, 62, 6, 27, 98\]  
> 第 2 次往右排序第 2 次内层排序: \[1, 4, **26, 42**, 62, 6, 27, 98\]  
> 第 2 次往右排序第 3 次内层排序: \[1, 4, 26, **42, 62**, 6, 27, 98\]  
> 第 2 次往右排序第 4 次内层排序: \[1, 4, 26, 42, **6, 62**, 27, 98\]  
> 第 2 次往右排序第 5 次内层排序: \[1, 4, 26, 42, 6, **27, 62**, 98\]

*  第 2 次往左排序

> 第 2 次往左排序第 1 次内层排序: \[1, 4, 26, 42, **6, 27**, 62, 98\]  
> 第 2 次往左排序第 2 次内层排序: \[1, 4, 26, **6, 42**, 27, 62, 98\]  
> 第 2 次往左排序第 3 次内层排序: \[1, 4, **6, 26**, 42, 27, 62, 98\]  
> 第 2 次往左排序第 4 次内层排序: \[1, **4, 6**, 26, 42, 27, 62, 98\]

*  第 3 次往右排序

> 第 3 次往右排序第 1 次内层排序: \[1, 4, **6, 26**, 42, 27, 62, 98\]  
> 第 3 次往右排序第 2 次内层排序: \[1, 4, 6, **26, 42**, 27, 62, 98\]  
> 第 3 次往右排序第 3 次内层排序: \[1, 4, 6, 26, **27, 42**, 62, 98\]

*  第 3 次往左排序

> 第 3 次往左排序第 1 次内层排序: \[1, 4, 6, **26, 27**, 42, 62, 98\]  
> 第 3 次往左排序第 2 次内层排序: \[1, 4, **6, 26**, 27, 42, 62, 98\]

*  第 4 次往右排序

> 第 4 次往右排序第 1 次内层排序: \[1, 4, 6, **26, 27**, 42, 62, 98\]

**2.3 算法分析**

> 到最后的循环中如果没有数据需要更新，代表排序完成，相较于泡沫排序如果循环没有更改任何值，可以省略循环。如果序列数据大都排好，时间复杂度可以使O(n)，不过平均是O(![n^\{2\}][n_2])。

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

## 三. 选择排序**（selection sort）** ##

> 所谓**选择排序（selection sort）**工作原理是从为排序的列表的序列中找最小数字，然后将此最小数字与最小索引位置的数字对调。然后从剩余的未排序数字汇总继续找寻最小数字，再将次最小数字与未排序的最小索引位置的数字对调。以此类推，直到所有数字完成从小到大排序。
> 
> 这个排序法在找寻最小数字时，是使用线性搜索。由于是线性搜寻，第1次循环执行是需要比较n-1次，第2次循环是比较n-2ci，其他依次类推，整个完成需要执行n-1次循环。

**3.1 代码如下：**

# 选择排序(selection sort)-------------------------------------------------------------
    def selection_sort(nlist):
        for i in range(len(nlist)-1):
            print('第', i+1, '次循环前列表：', nlist)
            index = i
            for j in range(i+1, len(nlist)):
                if nlist[index] > nlist[j]:
                    index = j
            if i == index:
                pass
            else:
                nlist[index], nlist[i] = nlist[i], nlist[index]
            print('第', i+1, '次循环后列表：', nlist)
            print('\n')
        return nlist
    
    data = [42,62,4,26,98,6,1,27]
    print('原始列表：', data)
    print('排序后的列表：', selection_sort(data))

**3.2 代码讲解**

> 下面跟大家一起走一遍排序的过程（**黑色代表已经排列好的序列，红色代表本次循环对调的数**）：

> 原始列表： \[42, 62, 4, 26, 98, 6, 1, 27\]

*  第 1 次循环

> 第 1 次循环前列表： \[**42**, 62, 4, 26, 98, 6, **1**, 27\]  
> 第 1 次循环后列表： \[**1**, 62, 4, 26, 98, 6, **42**, 27\]

*  第 2 次循环

> 第 2 次循环前列表： \[1, **62**, **4**, 26, 98, 6, 42, 27\]  
> 第 2 次循环后列表： \[**1**, **4**, **62**, 26, 98, 6, 42, 27\]

*  第 3 次循环

> 第 3 次循环前列表： \[1, 4, **62**, 26, 98, **6**, 42, 27\]  
> 第 3 次循环后列表： \[**1, 4,****6**, 26, 98, **62**, 42, 27\]

*  第 4 次循环

> 第 4 次循环前列表： \[1, 4, 6, **26**, 98, 62, 42, 27\]  
> 第 4 次循环后列表： \[**1, 4, 6,** **26**, 98, 62, 42, 27\]

*  第 5 次循环

> 第 5 次循环前列表： \[1, 4, 6, 26, **98**, 62, 42, **27**\]  
> 第 5 次循环后列表： \[**1, 4, 6, 26,** **27**, 62, 42, **98**\]

*  第 6 次循环

> 第 6 次循环前列表： \[1, 4, 6, 26, 27, **62**, **42**, 98\]  
> 第 6 次循环后列表： \[**1, 4, 6, 26, 27,** **42**, **62**, 98\]

*  第 7 次循环

> 第 7 次循环前列表： \[1, 4, 6, 26, 27, 42, **62, 98**\]  
> 第 7 次循环后列表： \[**1, 4, 6, 26, 27, 42,** **62, 98**\]

**3.3 算法分析**

> 选择排序第一次循环的线性搜寻最小值是比较n-1次，第二次循环是n-2次，到第n-1次循环的时候是1次，所以比较总次数与泡沫排序相同，计算方式为：(n-1)+(n-2)+···+1
> 
> 上述执行是每个循环将最小值与未排序的最小索引最多对调一次，整体所需时间（时间复杂度）是 O(![n^\{2\}][n_2])。

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

## 四. 插入排序（insertion sort） ##

> 这是一个直观的算法，从序列左边往右边排序，先讲左边的数字排序完成，再取右边未排序的数字，在已排序的序列中由右向左找对应的位置插入。

**4.1 代码如下：**

def insertion_sort(nlist):
        n = len(nlist)
        if n == 1:
            print('第', n, '次循环排序：', nlist)
            return nlist
        print('第1次循环排序：', nlist)
        for i in range(1,n):
            for j in range(i,0,-1):
                if nlist[j] < nlist[j-1]:
                    nlist[j], nlist[j-1] = nlist[j-1], nlist[j]
                else:
                    break
            print('第', i+1, '次循环排序：', nlist)
        return nlist
    
    data = [42,62,4,26,98,6,1,27]
    print('原始列表：', data)
    print('排序后的列表：', insertion_sort(data))

**4.2 代码讲解**

> 下面跟大家一起走一遍排序的过程（**黑色代表已经排列好的序列，红色代表本次循环插入的数**）：

> 原始列表： \[42, 62, 4, 26, 98, 6, 1, 27\]

*  第1次循环

> 第1次循环排序： \[**42**, 62, 4, 26, 98, 6, 1, 27\]

*  第 2 次循环

> 第 2 次循环排序： \[**42,** **62**, 4, 26, 98, 6, 1, 27\]

*  第 3 次循环

> 第 3 次循环排序： \[**4****, 42, 62**, 26, 98, 6, 1, 27\]

*  第 4 次循环

> 第 4 次循环排序： \[**4,** **26****, 42, 62**, 98, 6, 1, 27\]

*  第 5 次循环

> 第 5 次循环排序： \[**4, 26, 42, 62,** **98**, 6, 1, 27\]

*  第 6 次循环

> 第 6 次循环排序： \[**4,** **6****, 26, 42, 62, 98**, 1, 27\]

*  第 7 次循环

> 第 7 次循环排序： \[**1****, 4, 6, 26, 42, 62, 98**, 27\]

*  第 8 次循环

> 第 8 次循环排序： \[**1, 4, 6, 26,** **27****, 42, 62, 98**\]

**4.3 算法分析**

> 插入排序的原则是将去取出的值与索引左边的值作比较，如果左边的值比较小就不必对调，此循环就算结束。
> 
> 这种循环最不好的情况是第2次循环比较1次、第三次循环比较2次、······、第n次循环比较n-1次，所需运行时间（时间复杂度）与泡沫排序及选择排序相同，为 O(![n^\{2\}][n_2])。

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

## **五. 堆积树排序（heap sort）** ##

>  **堆排序(Heap sort)**是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。堆分为大根堆和小根堆，是完全二叉树。

**5.1 代码如下：**

class Heaptree():
        def __init__(self):
            self.heap = []
            self.size = 0
    
        def data_down(self, i):
            while (i*2+2) <= self.size:
                mi = self.get_min_index(i)
                if self.heap[i] > self.heap[mi]:
                    self.heap[i], self.heap[mi] = self.heap[mi], self.heap[i]
                i = mi
    
        def get_min_index(self, i):
            if i*2+2 >=self.size:
                return i*2+1
            else:
                if self.heap[i*2+1] < self.heap[i*2+2]:
                    return i*2+1
                else:
                    return i*2+2
    
        def build_heap(self, mylist):
            i = (len(mylist)//2)-1
            self.size = len(mylist)
            self.heap = mylist
            while(i>=0):
                self.data_down(i)
                i = i-1
    
        def get_min(self):
            min_ret = self.heap[0]
            self.size -= 1
            self.heap[0] = self.heap[self.size]
            self.heap.pop()
            self.data_down(0)
            return min_ret
    
    data = [42,62,4,26,98,6,1,27]
    print('原始列表：', data)
    obj = Heaptree()
    obj.build_heap(data)
    print('形成堆积树后的列表：',obj.heap)
    sort_h = []
    for i in range(len(data)):
        sort_h.append(obj.get_min())
        print('第', i+1, '次取出堆积树最小值后的列表：', sort_h)

**5.2 代码讲解**

> 原始列表： \[42, 62, 4, 26, 98, 6, 1, 27\]

> 形成堆积树后的列表： \[1, 26, 4, 27, 98, 6, 42, 62\]

>  *  第 1 次取出堆积树最小值后的列表： \[1\]
>  *  第 2 次取出堆积树最小值后的列表： \[1, 4\]
>  *  第 3 次取出堆积树最小值后的列表： \[1, 4, 6\]
>  *  第 4 次取出堆积树最小值后的列表： \[1, 4, 6, 26\]
>  *  第 5 次取出堆积树最小值后的列表： \[1, 4, 6, 26, 27\]
>  *  第 6 次取出堆积树最小值后的列表： \[1, 4, 6, 26, 27, 42\]
>  *  第 7 次取出堆积树最小值后的列表： \[1, 4, 6, 26, 27, 42, 62\]
>  *  第 8 次取出堆积树最小值后的列表： \[1, 4, 6, 26, 27, 42, 62, 98\]

**5.3 算法分析**

> 插入数据到堆积树和去除最小堆积树的值，时间复杂度都是O(![\\log n][log n])。其实我们可以使用不断取出最小堆积树的最小值的方式，达到排序的目的，时间复杂度是O(![n\\log n][n_log n])。

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

## **六. 快速排序（quick sort）** ##

>  **快速排序法的步骤为：**
> 
>  *  从数列中挑选**基准值**（pivot）；
>  *  重新排列数据，将所有比基准值小的排在基准值左边，所有比基准值大的牌在基准值的右边，如果与基准值相同可以排到任意一边；
>  *  **递归式**针对两边子序列做相同排序；
> 
> （注：当步骤2当一边的序列数量是0或1，则表示改编的序列已经完成排序）

**6.1 代码如下：**

import random
    
    def quick_sort(nlist):
        if len(nlist) <= 1:
            return nlist
        
        left = []
        right = []
        piv = []
        pivot = random.choice(nlist)
        for val in nlist:
            if val == pivot:
                piv.append(val)
            elif val < pivot:
                left.append(val)
            else:
                right.append(val)
        return quick_sort(left)+piv+quick_sort(right)
    
    data = [42,62,4,26,98,6,1,27]
    print('原始列表：', data)
    print('排序后的列表：', quick_sort(data))

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

## 七. 合并排序（merge sort） ##

> 合并排序算法的精神是分治法（devide and conquer），主要是先将欲排列的序列分割（divide）成几乎等长的两个序列，这个动作重复chulzhidao序列只剩下一个数字无法再分割。接着合并（conquer）被分割的数列，主要将已排序最小单位的数列开始合并，重复处理，知道合并为与原数列相同大小的一个数列。

**7.1 代码如下：**

def merge(left, right):
        output = []
        while left and right:
            if left[0] <= right[0]:
                output.append(left.pop(0))
            else:
                output.append(right.pop(0))
        if left:
            output += left
        if right:
            output += right
        return output
    
    def  merge_sort(nlist):
        if len(nlist) <= 1:
            return nlist
        mid = len(nlist)//2
    
        left = nlist[:mid]
        right = nlist[mid:]
    
        left = merge_sort(left)
        right = merge_sort(right)
    
        return merge(left, right)
    
    data = [42,62,4,26,98,6,1,27]
    print('原始列表：', data)
    print('排序后的列表：', merge_sort(data))

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

## **算法技巧专栏**  ##

[https://blog.csdn.net/weixin\_53919192/category\_11761989.html![icon-default.png?t=M3K6][icon-default.png_t_M3K6]https://blog.csdn.net/weixin\_53919192/category\_11761989.html][https_blog.csdn.net_weixin_53919192_category_11761989.html_icon-default.png_t_M3K6_icon-default.png_t_M3K6_https_blog.csdn.net_weixin_53919192_category_11761989.html]

[n_2]: https://latex.csdn.net/eq?n%5E%7B2%7D
[log n]: https://latex.csdn.net/eq?%5Clog%20n
[n_log n]: https://latex.csdn.net/eq?n%5Clog%20n
[icon-default.png_t_M3K6]: https://csdnimg.cn/release/blog_editor_html/release2.1.0/ckeditor/plugins/CsdnLink/icons/icon-default.png?t=M3K6
[https_blog.csdn.net_weixin_53919192_category_11761989.html_icon-default.png_t_M3K6_icon-default.png_t_M3K6_https_blog.csdn.net_weixin_53919192_category_11761989.html]: https://blog.csdn.net/weixin_53919192/category_11761989.html