【札记】基本排序算法(Python实现)

本文是学习数据结构和经典排序算法的个人札记。

原文: Problem Solving with Algorithms and Data Structures using python

基本概念

(1)排序算法的稳定性:所谓“稳定性”是指,在待排序数组出现的两个相同的元素,排序之后相对维持保持不变。
(2)原地排序:所谓原地排序是指,不申请多余的空间来辅助完成排序算法,而是在原来的待排序的数据之上直接进行比较,交换,移动等操作


Bubble Sort 冒泡排序

概述

  • 冒泡排序从数组首将最大元素逐一交换至队尾,并依此对未排序的子数组进行上述排序。
  • 时间复杂度为O(N^2)
  • 原地排序
  • 稳定

Python实现

1
2
3
4
5
6
7
8
9
def bubble_sort(list):
#O(n^2)
for sorted_position in range(len(list)-1,0,-1): #traverse the list reversively
for i in range(0,sorted_position): #bubble exchange
if list[i] > list[i+1]:
temp = list[i]
list[i] = list[i+1]
list[i+1] = temp
return list

Selection Sort 选择排序

概述

  • 一种对冒泡排序的改进,将子数组中最大元素与数组数组尾元素进行比较并交换。
  • 每个外部循环,只进行一次数据交换
  • 时间复杂度为O(N^2)
  • 原地排序
  • 稳定

Python实现

1
2
3
4
5
6
7
8
9
10
11
def selection_sort(list):
#O(n^2)
for sort_position in range(len(list)-1,0,-1):
position_max = 0
for i in range(0,sort_position+1):
if list[i] > list[position_max]:
position_max = i
temp = list[sort_position]
list[sort_position] = list[position_max]
list[position_max] = temp
return list

Insertion Sort 插入排序

概述

  • 将新元素插入已经排序完成的数组中,从数组头开始迭代进行排序。
  • 时间复杂度为O(N^2)
  • 原地排序
  • 稳定

Python实现

1
2
3
4
5
6
7
8
9
10
11
12
def insertion_sort(list):
#O(n^2)
#sort from head
for index in range(0,len(list)):
insert_value = list[index]
position = index
#leave a slot for inserted data
while position > 0 and list[position-1] > insert_value:
list[position] = list[position-1]
position = position - 1
list[position] = insert_value
return list

Merge Sort 归并排序

概述

  • 采用二分法将数组进行分割,对2原数字比较大小排序,然后将两个等长已排序数组逐元素比较大小进行归并。
  • 时间复杂度为O(nlgn)
  • 非原地排序,以空间换时间,另外需要O(n)的空间
  • 分治思想,递归实现
  • 稳定

Python实现

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
35
36
37
38
def merge_sort(list):
#O(nlgn)
#devide and conquer
print('Splitting:',list)
if len(list) > 1:
mid = len(list) // 2
left_list = list[:mid]
right_list = list[mid:]

merge_sort(left_list)
merge_sort(right_list)

#merge
#list here indicate the left_list or right_list above
left_index = 0
right_index = 0
index = 0
while left_index < len(left_list) \
and right_index < len(right_list):
if left_list[left_index] < right_list[right_index]:
list[index] = left_list[left_index]
left_index += 1
else:
list[index] = right_list[right_index]
right_index += 1
index += 1

while left_index < len(left_list):
list[index] = left_list[left_index]
left_index += 1
index += 1

while right_index < len(right_list):
list[index] = right_list[right_index]
right_index += 1
index += 1

print('Merging:',list)

Quick Sort 快排

概述

  • 将数组元素和某一轴元素进行比较,依此将数组分为两堆,递归调用上述过程,最终将数组排序。
  • 大数据阶段用快排递归,递归层次太深可以用堆排序
  • 平均时间复杂度为O(nlgn),最差情况为O(n2)
  • 原地排序
  • 不稳定

Python实现

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
35
36
def quick_sort(list,first=0,last=-1):
#O(n^2)
#devide and conquer
if last == -1:
last = len(list)-1
if first < last:
pivot = list[first]
left_index = first + 1
right_index = last
done = False
while not done:
#skip the values smaller than pivot on the left side
while left_index <= right_index \
and list[left_index] <= pivot:
left_index += 1
#skip the values bigger than pivot on the right side
while right_index >= left_index \
and list[right_index] >= pivot:
right_index -= 1
#change the elements
if left_index > right_index:
done = True
else:
temp = list[left_index]
list[left_index] = list[right_index]
list[right_index] = temp

#change the pivot to the middle
#note that now right_index < left_index
temp = list[first]
list[first] = list[right_index]
list[right_index] = temp
print right_index
#recursively sort
quick_sort(list, first, right_index-1)
quick_sort(list, right_index+1, last)

Shell Sort 希尔排序

概述

  • 希尔排序是插入排序的一种,称为缩小增量排序,将数列按照指定间隔的下标分成若干子数列,对每个字数列进行插入排序,不断减少间隔大小,最终进行全数列的插入排序
  • 插入排序在对几乎已经排好序的数据操作时,效率高,即可以达到线性排序的效率。
  • 该算法也有分治法的思想
  • 时间复杂度和间隔增量序列选择有关,下界为O(n·log2n),对规模大的数据不是最好选择
  • 原地排序
  • 不稳定

Python实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def shell_sort(test_list):
#O(n^2)
#define the increment gap descending method
sublist_count = len(test_list) // 2
while sublist_count > 0:
for start_index in range(sublist_count):
insertion_sort(test_list,start_index,sublist_count)
sublist_count = sublist_count // 2
return test_list


def insertion_sort(test_list,start_index,gap):
##O(n^2)
for index in range(start_index+gap, len(test_list), gap):
position = index
#reversily
while position >= gap and test_list[position] < \
test_list[position-gap]:
test_list[position], test_list[position-gap] = \
test_list[position-gap], test_list[position]
position = position - gap