
"""
作者：佩大奇
日期：2022/03/05/
描述：冒泡排序：n个元素的排序需要走n-1趟循环，每一趟都能确定一个有序元素，无序元素会减少一个，直到n-1次后，n个元素去拿不变成有序的
new_knowledge:生成随机数：import random      li=[random.randint(0,1000) for i in range(1000)]
"""
#这是升序
def bubble_ascending_order(li):
    for n in range(len(li)-1):#趟数
       exchange=False
       for i in range(len(li)-n-1):#无序区范围
           if li[i] > li[i+1]:
                li[i], li[i+1] = li[i+1], li[i]
                exchange=True
             # tem=li[i]
             # li[i]=li[i+1]
             # li[i+1]=tem
       # 或者 if  exchange == False:
       #     print("排序完成,列表是个有序序列")
       #     break
       if not exchange:#避免中途列表已经排序完成依然进行循环排序
           print("排序完成，列表是个有序列表")
           break
       print(li)
    print("--------该列表冒泡排序升序的结果为：-------")
    print(li)
 
 
 
#这是降序
def bubble_Descending(li):
    for n in range(len(li)-1):
        exchange=False
        for i in range(len(li)-n-1):
            if li[i]<li[i+1]:
                li[i] , li[i+1] = li[i+1] , li[i]
                exchange=True
        if not exchange:
           print("排序完成，列表是个有序列表")
           break
        print(li)
    print("该列表降序的结果为：")
    print(li)
 
print("请输入列表元素:")
li=list(input().split())
for i in range(len(li)):
    li[i]=int(li[i])
print("你输入的列表为：")
print(li)
print("通过冒泡排序，该列表的升序的过程为：")
 
bubble_ascending_order(li)
 
print()
print("----------------------------------------")
print("该列表冒泡排序降序的过程为：")
bubble_Descending(li)

选择排序（Select Sort)

选择排序：每一趟查找都能找到一个列表中的最小值，一趟排序记录最小的数，并且将其放到第一个位置，经过k趟查找，找到的k个最小的元素在列表的前k 个位置中是有序的
算法关键点：
- 有序区：经过k次遍历查找，找到的k个最小的元素，会在列表的前k个位置形成有序区
- 无序区：对于n个元素的列表中，经过k次遍历查找，找到的k个最小的元素后面的元素（n-k）个元素就是无序区
- 无序区的开始位置：经过k次遍历查找，找到的k个最小的元素，那么第k+1就是无序区的开始位置
选择排序的时间复杂度是O(n²）

选择排序代码如下：


"""
作者：佩大奇
日期：2022/03/05/
描述：选择排序：每遍历一次都能找到一个最小的值，每次查找后，将最小值放在第一位，第二个最小值放在第二位，以此类推
例子：查找最小的k个元素
"""
def select(li):
   print("请输入你要查找的元素个数")
   n=int(input())
   if n >len(li):
       print("你要查找的元素个数有误")
   else:
       for i in range(len(li)-1):#无序区的开始位置(范围就是整个列表）
           # 因为每一趟都能查找到一个最小的数，那么最后一趟就不需要遍历了，
           # 因为最后一趟就只有一个元素，那么就是只有一个元素了，就是最大的，使用可以不需要遍历判断它
           for j in range(i+1,len(li)):#每次遍历查找都是从无序区（就是i+1）开始，也可以和i开始，因为python中的区间是前闭后开的，所以如果从i开始就是i和i进行比较（因为此时的j==i)
               #每一次查找都需要将每个元素进行对比
               if li[i] > li[j]:
               #假设最小数是无序区的开始i位置，然后无序区的开始位置与后面的无序区元素相互比较，然后后面的有比开始位置小的元素，那么和无序区开始位置相互交换
               #当满足需要查找最小元素的个数时，则停止循环结束，后面即使有一样的元素也不管，因为只需要查找k个最小元素
                   # min=li[j]
                   li[i] ,li[j] = li[j] , li[i]
           # print("----第",end="")
           # print(i,end="")
           # print("边查找，找到的最小的元素是：",end="")
           # print(min)
           print(li)#输出每次选择排序的过程
       print("选择排序后的列表:")
       print(li)
       print("查找到列表中最小的",end="")
       print(n,end="")
       print("个元素分别为：",end="")
       print("[",end="")
       for m in range(n):#遍历输出查找到的最小的k个元素，就是输出有序区的元素
           print(li[m],end="  ")
       print("]")
 
 
print("请输入你的列表，元素间用空格隔开：")
li=list(input().split())
for i in range(len(li)):
    li[i]=int(li[i])
print("你输入的列表为：")
print(li)
select(li)

插入排序(Insert Sort)

插入排序：插入排序的过程是相当于抽扑克牌然后在原来已拥有的扑克牌中将其按从大到小（或者从小到大）的顺序插入。
过程描述：对于一个列表中，已经拥有的扑克牌是个有序序列，默认为列表中第一个位置是有序序列，从第二个位置开始到列表的最后一个位置是无序序列，因此默认抽取的扑克牌是第二个位置开始的，然后将抽出的扑克牌和已经拥有的所有扑克牌做比较，当有序区中的元素大于抽出的扑克牌时，则将大于抽出的扑克牌的有序区的元素向后（右）移动一个位置，当有序区的某个元素小于抽出的扑克牌元素时，那么抽出的扑克牌元素将插入到这个小于它的元素的后一个位置（即它的右边），然后依次类推，直到将列表中无序区的全部元素抽取并且插入，使列表成为有序序列为止则结束循环。
注意：抽出的扑克牌要插入成为有序区的元素时，它才属于已拥有的扑克牌
插入排序的时间复杂度是O(n²）

插入排序的代码如下：


"""
作者：佩大奇
日期：2022/03/06/
描述：插入排序:相当于扑克牌的插牌。
    无序区的元素i和有序区的元素比较，无序区开始位置的元素和有序区的所有元素比较,
    当无序区的开始位置比有序区中的某个元素小时，那么在所有比无序区开始元素大的有序区元素都向后移动一位,
    其中移动范围是有序区中的某个元素比无序区中的开始位置的元素小的位置的后一位开始到无序区的开始位置,
"""
def insert(li):
    for i in range(1,len(li)):#从无序区遍历
        j=i-1#i可以表示为前i张排，那么第i张开始是抽牌（即无序区），那么减1就是表示减去第i张就是无序区的排（抽牌），即有序区的范围遍历
        temp = li[i]
        while j>-1 and li[j]>temp:
            #这里不能是li[j]>li[i],因为有序区和每一次的li[i]判断是，都不是一开始无序区的li[i]
            #应为i是要每一次有序区循环判断一次后才会改变值，因此在有序区判断过程中i是固定的，使用每一次判断的值都有误，只有temp在有序区
            #判断过程是永远保持不变的，插入时导入也是原来无序区的li[i]
            li[j+1]=li[j]
            j=j-1
        else:
            li[j+1]=temp
        print("插入排序的过程为：",end="")
        print(li)
    print("-----------------------------------------")
    print("插入排序的结果为：",end="")
    print(li)
 
print("请输入你列表中的元素,用空格隔开：")
li=list(input().split())
for i in range(len(li)):
    li[i]=int(li[i])
print("你输入的列表是：",end="")
print(li)
print("------插入排序结果和过程-------")
insert(li)

快速排序（Quick Sort)

思路：依据一个“中值”数据项来把数据表分成两半，小于中值的一半和大于中值的一半，然后每部分分别进行快速排序（递归）
快速排序的时间复杂度是O(nlogn)
快速排序的问题：
- 最坏的情况：有一部分没有数据，那么时间复杂度就是O(n²）
- 递归
快速排序的特点：快、原地排序（不需要额外的存储空间）
快速排序实现过程图：

快速排序代码如下：


"""
作者：佩大奇
日期：2022/03/09/
描述：快速排序
"""
def partition(li,left,right):
     i = left
     j = right
     if  i < j:#前提
         temple = li[left]
         while i < j:#循环次数
             while i < j and li[j] > temple:
                 j -=1
             if i < j :#避免第n次调用途中right全部值都小于temple,直到超过i的值才有小于temple的值
                 li[i] = li[j]
                 i +=1
             while i < j and li[i] < temple:
                 i +=1
             if i < j:
                 li[j]=li[i]
                 j -=1
         li[i]=temple
         partition(li,left,i-1)#递归调用
         partition(li,i+1,right)
 
 
li=[i for i in range(20)]
import random
random.shuffle(li)
print("随机生成的列表是：",end="")
print(li)
partition(li,0,len(li)-1)
print("快速排序的结果：",end="")
print(li)

堆排序（Heap Sort)

树的基础知识：
- 树是一种数据结构，比如目录结构
- 树是一种可以递归定义的数据结构
- 树是由n个节点组成的集合：
  - 如果n=0，那么这是一棵空树
  - 如果n>0，那存在1个节点作为树的根节点，其他节点可以分为m个集合，每个集合本身又是一棵树
  - 如下图，下面每一个框块都是一棵树（A的子树）：其中A是根节点，其他都是A的子节点
树的基本概念
- 根节点：在一棵树里，节点是由A组成的节点，那么A就是节点
- 叶子节点：没有子节点的节点称为叶子节点
- 树的深度（高度）：树的层数
- 树的度：节点的子节点的个数。一棵树的度，就是根节点子节点的个数
- 孩子节点/父节点
- 子树：一棵树里某个子节点和该子节点的子节点组成的树
- 如下图解释：
二叉树：度不超过2的树（即每个节点最多有2个子节点的树），连个子节点被区分成左孩子节点和右孩子节点
- 如图所示：
满二叉树：一个二叉树，如果每一个层的节点数都达到最大值，则这个二叉树就是满二叉树
- 如下图，是一个满二叉树
完全二叉树：叶节点只能出现在最下层和次下层，并且最下面一层的节点都集中在该层最左边的若干位置的二叉树
- 如图，是一个完全二叉树
二叉树的存储方式（表示方式）：
- 链式存储方式
- 顺序存储方式（使用列表）
堆的基本概念
堆的时间复杂度使O(nlogn)
堆是一种特殊的完全二叉树，分为大根堆和小根堆两类：
- 大根堆：一棵完全二叉树，满足任一节点都比其孩子节点大（父大子小）
- 小根堆：一个完全二叉树，满足任一节点都比其孩子节点小（父小子大）
- 例子如下图
右（左）孩子 i 节点找父节点,则父节点是(i-1)//2
父节点 i 找左孩子节点，则左孩子节点是2*i+1
堆的节点在列表中的位置如图：
使用堆排序的前提要是堆，不是堆要先建立堆
- 建堆的方法：
  - 堆的向下调整：自身不是堆时，当根节点的左右子树都是堆时，可以通过一次向下的调整来将其变换成一个堆
堆排序的演示过程：
- 每次用最后一个节点放上根节点的位置，然后使用建堆的方法即使用堆的向下调整方法，使树成为大根堆或小根堆，重复使用该方法，让树中最大的值由大到小的顺序被放进列表中，这种过程成为堆排序
- 过程如图：
- 堆排序详细过程：
1. 建立堆（构建堆）：
  1. 如图所示：从最底层的最后一个小框开始重新按大根堆或小根堆的方式摆放
2. 得到堆顶的元素，为最大元素
3. 去掉堆顶，将堆最后一个元素放到堆顶，此时可通过一次调整重新使堆有序
4. 堆顶元素为第二大元素
5. 重复步骤，直到堆变空

堆排序代码如下（不使用递归）：


"""
作者：佩大奇
日期：2022/03/09/
描述：堆排序(不使用递归）
     堆排序主要使先建立堆，然后通过挨个出数的方法进行堆排序
"""
def sift(li,low,height):
    i=low#i移动父节点指针,一开始位于堆顶
    j=2*i+1#j移动子节点指针
    temp=li[low]#存放堆顶元素
    while j <=height:#针对于一棵二叉树而言，每次调整是针对一个子树，多个子树组成一棵二叉树
        if j+1 <=height and li[j] <li[j+1]: #j+1<=height说明有右孩子，li[j]<li[j+1]说明右孩子大于左孩子
            j=j+1 #j指针移向右孩子
        if li[j] >temp:
            li[i]=li[j]#把li[j]的值赋值给li[i]
            i=j#i指针移动下一层，即i指针移动至刚刚赋值后空缺位置的那一层
            j=2*i+1#j指针移动下一层
        else:
            li[i]=temp#当j指向的值比temp小的时候，则temp继续赋值i位置，这仅是针对于一棵子树而言
            break
    li[i]=temp   #当j>height时候，那么说明也不存在比temp小的值
 
def heap(li):
    n=len(li)-1#节点个数
    #1.先建堆
    for i in range((n-1)//2,-1,-1):#这里是走父节点
        sift(li,i,n)#这里的height最后一个节点是n，是因为不管是哪棵子树，只有他有孩子，
        # 那么他的孩子下标一定小于等于height，如果不存在孩子，那么j到下一层时候j的值就会超过height，只要超过了height就说明他没有孩子
    print("建立堆的结果：",end="")
    print(li)
 
    #2.挨个出数，成为有序序列
    for i in range(n,-1,-1):#这里的出数是对于所有节点而言的，因此开始是n,结束是左后一个元素，因为出数的过程是将堆顶元素（最大的值）和
        #最后一个元素交换，然后height界限向前移动，因为，最后相当于将最大值有后往前放，因此交换最后一个元素，
        li[0] , li[i] =li[i] , li[0]
        sift(li,0,i-1)#这里调用调整函数sift(),height就是i-1,使每一次最大值放后面后，height就往前移动，往前移动后，刚刚的最大值位置就不属于堆里的内容了
    print("堆排序的结果：",end="")
    print(li)
 
 
li=[i for i in range(10)]
import  random
random.shuffle(li)
print(li)
heap(li)

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/AllinToyou/article/detail/407430