{{ selected_gold.title }}
排序
本文将介绍编程过程中常常会遇到的问题：排序。排序无处不在，比如，你买机票的时候会选择按照价格排序，这个过程会用到排序。排序的方式有很多，而且都有它们的优缺点，因此，本文将介绍一些通用的排序算法，并分析它们适合的场景，最终能够帮助你在合适的场景里选择合适的排序算法。
- 堆排序
- 快速排序
堆排序
堆排序是一种高效的排序方法，它借助了堆数据结构，实现比较复杂，然而，无论从时间复杂度，还是空间复杂度来讲，它都是一个高效的排序算法。
堆排序的过程伴随着建立堆的过程，堆建立之后，才会执行堆排序操作。关于什么是堆以及如何建立堆，你需要参考这篇文章。
堆建立成功之后，你需弹出堆顶元素，再重建堆，一直反复执行整个过程，直到堆中只剩一个元素。最后，输入的数据就变成有序了。
假设需要对以下数据进行堆排序：
data = [17,19,100,36,3,25,1,7,2]
第一步：在data上建堆，我们选择建立大根堆，结构如下所示：
建立完成之后，data中的数据发生了变化，如下所示：
data = [100,19,36,17,3,25,1,2,7]
第二步：将堆顶的元素与堆尾的元素互换，也就是上图的100与7互换。由于现在堆顶元素是7，因此需要重新建立堆，需要注意的是，在重新建立堆的时候，需要把元素100排除出去。建立完毕之后，data发生了如下变化：
data = [36,19,25,17,3,7,1,2,100]
注意：重建好的堆由36到2组成，并不包括100，如下图所示：
第三步：反复执行第二步，直到堆中只有一个元素。最后，堆排序就完成了，data也变得有序了。
以下是Python版的堆排序：
class Heap:
def __init__(self, arr_data, min_heap = True):
self.arr_data = arr_data
self.compare_func = (lambda parent, child : parent > child) if min_heap else (lambda parent, child : parent < child)
for index, _ in enumerate(self.arr_data):
self._heap_up(index)
def _heap_up(self, start_index):
tmp_index = start_index
while True:
parent_index = int((tmp_index -1) / 2)
if tmp_index == 0:
break
if self.compare_func(self.arr_data[parent_index], self.arr_data[tmp_index]):
self.arr_data[parent_index], self.arr_data[tmp_index] = self.arr_data[tmp_index], self.arr_data[parent_index]
else:
break
tmp_index = parent_index
def push(self, val):
self.arr_data.append(val)
self._heap_up(len(self.arr_data) - 1)
def pop(self):
if len(self.arr_data) == 0:
return (False, None)
val = self.arr_data[0]
self.arr_data[0] = self.arr_data[len(self.arr_data) - 1]
self.arr_data.pop()
self._heap_down()
return (True, val)
def _heap_down(self):
total_len = len(self.arr_data)
parent_index = 0
while True:
left_child_index = parent_index * 2 + 1
right_child_index = parent_index * 2 + 2
# left child and right child are None
if left_child_index >= total_len:
break
# has left child and right child is None
if left_child_index < total_len and right_child_index == total_len:
if self.compare_func(self.arr_data[parent_index], self.arr_data[left_child_index]):
self.arr_data[left_child_index], self.arr_data[parent_index] = self.arr_data[parent_index], self.arr_data[left_child_index]
parent_index = left_child_index
else:
break
# has left child and has right child
else:
child_index = right_child_index if self.compare_func(self.arr_data[left_child_index], self.arr_data[right_child_index]) else left_child_index
if self.compare_func(self.arr_data[parent_index], self.arr_data[child_index]):
self.arr_data[child_index], self.arr_data[parent_index] = self.arr_data[parent_index], self.arr_data[child_index]
parent_index = child_index
else:
break
def sort(self):
result = []
while len(self.arr_data) != 0:
val = self.pop()
result.append(val[1])
return result
具体的用法如下所示：
# define a max heap
data = [17,19,100,36,3,25,1,7,2]
maxHeap = Heap(data, False)
print(maxHeap.sort())
最坏情况下，堆排序的时间复杂度是O(nlog(n))，空间复杂度是O(1)。根据数组建立一个完整的堆主要是由_heap_up完成，时间复杂度是O(log(n))，而弹出堆顶元素，然后再重建堆，主要是由pop完成，时间复杂度是O(log(n))。整个排序入口在函数sort完成，时间复杂度是O(nlog(n))。
快速排序
快速排序的基本思想是，从数组中取出一个元素c，并在数组中找到一个位置放置该元素c，并确保数组的开头到c之间的元素均小于c，从c到数组结尾的所有元素均大于或等于c，然后用同样的方式分别处理前半部分和后半部分的数据，整个过程会用到函数的递归。具体的Python实现如下所示：
def quick_sort(data, start, end):
if start >= end:
return
c_index = start
i = start
j = end
while True:
while i < j:
if data[i] > data[c_index]:
break
i += 1
while i < j:
if data[j] <= data[c_index]:
break
j -= 1
if i >= j:
break
else:
data[i], data[j] = data[j], data[i]
i += 1
j -= 1
if data[c_index] > data[i]:
data[c_index], data[i] = data[i], data[c_index]
quick_sort(data, start, i - 1)
quick_sort(data, i + 1, end)
一般情况下，快速排序的时间复杂度和空间复杂度分别是O(nlog(n))和O(log(n))，对于一般的情况已经足够了。然而，如果输入的数据是一个有序的数组，那么，快速排序就会大打折扣。
假设输入了一个从1到n的有序数组，然后对这个数组进行快速排序，此时，时间复杂度变成了O(n^2)，空间复杂度变成了O(n)，这就是快速排序最糟糕的情况。如果n非常大，比如超过一个亿，而且是接近有序，那么快速排序并不能很好地完成排序工作。
创建新文章
删除文章或章节
{{ c.user.name }}
{{ c.content }}