一、概念

排序算法是一种能将一串数据按照特定顺序进行排列的一种算法

稳定性: 稳定排序算法会让原本有相等数值的记录维持相对顺序,也就说当有两个相等的数据A,B时,且原本A在B的前面,则在排序后A仍然是在B的前面,这就是稳定性的概念;

二、冒泡排序

1、啥子叫冒泡排序

它是一种较为简单的排序算法,具体过程就是遍历所要排序的数列,每一次比较两个数,如果他们顺序错误则交换顺序,直至所有的数据交换完毕,也就是完成了数列的排序;由于在交换过程中,最小的元素会处于顶端的位置,所以叫做冒泡排序

2、过程分析

在实现冒泡排序的过程中,每次循环之后,数列中最大的元素移动到了最末端,然后在进行下一次的循环遍历,选出次大的元素,继续循环,直至排完序,则最小的处在顶端的位置

3、实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def bubble_sort(alist):
for j in range(len(alist)-1):
for i in range(0,len(alist)-1-j): # 操作下标而不是直接作用于元素上
if alist[i] > alist[i+1]:
alist[i],alist[i+1] = alist[i+1],alist[i]

# 优化情况
def bubble_sort(alist):
for j in range(len(alist)-1):
count = 0 # 记录交换的次数
for i in range(0,len(alist)-1-j):
if alist[i] > alist[i+1]:
alist[i],alist[i+1] = alist[i+1],alist[i]
count += 1
if count is 0: # 如果count为0,则说明没有进行交换
break


if __name__ == "__main__":
li = [1,2,6,4,12,9]
bubble_sort(li)
print(li)

说明:

  • 最优时间复杂度为O(n) <遍历一遍发现全都排好了>
  • 最坏时间复杂度为O(n^2)
  • 稳定

三、选择排序

1、思想

一组数据相当于分成了两个部分,后一部分是待排数列,初始默认第一个元素是最小值,然后从这些待排的数列中进行遍历找到最小值并记录下标位置,然后与记录的初始最小值比较,如果找到的小于初始值则进行交换,然后继续遍历;也就是说,整个过程就是在找最小值。

2、实现

1
2
3
4
5
6
7
8
9
def select_sort(alist):
'''选择排序'''
n = len(alist)
for j in range(n-1):
min_index = j
for i in range(j+1,n-1):
if alist[min_index] > alist[i]:
min_index = i
alist[j], alist[min_index] = alist[min_index], alist[j]

时间复杂度:O(n^2)

稳定性:简单的考虑这种情况,在一个乱序的列表中[11,23,12,23,6],排序时第一个23较大,则在排序时会由于交换而移动到最后面,则在排列第二个23时,因为它不比第一个23大,所以不变化,由此可见,二者交换了顺序,稳定性就是不稳定

四、插入排序

1、思想

通过构建有序序列,对于未排列的数据,在已经排好序的数列中从后向前进行扫描,找到相应的位置并插入,插入排序在实现上,在从后向前扫描的过程中,需要反复把已经排序元素逐步向后移动

2、实现

1
2
3
4
5
6
7
8
9
10
11
12
13
def insert_sort(alist):
'''插入排序'''
n = len(alist)
# j表示循环次数,也即是有多少个元素执行此过程
for j in range(1, n):
i = j
# i是表示从从待排序列中取出第一个,然后进行扫描比较
while i > 0:
if alist[i] < alist[i-1]:
alist[i], alist[i-1] = alist[i-1], alist[i]
i -= 1
else:
break

3、时间复杂度

最优时间复杂度: O(n) <数列已按照升序排列,这个时间复杂度仅仅是遍历的时间>

最坏时间复杂度: O(n^2)

稳定性:稳定

五、希尔排序

1、概念

它是插入排序的一种,也称为缩小增量排序,是直接插入排序算法的一种更为高效的改进版;但是它是不稳定的。具体思想就是把数据按照下标的一定增量进行分组,然后对每一个组进行插入排序,随着增量的一步步减少,每一组包含的数据越多,当增量为1时,整个排序完成!

2、实现

1
2
3
4
5
6
7
8
9
10
11
12
13
def shell_sort(alist):
n = len(alist)
gap = n // 2 # 确定步长
while gap >= 1:
for j in range(gap,n):
i = j
while i > 0:
if alist[i] < alist[i-gap]:
alist[i],alist[i-gap] = alist[i-gap],alist[i]
i -= gap
else:
break
gap //= 2

最优时间复杂度: 无法确定

最坏时间复杂度: O(n)

稳定性: 不稳定

六、快速排序

1、思想


  • 先从给定数列中取出一个基准数据值,记为x
  • 排序过程中,小于x的数据全放在左边,大于x的数据全放在其右边
  • 然后再次重复上述步骤即可

2、实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def quick_sort(alist,first,last):
if first >= last:
return
mid_value = alist[0]
low = first
high = last
while low < high:
# high左移
while low < high and alist[high] >= mid_value:
high -= 1
alist[low] = alist[high]
# low右移,在判断里面进行移动low的值以防它移动过度
while low < high and alist[low] < mid_value:
low += 1
alist[high] = alist[low]
alist[low] = mid_value
# 此时low的位置就是初始的那个值
# 递归使用函数本身,快排左边
quick_sort(alist,first,low-1)
# 递归快排右边
quick_sort(aliist,low+1,last)
  • 最优时间复杂度: O(n*logn)
  • 最坏时间复杂度: O(n^2) # 这种情况下就是每次再分的时候都只能分为总是第一项和剩余项
  • 稳定性:不稳定

七、归并算法

1、思想


  分而治之,就是将一组待排序列向下均分、均分、均分······直至每一个小分组中只有一个元素,然后向上走进行合并操作,以致达到排序的目的

2、实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def merge_sort(alist):
'''归并排序'''
# 分而治之,先进行分的操作
n = len(alist)
if n <= 1:
return alist
mid = n/2
# 分的结果为两个新的列表left 和 right;以下是递归操作
left = merge_sort(alist[:mid])
right = merge_sort(alist[mid+1:])
left_pointer, right_pointer = 0,0
result = []
while left[left_pointer] < len(left) and right[right_pointer] < len(right):
if left[left_pointer] <= right[right_pointer]:
result.append(left[left_pointe])
left_pointer += 1
else:
result.append(right[right_pointer])
right_pointer += 1
result += left[left_pointer:]
result += right[right_pointer:]
return result
#-----------------------------------------------------------

最优时间复杂度:O(n*logn)

最坏时间复杂度:O(n*logn) # 这种情况下就是每次再分的时候都只能分为总是第一项和剩余项

稳定性:稳定