基本排序算法及python实现

稳定度

在待排序的文件中,若存在多个关键字相同的记录,经过排序后这些具有相同关键字的记录之间的相对次序保持不变,该排序方法是稳定的;若具有相同关键字的记录之间的相对次序发送变化,则称这种排序方法是不稳定的。

1.冒泡排序(Bubble Sort)

原理:重复走访过要排序的数列,一次比较两个元素,如果她们的顺序错误就把他们交换过来。
这个算法的名字由来是因为最小的元素会经由交换慢慢“浮”到数列的顶端。

步骤

  1. 比较相邻的元素,如果第一个比第二个大,就叫唤顺序。
  2. 对每一对相邻的元素作相同的工作,从开始第一对到最后一对。这步做完后,最后的元素会是最大的数。
  3. 对除最后一个元素的所有元素重复上述动作。
  4. 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。

代码

 

2. 选择排序(Selection sort)

原理: 将后面的元素最小元素一个个取出然后顺序放置

步骤

  1. 在未排序序列中找到最小元素,存放在排序序列的起始位置
  2. 从剩余未排序元素中继续寻找最小元素,然后放到已排序序列的末尾
  3. 重复步骤2,直到所有元素均排序完毕

代码

 

3. 插入排序(Insertion Sort)

原理:通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。

步骤

  1. 从第一元素开始(认为其已排序)

  2. 取出下一个元素,在已排序元素中从后向前扫描

  3. 如果已排序元素中有元素x大于新元素,将x移到下一位置

  4. 重复步骤3,直到找到已排序的元素小于或等于新元素的位置,将新元素插入到该位置 5. 重复2-4

代码

 

4. 希尔排序

原理:
希尔排序,也称递减增量排序,是插入排序的一种更高效的改进版本。
基于插入排序的亮点相知而改进:
插入排序在对几乎已经排好序的数据操作时,效率高,即可以达到线性排序的效率
但插入排序一般来说时低效的,因为插入排序每次只能将数据移动一位

步骤

  1. 取定一个小于序列长度n的整数d1作为第一个增量,把序列的全部记录分成d1个组
  2. 所有距离为d1的倍数的记录放在同一个组中,在各组内进行插入排序
  3. 取第二个增量d2<d1,重复上述的分组和排序,直至所取的增量dt=1为止

代码

 

5. 归并排序

原理: 将两个已经排序的序列合并成一个序列的操作

步骤

  1. 将n个数据看成n个长度为1的表,将相邻的表成对合并,得到长度为2的n/2个有序表
  2. 进一步将相邻的合并,得到长度为4的n/4个有序表,依次类推。

代码

 

6. 快速排序

原理: 分治策略。
1. 分解–将原问题分解为子问题;
2. 求解–递归地解各子问题;
3. 组合–将各子问题的解组合成原问题的解

步骤

  1. 挑选一个元素为基准(pivot),
  2. 所以元素,比基准小的摆放在基准前面,反之摆放在后面。从而分区(partion)
  3. 递归地把小于基准值元素的子数列和大于基准值元素的子数列排序。

代码

 

7. 堆排序

原理: 堆排序(heapsort)是指利用堆这种数据结构所设计的一种排序算法。 堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:即子节点的键值或索引总是小于(或大于)它的父节点。

步骤

  1. 创建最大堆: 将堆所有数据重新排序,使其成为最大堆

  2. 最大堆调整: 作用是保持最大堆的性质,是创建最大堆的核心子程序

  3. 堆排序: 移除位在第一个数据的根节点,并做最大堆调整的递归运算

代码

 

%e5%b1%8f%e5%b9%95%e5%bf%ab%e7%85%a7-2016-11-17-%e4%b8%8b%e5%8d%884-23-10

 

References:

https://zhuanlan.zhihu.com/p/21839027
https://github.com/nryoung/algorithms/tree/master/algorithms/sorting

《数据结构与算法分析–java语言描述》

暂无评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注