排序算法

算法代码

插入排序
- 直接插入
  - 原理
    
    每次从无序表中取出第一个元素，把它插入到有序表的合适位置，使有序表仍然有序。具体方法是第一趟比较前两个数，然后把第二个数按大小插入到有序表中；第二趟把第三个数据与前两个数从前向后扫描，把第三个数按大小插入到有序表中；依次进行下去，进行了(n-1)趟扫描以后就完成了整个排序过程。
  - 示例
    
    待排序数组：{6, 5, 3, 1, 8, 7, 2, 4, 9, 0}
    
    i=1： 5 {5, 6, 3, 1, 8, 7, 2, 4, 9, 0}
    
    i=2： 3 {3, 5, 6, 1, 8, 7, 2, 4, 9, 0}
    
    i=3： 1 {1, 3, 5, 6, 8, 7, 2, 4, 9, 0}
    
    i=4： 8 {1, 3, 5, 6, 8, 7, 2, 4, 9, 0}
    
    i=5： 7 {1, 3, 5, 6, 7, 8, 2, 4, 9, 0}
    
    i=6： 2 {1, 2, 3, 5, 6, 7, 8, 4, 9, 0}
    
    i=7： 4 {1, 2, 3, 4, 5, 6, 7, 8, 9, 0}
    
    i=8： 9 {1, 2, 3, 4, 5, 6, 7, 8, 9, 0}
    
    i=9： 0 {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
  - Python3实现
```
 # 直接插入排序
 def Insert(listdata):
     for i in range(1, len(listdata)):
         # 设置当前值前一个元素的标识
         j = i - 1
         # 如果当前值小于前一个元素,则将当前值作为一个临时变量存储,将前一个元素后移一位
         if listdata[i] < listdata[j]:
             temp, listdata[i] = listdata[i], listdata[j]
             # 继续往前寻找,如果有比临时变量大的数字,则后移一位,直到找到比临时变量小的元素或者达到列表第一个元素
             j = j - 1
             while j >= 0 and listdata[j] > temp:
                 listdata[j + 1] = listdata[j]
                 j = j - 1
             # 将临时变量赋值给合适位置
             listdata[j + 1] = temp
     return listdata
```
- 希尔
  - 原理
    
    将待排序列划分(根据增量或者步长)为若干组，在每一组内进行插入排序，以使整个序列基本有序，然后再对整个序列进行插入排。增量的选取会影响算法的时间复杂度。
  - 示例：
    
    待排序数组：{6, 5, 3, 1, 8, 7, 2, 4, 9, 0}
    
    第一次步长h=4,那么数组按照步长可以拆分成4个小数组（[0]6的意思是下标[0]的值为6）
    
    {[0]6, [4]8, [8]9}， {[1]5, [5]7, [9]0}， {[2]3, [6]2}， {[3]1, [7]4}
    
    对这4个小数组分别进行插入排序后，4个小数组变成：
    
    {[0]6, [4]8, [8]9}， {[1]0, [5]5, [9]7}， {[2]2, [6]3}， {[3]1, [7]4}，
    
    合并起来就是：{6, 0, 2, 1, 8, 5, 3, 4, 9, 7}
    
    第二次步长h=1,那么数组按照步长只有1个数组了
    
    {6, 0, 2, 1, 8, 5, 3, 4, 9, 7}
    
    对这个数组进行一次插入排序后，最终顺序就成为：
    
    {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
  - Python3实现
```
# 希尔排序
def Shell(listdata):
    n = len(listdata)
    # 希尔增量
    gap = int(n / 2)
    while gap > 0:
        # 按增量进行直接插入排序
        for i in range(gap, n):
            j = i
            # 直接插入排序
            while j >= gap and listdata[j - gap] > listdata[j]:
                listdata[j - gap], listdata[j] = listdata[j], listdata[j - gap]
                j -= gap
        # 得到新的增量
        gap = int(gap / 2)
    return listdata
```
选择排序
- 直接选择
  - 原理
    
    从待排序序列中，找到关键字最小的元素；如果最小元素不是待排序序列的第一个元素，将其和第一个元素互换；从余下的 N - 1 个元素中，找出关键字最小的元素，重复1，2步，直到排序结束。
  - 示例
    
    待排序数组：{6, 5, 3, 1, 8, 7}
    
    i=1： {1, 5, 3, 6, 8, 7} 最小值1，交换6和1
    
    i=2： {1, 3, 5, 6, 8, 7} 最小值3，交换5和3
    
    i=3： {1, 3, 5, 6, 8, 7} 最小值5，无需交换
    
    i=4： {1, 3, 5, 6, 8, 7} 最小值6，无需交换
    
    i=5： {1, 3, 5, 6, 7, 8} 最小值7，交换7和8
    
    i=6： {1, 3, 5, 6, 7, 8} 最小值8，无需交换，结束排序
  - Python3实现
```
# 直接选择排序
def Select(listdata):
    for i in range(len(listdata) - 1):
        minnum = i
        for j in range(i + 1, len(listdata)):
            if listdata[j] < listdata[minnum]:
                minnum = j
        listdata[i], listdata[minnum] = listdata[minnum], listdata[i]
    return listdata
```
- 堆
  - 原理
    
    堆分为最大堆和最小堆，其实就是完全二叉树。最大堆：父节点的值都不小于子节点的值，最小堆：父节点的值都不大于子节点的值。每次都取堆顶的元素，将其放在序列最后面，然后将剩余的元素重新调整为最大堆(升序)或者最小堆(降序)，依次类推，最终得到排序的序列。
    
    1，将初始待排序关键字序列(R1,R2....Rn)构建成大顶堆，此堆为初始的无序区；
    
    2，将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,......Rn-1)和新的有序区(Rn)；
    
    3，由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,......Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2....Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成；
  - 示例
    
    待排序数组{7, 13, 2, 9, 15}，升序
    1. 生成最大堆
    1. 互换——生成最大堆重复操作
    排序结果{2, 7, 9, 13, 15}
  - Python3实现
```
 # 堆排序
 def adjust_heap(lists, i, size):
     lchild = 2 * i + 1
     rchild = 2 * i + 2
     max = i
     if i < size / 2:
         if lchild < size and lists[lchild] > lists[max]:
             max = lchild
         if rchild < size and lists[rchild] > lists[max]:
             max = rchild
         if max != i:
             lists[max], lists[i] = lists[i], lists[max]
             adjust_heap(lists, max, size)
 
 # 创建堆
 def build_heap(lists, size):
     for i in range(0, (int(size/2)))[::-1]:
         adjust_heap(lists, i, size)
 
 # 堆排序
 def Heap(lists):
     size = len(lists)
     build_heap(lists, size)
     for i in range(0, size)[::-1]:
         lists[0], lists[i] = lists[i], lists[0]
         adjust_heap(lists, 0, i)
     return lists
```

交换排序

冒泡

原理

临近的数字两两进行比较,按照从小到大或者从大到小的顺序进行交换,这样遍历过一次数组后,最大或最小的数字被交换到了最后一位,然后再从头开始进行两两比较交换,直到倒数第二位时结束排序。

示例

待排序数组{8，6，9，3}，升序

第一次遍历(外循环)

  第1次两两比较8 > 6，需要交换(内循环)：交换前状态{8，6，9，3}交换后状态{6，8，9，3}
  
  第2次两两比较8 < 9，不需要交换(内循环)：状态{6，8，9，3}
  
  第3次两两比较9 > 3，需要交换(内循环)：交换前状态{6，8，9，3}交换后状态{6，8，3，9}
  
  **结束比较**

第二次遍历(外循环)

  第1次两两比较6 < 8，不需要交换(内循环)：状态{6，8，3，9}
  
  第2次两两比较8 > 3，需要交换(内循环)：交换前状态{6，8，3，9}交换后状态{6，3，8，9}
  
  **结束比较**

第三次遍历(外循环)

  第1次两两比较6 > 3，需要交换(内循环)：交换前状态{6，3，8，9}交换后状态{3，6，8，9} 
  
  **结束比较**

第四次遍历(外循环)

 **无交换，结束内循环**

结束外循环遍历，排序结束

Python3实现

# 冒泡排序
def Bubble(listdata):
    for i in range(len(listdata) - 1):  # 这个循环负责设置冒泡排序进行的次数
        for j in range(len(listdata) - i - 1):  # ｊ为列表下标
            if listdata[j] > listdata[j + 1]:
                listdata[j], listdata[j + 1] = listdata[j + 1], listdata[j]
    return listdata

快速

原理

先从数列中取出一个数作为基准数，分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边，再对左右区间重复第二步，直到各区间只有一个数

示例

待排序数组：{4, 5, 3, 1, 7, 6, 2}

第1次

 **基准数=6**，首先，用两个变量 i 和 j 从数组两边开始向中间扫描，i 向右走，j 往左走
            
            i 往右走，直到遇见不小于基准数的值停止移动 5 
            
            j 向左走，直到遇见不大于基准数的值停止移动 2
            
            交换两个值的位置 {4, 2, 3, 1, 7, 6, 5}
            
            i,j继续：i停在1，j和i相遇，停止移动，1和基准数互换位置。{1, 2, 3, 4, 7, 6, 5}

第2次

 待排序数组：同样操作

 {1, 2, 3} 基准数1  

 {7, 6, 5} 基准数7

Python3实现

# 快速排序
def Quick(listdata):
    if len(listdata) == 0:
        return []
    pivots = [x for x in listdata if x == listdata[0]]
    lesser = Quick([x for x in listdata if x < listdata[0]])
    greater = Quick([x for x in listdata if x > listdata[0]])
    return lesser + pivots + greater

归并排序

归并

原理

该算法采用经典的分治(divide-and-conquer)策略，将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之。

示例

待排序数组：{4, 5, 3, 1, 7, 6, 2, 9}

分

         {4, 5, 3, 1}         |          {7, 6, 2, 9} 
         
    {4, 5}        {3, 1}      |     {7, 6}         {2, 9} 
    
  {4}   {5}      {3}   {1}    |    {7}    {6}      {2}    {9}

治

  {4, 5}        {1, 3}        |   {6, 7}         {2, 9} 
  
        {1, 3, 4, 5}          |       {2, 6, 7, 9}

排序结果：{1, 2, 3, 4, 5, 6, 7, 9}

Python3实现

 # 归并排序
 def Merge(listdata):
     n = len(listdata)
 
     if n == 1:
         return listdata
     mid = n // 2
 
     # 对分割的左半部分进行归并排序
     leftdata = Merge(listdata[:mid])
     # 对分割的右半部分进行归并排序
     rightdata = Merge(listdata[mid:])

     # 对排序之后的两部分进行合并
     # 定义两个游标
     left, right = 0, 0
 
     merge_result_li = []
     left_n = len(leftdata)
     right_n = len(rightdata)
 
     while left < left_n and right < right_n:
         if leftdata[left] <= rightdata[right]:
             merge_result_li.append(leftdata[left])
             left += 1
         else:
             merge_result_li.append(rightdata[right])
             right += 1
 
     merge_result_li += leftdata[left:]
     merge_result_li += rightdata[right:]

     # 将合并后的结果返回
     return merge_result_li

分配排序

基数

原理

基数排序（以整形为例），将整形10进制按每位拆分，然后从低位到高位依次比较各个位。主要分为两个过程：分配，先从个位开始，根据个位值(0-9)分别放到0至9号桶中（比如53,个位为3，则放入3号桶中)；收集，再将放置在0至9号桶中的数据按顺序放到数组中。从最低位到最高位重复分配与收集过程。
示例

待排序数组：{4561, 349, 78, 12, 201, 9, 3208}

个位

分配

 0：
 1：4561, 201
 2：12
 3：
 4：
 5：
 6：
 7：
 8：78, 3208
 9：349, 9

收集

 4561, 201, 12, 78, 3208, 349, 9

十位

分配

 0：201, 3208, 9
 1：12
 2：
 3：
 4：349
 5：
 6：4561
 7：78
 8：
 9：

收集

 201, 3208, 9, 12, 349, 4561, 78

百位

分配

 0：9, 12, 78
 1：
 2：201, 3208
 3：349
 4：
 5：4561
 6：
 7：
 8：
 9：

收集

 9, 12, 78, 201, 3208, 349, 4561

千位

分配

 0：9, 12, 78, 201, 349
 1：
 2：
 3：3208
 4：4561
 5：
 6：
 7：
 8：
 9：

收集

 9, 12, 78, 201, 349, 3208, 4561

Python3实现

# 基数排序
def Radix(listdata):
    k = len(str(max(listdata)))  # k获取最大位数
    for k in range(k):  # 遍历位数，从低到高
        s = [[] for i in range(10)]  # 生成存放数的十个桶
        for i in listdata:  # 遍历元素
            s[i // (10 ** k) % 10].append(i)  # 分配
        listdata = [a for b in s for a in b]  # 收集
    return listdata

回到顶部

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

排序算法

FilesExpand file tree

2排序算法.md

Latest commit

History

2排序算法.md

File metadata and controls

排序算法