python三个数从小到大排序3.7 比较中间数

来源：蜘蛛抓取(WebSpider) 时间：2018-08-04 16:28 标签： python三个数从小到大排序

算法是程序的灵魂,而排序算法 是算法的入门经典,作者在此用python三个数从小到大排序亲自实现了7种主流的排序算法,并做简短的说明.

将列表中最大数与最小数之间的数全部做成標签,贴到N个桶上
将每个元素放到对应值的桶里面(如果有M个相同的元素值,则将M个元素全部放到相应的桶中,取的时候占用M个位置)
最后按照桶编號的先后顺序,从桶中依次取出值,排列完成

1.设置游标,游标带领第一个元素开始,与右侧元素(第1个元素)比较,如果大于右侧元素,则二者交换数值,然後游标带领元素继续向右移动如果小于右侧元素,则不进行交换，游标继续向右移动当游标移动到列表最右侧，第一轮比较就完成了（囲比较N-1次）
2.然后游标回到起始位置开始第二轮比较，由于最后一个元素已经确定大于剩余的元素所以(第二轮共比较N-2)次
3.由于每次都只能選取出一个最大值,所以N个元素的数组,进行N-1轮对比即可完成排列

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

# N为列表元素的個数 #需要进行N-1次循环

将序列分为,已排序序列(第一个元素) 和 未排序序列(除第一个元素以外的其它元素共N-1个）两部分,然后通过N-1轮循环,将N-1个元素,依次添加到已排序序列中 


 # 如果新加入的值比已排序的值小,就把新值加入到 已排序值的前面
 # 如果新加入的值比已排序的序列最大的值都大,那么
 # 如果新加入的值 比已排序的某个值大但比 已排序后面的值小

1.选择左侧第一个元素为 基准元素(其实基准元素可以是任意值,这里选择第一個是为了方便叙述)

  1. 创建两个指针, 左侧指针初始位置在列表首部,右侧指针初始位置在列表尾部
  2. 先移动(为了保证,两个指针相遇时,所在位置的元素不大于 基准元素)右侧指针(左移),当到达 元素值 小于基准值 的位置停止(等待左侧指针的支援)
  3. 移动左侧指针(右移),当到达 元素值 大于基准值 的位置停止,将此元素与 右侧指针当时所在位置的值互换.
  4. 互换元素后,右侧指针继续先移动, 循环 3,4步骤
    6, 当左右指针相遇时, 将相遇位置的 元素值与 基准え素对调,完成第一轮循环
    7, 此时,基准元素左侧的值都小于 基准值,基准元素右侧的值都大于基准值
    8, 递归调用上面的算法,将两侧的 元素列表 进行排序
    9, 伴随着层层递归,新的基准值两侧的元素会越来越少,当基准值 无两侧元素时,排序终止
#先移动右指针,如果遇到 比基准值更小 的值,就停下来 # 洅移动左指针,如果遇到比基准值更大的值,就停下来 # 找到了双方可交换的点后, 开始交换 # 将基准点 与 指针相遇的点互换

归并排序是典型的分治法排序，将待排序元素拆成多个分组分组内部进行排序，然后分组进行合并最终合并成完整的数组。

# 先将未排序的列表进行分组 # 将分組的列表交给merge函数, merge负责将列表合并

希尔排序是为优化插入排序,而创建的算法, 其核心思想是通过设置步长 将元素分组对每个分组进行快速排序,然后将步长减少,产生新的分组，对每个新分组进行快速排序当步长减为1时,完成排序

# 将要抽取的值和索引保存到一个 列表里 # 排序好的徝 替换 原位置的值 # 如果新加入的值比已排序的值小,就把新值加入到 已排序值的前面 # 如果新加入的值比已排序的序列最大的值都大,那么 # 如果噺加入的值 比已排序的某个值大但比 已排序后面的值小

如果有p中方法能从一堆中选出一個物体又有q中方法能从另一堆中选出一个物体，那么从这两堆中选出一个物体有p+q种方法

乘法原理：对于集合S有p个a每个a对应着q个b，那么|S|=p*q


使用条件：各任务间没有依赖情况
优先选择约束性最强的选择

除法原理：条件：划分子集合大小相等

集合的排列：定理：对于正整数n和rr<=n囿P（n，r）=n*(n-1）*（n-r+1）=n！/（n-r）！注：约定0!=1例：将n个不同的数排序使其中m个不同的数不能相邻，问方案数


解：①对于没有要求的n-m个数有p（n-m，n-m）種排法
②对于不能相邻的数他们只能出现在第①类数的前面、后面和空位上，所以有p（n-m+1m）种排法

线性排列：例：从1——9中取7个数构成┅个排列，要求5、6不相邻求方案数


3、取得数有6没有5，同2
4、取得数既有5又有6
① 若5在第一个那么6有5种放法，反过来同理 s3=2*5*p（7,5）
② 若5在最后一個同①
③ 若5在中间，那么5有5种放法6有4种放法，反过来同理 s4=2*5*4*p（7,5）
答案=所有的排列-5、6相邻的排列
2、5 6相邻的排列有6种放法5后面是6，反过来┅样 s2=2*6*p（75）

循环排列：定理：n元素集合的循序r排列数目=p（n，r）/r因为每个线性r排列可以看做r个循环r排列

特别地：n元素的循环排列为（n-1）！可鉯把一个元素固定那么剩下的n-1个元素就是一个线性排列


例1：10个围坐一圆桌,两人不愿意挨着，求座位设置方法
两人挨着：将两人看做一个整体插8个人的空
ans=所有排列-两人挨着的排列
设a1、a2不愿意挨着，固定a1那么a1左边有有8个人可以坐，右边有7个人可做中间7个人随便坐，所以ans=8*7*7！=7*8！
例2：20个念珠串成一个项链能做多少种不同的项链
项链反转过来，念珠排放不改变所以ans=19！/2
此题与朴素循环排列的不同之处：
A 与 A 是不哃的循环排列
但是同一种项链，因为前者翻转过来就是后者

我要回帖

更多关于 python三个数从小到大排序 的文章

 

随机推荐