1 Introduction

根据中说明,可以
了解, 基于交换的排序目前有两大类: bubble-sort, quick-sort. 所有交换排序, 受方法本身的限制, 最低的时间复杂度为 O(nlogn).

其中基于交换的排序, 都是在原有空间基础上, 进行两个数值的比较和交换工作, 所有的
交换排序步骤:

  • 比较两个值, 判断大小
  • 如果发现逆置, 则交换两个元素
  • 不断地进行上述的操作

维基百科: 冒泡排序, 快速排序

冒泡排序和快速排序的动画演示.

2 冒泡排序

2.1 Analysis

本质上,一种比较类-非线性时间-交换类-排序

冒泡排序是一种简单的排序算法, 重复地走访过要排序的数列,一次比较两个元素,
如果他们的顺序错误就把他们交换过来, 走访数列的工作是重复地进行直到没有再需要交换.
这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端.

哇,政策下来了…:

1
2
3
我比你大,我们两得换换了;(仅仅和相邻元素进行对比)
走一步是一步哪管得了不熟的人;### 2.2 Example
一个个来,不要急(每次仅仅将当前最大数归位);

性能:O(n*n)

2.2 Example

1
2
3
4
5
6
7
8
9
10
11
def bubbleSort(list1):
"""bubbleSort

:param list1:source list1
"""
list_len = len(list1)
for i in range(list_len):
j = list_len - i - 1
for k in range(j):
if list1[k] > list1[k + 1]:
list1[k], list1[k + 1] = list1[k + 1], list1[k]

3 快速排序

3.1 Analysis

基于分治法, 可以将Quicksort/Partition-exchange sort分为如下三步:

  • 在数据集中, 选择一个元素作为基准pivot
  • 所有小于pivot的元素, 都移动到基准的左边, 大于pivot的元素移动到基准的右边, 其中pivot所在的位置就是最终的位置, 称为partition操作
  • 对pivot左右两边的子集, 重复使用分治法, 直到所有子集都是剩下一个元素为止.

说明:

  • 本质上,比较类-非线性时间-交换类-二分法思维(分而治之)-排序
  • 大哥,我们两一起将SB归为SB,NB归为NB,标准以我为参考(k = A[i])
  • 大哥,你先走,我等下将NB的人替换你哪里SB的人(交换A小于k,B小于k时的两值)
  • 大哥,革命会师之日就是你我相见之时(表示一次基准二分结束)

fastsort

3.2 性能分析

时间复杂度: O(nlogn), 最坏情况1.4*O(nlogn), 该值可见维基百科说明.

空间复杂度: 最好情况-O(nlogn), 最坏情况-O(n^2 logn)

快速排序是二叉查找树的一个优化版本, 根据快速排序来组织这些数据项到一个隐含的树中,
实际上大部分的分治法都会产生一棵隐含的树结构.

  • 快速排序与堆排序: 两者性能类似, 堆排序稍慢于快速排序, 但是最坏情况O(nlogn)
  • 快速排序与归并排序: 最坏情况 O(nlogn), 归并排序是一个稳定的排序算法, 可以在外排序中使用

3.3 Example

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
def qsort(list1, left, right):
"""qsort:quick sort

:param list1:source list
:param left:left index of list1 at current sort
:param right:right index of list1 at current sort
"""
# 革命会师,好久不见
if left >= right:
return list1

k = list1[left]
lp = left
rp = right

while lp < rp:
# 必须大哥先走
while rp > lp and list1[rp] >= k:
rp -= 1

# 小弟来换大哥的SB了
while lp < rp and list1[lp] <= k:
lp += 1

list1[lp], list1[rp] = list1[rp], list1[lp]

# 大哥,将我们脚下这笨蛋替换为一开始的标准
list1[left], list1[lp] = list1[lp], list1[left]

# 一个新的轮回,大哥,来世再见
qsort(list1, left, lp - 1)
qsort(list1, lp + 1, right)

return list1