排序算法是算法中的基础，也是面试重点。现利用Python语言实现了经典的排序算法并且做出一定的总结。也是帮助自己记忆和理解。
一、冒泡排序
原理：比较然后交换相邻的两个元素。每次冒泡操作至少会让一个元素移动到它应该在的位置。重复n次，就至少完成n个数据的排序。
时间复杂度 : O(N²)
空间复杂度：O(1)
稳定性：稳定
代码：
def bubble_sort(a):
n = len(a)
if n<=1:
return
for i in range(0,n):
flag = False
for j in range(0,n-i-1):
if a[j]>a[j+1]:
a[j],a[j+1] = a[j+1],a[j]
flag = True
if flag != True:
break
二、插入排序
原理：将数组中的元素分为已排序和未排序两个区间，然后将未排序区间的元素按次序插入到已排序区间内，并保证已排序区间一直有序。
时间复杂度 : O(N²)
空间复杂度：O(1)
稳定性：稳定
代码：
def insertion_sort(x):
n = len(x)
if n<=1:
return
for i in range(1,n):
value = x[i]
index = i
for j in range(i-1,-1,-1):
if x[j]> value:
x[j+1] = x[j]
index = j
else:
break
a[index] = value
return x
另：事实上有更简洁的实现插入排序的代码，如下所示：
def insert_sort(array):
for i in range(len(array)):
for j in range(i):
if array[i] < array[j]:
array.insert(j, array.pop(i))
break
return array
三、选择排序
原理：与插入排序的原理类似，也分为两个区间，但是选择排序每次是从未排序区间内找最小元素，放到已排序区间末尾。
时间复杂度 : O(N²)
空间复杂度：O(1)
稳定性：不稳定
代码：
for i in range(len(x)):
a = i
for j in range(i, len(x)):
if x[j] < x[a]:
a = j
x[i], x[a] = x[a], x[i]
return x
四、快速排序
原理：快排采用了分治法和递归的思想：如果要排序数组下标q到e的元素，先选择一个分区点pivot（通常是头部元素或者尾部元素）,然后遍历，将小于分区点的放在分区点左边，大于分区点的放在右边；最后利用分区点将数组分成[q:pivot]和[pivot:e]两个区间，再采用之前的步骤进行迭代。
时间复杂度 : O(NlogN)
空间复杂度：O(1) (经过设计可以实现快排拥有原地排序的属性）
稳定性：不稳定
代码：
def quick_sort(x):
def sort(q,e):
if q>e:return
i,j = q,e
pivot = x[q]
while i<j:
while i<j and pivot<x[j]:
j-=1
while i<j and pivot>=x[i]:
i+=1
x[i],x[j] = x[j],x[i]
x[i],x[q] = pivot, x[i]
sort(q,i-1)
sort(j+1,e)
sort(0,len(x)-1)
五、归并排序
原理：将数组分成两个子数组，然后将子数组分成两个子子数组......，直到分成含有两个或一个元素的数组然后进行比较，最后向上递归。
时间复杂度 : O(NlogN)
空间复杂度：O(1)
稳定性：稳定
代码：
def merge_sort(x):
def sort(left,right):
list = []
while len(right) and len(left):
if left[0] <= right[0]:
list.append(left.pop(0))
elif left[0] > right[0]:
list.append(right.pop(0))
if len(right) == 0:list += left
elif len(left) == 0:list += right
return list
def merge(list):
if len(list) ==1:return list
mid = len(list)>>1
left = merge(list[:mid])
right = merge(list[mid:])
return sort(left,right)
return merge(x)
六、堆排序
原理：简单来说就是构造一个大顶堆，然后依次取堆顶元素+剩余元素堆化的操作进行排序
时间复杂度 : O(NlogN)
空间复杂度：O(1)
稳定性：不稳定
代码：
def heap_sort(array):
def heap_adjust(parent):
child = 2 * parent + 1 # left child
while child < len(heap):
if child + 1 < len(heap):
if heap[child + 1] > heap[child]:
child += 1 # right child
if heap[parent] >= heap[child]:
break
heap[parent], heap[child] =
heap[child], heap[parent]
parent, child = child, 2 * child + 1
heap, array = array.copy(), []
for i in range(len(heap) // 2, -1, -1):
heap_adjust(i)
while len(heap) != 0:
heap[0], heap[-1] = heap[-1], heap[0]
array.insert(0, heap.pop())
heap_adjust(0)
return array
网友评论