归并排序与快速排序

基础算法复习:归并排序与快速排序。

归并排序

基本思路

  归并排序(Merge sort)是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。归并排序是一种稳定的排序方法。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。

  操作步骤如下:

  1. 申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列;
  2. 设定两个指针,最初位置分别为两个已经排序序列的起始位置;
  3. 比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置;
  4. 重复步骤 3 直到某一指针达到序列尾;
  5. 将另一序列剩下的所有元素直接复制到合并序列尾。

  示例,动图演示:

17-1

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
def merge(left, right):
print(left, right)
res = []
i, j = 0, 0
while i < len(left) and j < len(right):
if left[i] > right[j]:
res.append(right[j])
j += 1
else:
res.append(left[i])
i += 1
if i < len(left):
res.extend(left[i:])
if j < len(right):
res.extend(right[j:])
return res
def merge_sort(nums):
if len(nums) <= 1:
return nums
mid = len(nums) // 2
left = merge_sort(nums[:mid])
right = merge_sort(nums[mid:])
return merge(left, right)
时间复杂度
  • 最优时间复杂度:O(nlogn)。
  • 最坏时间复杂度:O(nlogn)。
  • 平均时间复杂度:O(nlogn)。
  • 空间复杂度:O(1)。
  • 稳定性:稳定。

快速排序

基本思路

  快速排序(Quick Sort)是对冒泡排序的一种改进,基本思想是选取一个记录作为基准,通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序。快速排序是一种分而治之思想在排序算法上的典型应用。

  操作步骤如下:

  1. 从数列中挑出一个元素,称为 “基准”(pivot);
  2. 重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作;
  3. 递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。

  示例,动图演示:

17-2

Python 实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def quick_sort(nums, left, right):
if left > right:
return
tmp = nums[left]
i = left
j = right
while i != j:
while nums[j] >= tmp and i < j:
j -= 1
while nums[i] <= tmp and i < j:
i += 1
if i < j:
nums[i], nums[j] = nums[j], nums[i]
nums[left] = nums[i]
nums[i] = tmp
quick_sort(left, i - 1)
quick_sort(i + 1, right)
时间复杂度
  • 最优时间复杂度:O(nlogn)。
  • 最坏时间复杂度:O(n**2)。
  • 平均时间复杂度:O(nlogn)。
  • 空间复杂度:O(logn)。
  • 稳定性:不稳定。
坚持原创技术分享,您的支持将鼓励我继续创作!