Classic Sorting Algorithms
Published:
This is my personal notes for classic sorting algorithms, including BubbleSort, SelectionSort, InsertionSort, MergeSort, QuickSort.
Overall Introduction
经典排序算法十分重要，也是基础，笔者整理并用Python实现了几大经典排序算法，包括冒泡排序，选择排序，插入排序，归并排序，快速排序, 计数排序, 基数排序, 堆排序。
本篇博客所有排序实现均默认从小到大。
BubbleSort
介绍：
冒泡排序的原理非常简单，它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。- 步骤：
- 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
- 对第0个到第n-1个数据做同样的工作。这时，最大的数就“浮”到了数组最后的位置上。
- 针对所有的元素重复以上的步骤，除了最后一个。
- 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
- python实现
def bubble_sort(array):
flag=0
for i in range(len(array)-1):
for j in range(len(array)-i-1):
if array[j]>array[j+1]:
array[j],array[j+1]=array[j+1],array[j]
flag=1
if flag==0:
break
return array
注: flag==0表示某一趟已经没有进行交换操作，数组全部有序，调出循环。
SelectionSort
介绍：
选择排序的原理非常简单，每一趟将未排序序列中的最小（大）值放到已排序序列的末尾。- 步骤：
- 在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
- 再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
- 以此类推，直到所有元素均排序完毕。
- python实现
def select_sort(array):
for i in range(len(array)):
min=i
for j in range(i+1,len(array)):
if array[j]<array[min]:
min=j
array[i],array[min]=array[min],array[i]
return array
InsertionSort
介绍：
插入排序的工作原理是，对于每个未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。- 步骤：
- 从第一个元素开始，该元素可以认为已经被排序
- 取出下一个元素，在已经排序的元素序列中从后向前扫描
- 如果被扫描的元素（已排序）大于新元素，将该元素后移一位
- 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
- 将新元素插入到该位置后
- 重复步骤2~5
- python实现
def insert_sort(array):
for i in range(1,len(array)):
if array[i]<array[i-1]:
temp=array[i]
for j in range(i-1,-1,-1):
if array[j]>temp:
array[j+1]=array[j]
index=j
else:
break
array[index]=temp
return array
MergeSort
介绍：
归并排序是采用分治法的一个非常典型的应用。归并排序的思想就是先递归分解数组，再合并数组。步骤：
先考虑合并两个有序数组，基本思路是比较两个数组的最前面的数，谁小就先取谁，取了后相应的指针就往后移一位。然后再比较，直至一个数组为空，最后把另一个数组的剩余部分复制过来即可。
再考虑递归分解，基本思路是将数组分解成left和right，如果这两个数组内部数据是有序的，那么就可以用上面合并数组的方法将这两个数组合并排序。如何让这两个数组内部是有序的？可以再二分，直至分解出的小组只含有一个元素时为止，此时认为该小组内部已有序。然后合并排序相邻两个小组即可。python实现
def merge(array1,array2):
new_array=[]
i,j=0,0
while i<len(array1) and j<len(array2):
if array1[i]<array2[j]:
new_array.append(array1[i])
i+=1
else:
new_array.append(array2[j])
j+=1
new_array+=array1[i:]
new_array+=array2[j:]
return new_array
def mergsort(array):
if len(array)<2:
return array
mid=len(array)//2
left=mergsort(array[:mid])
right=mergsort(array[mid:])
return merge(left,right)
QuickSort
介绍：
快速排序通常明显比同为Ο(n log n)的其他算法更快，因此常被采用，而且快排采用了分治法的思想，所以在很多笔试面试中能经常看到快排的影子。可见掌握快排的重要性。- 步骤：
- 从数列中挑出一个元素作为基准数(最左边或右边)。
- 分区过程，将比基准数大的放到右边，小于或等于它的数都放到左边。
- 再对左右区间递归执行第二步，直至各区间只有一个数。
- python实现
# (1) 左右两个指针相向而走
def partition(array,low, high):
left=low
key=array[low]
while low<high:
while low<high and array[high]>=key:
high-=1
while low<high and array[low]<=key:
low+=1
array[low], array[high] = array[high], array[low]
array[low],array[left]=array[left],array[low]
return low
def quick_sort(array,low,high):
if low<high:
key=partition(array,low,high)
quick_sort(array,low,key-1)
quick_sort(array,key+1,high)
# (2) 两个指针同时从左边走 (算法导论)
def partition(List,begin,end):
i=begin-1
for j in range(begin,end):
if List[j]<List[end]:
i=i+1
List[i],List[j]=List[j],List[i]
List[i+1],List[end]=List[end],List[i+1]
return i+1
def quick_sort(List,begin,end):
if begin<end:
begin_next=partition(List,begin,end)
quick_sort(List,begin,begin_next-1)
quick_sort(List,begin_next+1,end)
CoutingSort
介绍：
计数排序非comparison based sort, 可以做到O(n+k)，其中n是数字个数，k是数据的范围(maxN)，其适用条件是输入数字不明显大于数字个数. 比如[10, 5, 10k, 5k] 便不能用coutingsort。空间复杂度为O(n+k)。- 步骤：
- 构造count数组，长度为maxN+1，统计nums中各个数字的个数。
- 将count进行累加, 得到sumCount。
- 对于nums中的每个数，其位置即为sumCount中的个数，赋值完后将sumCount减1。
- python实现
def countingsort(nums):
maxN=max(nums)
count=[0]*(maxN+1)
ans=[0]*len(nums)
for n in nums:
count[n]+=1
for i in range(1,maxN+1):
count[i]+=count[i-1]
for j in range(len(nums)):
ans[count[nums[j]]-1]=nums[j]
count[nums[j]]-=1
return ans
RadixSort
介绍：
基数排序非comparison based sort, 时间复杂度可以做到O(d(n+k))，其中d趟数，n是数字个数 (d=b/r, b=log(base)(range),r=log(base)(size),k=2^r)。空间复杂度和计数排序一样，为O(n+k)。基数排序对每位数进行排序时是调用的counting sort，所以b==r时，基数排序就是计数排序。- 步骤：
- 求最长数字的位数d,即为外层循环次数。
- 在每次循环中，根据当前位的数字大小(0-9)将各个数字放到不同的桶中，相同的保持原来顺序不变。
- 从桶中数字按顺序取出，重构nums。
- python实现
def radixsort(nums):
N=len(nums)
d=len(str(max(nums)))
for i in range(d):
new=[[] for _ in range(10)]
for j in range(N):
new[(nums[j]//(10**i))%10].append(nums[j])
nums=[n for m in new for n in m]
return nums
HeapSort
介绍：
堆排序的关键是创建最大/最小堆的过程，时间复杂度为 O(nlogn)，其中创建堆的过程为 O(logn)。- 步骤：
- 对数组创建堆。
- 将堆顶元素和最后一个交换，将剩余元素heapify。
- 直至只剩下一个元素。
- python实现
def heapify(arr, n, i):
largest = i # Initialize largest as root
l = 2 * i + 1 # left = 2*i + 1
r = 2 * i + 2 # right = 2*i + 2
# See if left child of root exists and is
# greater than root
if l < n and arr[i] < arr[l]:
largest = l
# See if right child of root exists and is
# greater than root
if r < n and arr[largest] < arr[r]:
largest = r
# Change root, if needed
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i] # swap
# Heapify the root.
heapify(arr, n, largest)
# The main function to sort an array of given size
def heapSort(arr):
n = len(arr)
# Build a maxheap.
for i in range(n, -1, -1):
heapify(arr, n, i)
# One by one extract elements
for i in range(n - 1, 0, -1):
arr[i], arr[0] = arr[0], arr[i] # swap
heapify(arr, i, 0)
Comparison
| Method | Overall | Best | Wrost | Space | Stability |
| Bubble | O(n^2) | O(n) | O(n^2) | O(1) | Stable |
| Selection | O(n^2) | O(n^2) | O(n^2) | O(1) | Unstable |
| Insertion | O(n^2) | O(n) | O(n^2) | O(1) | Stable |
| Merge | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | Stable |
| Quick | O(nlogn) | O(nlogn) | O(n^2) | O(nlogn)~O(n) | Unstable |
| Counting | O(n+k) | O(n+k) | O(n+k) | O(n+k) | stable |
| Radix | O(d(n+k)) | O(d(n+k)) | O(d(n+k)) | O(n+k) | stable |
| Heap | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | Unstable |