常见排序算法-python实现

常见排序算法一览表

快速排序

原理

数组中随机选一个基准元素，采用分治思想，筛选出小于基准值的的元素组成数组A和大于基准值的元素组成数组B，再将A，B分别进行选基准比较分出小于基准的数组C和大于基准的数组D，这算两个轮回，进行多轮操作直到新数组元素个数小于2。

代码

def quickSort(array):
  if len(array) < 2:
    return array

  pivot = array[0]
  
  l = [j for j in array[1:] if j <= pivot]
  r = [j for j in array[1:] if j > pivot]
  
  return quickSort(l) + [pivot] + quickSort(r)

归并排序

原理

选取中间值，拆分成左右两个数组A、B，再深度取中值拆分A，B得到C、D，这是两轮拆分，经过多伦拆分直到新数组元素个数小于2不能再拆分，不能再拆分的话说明最小数组一定有序，然后再递归将两个有序数组进行合并。

代码实现

def mergeSorted(arr1,arr2)
  # 合并两个有序数组
  i , j  = 0, 0
  length1, length2 = len(arr1), len(arr2)
  new_arr = []
  while i < length1 and j < length2:
    if arr1[i] < arr2[j]:
      new_arr.append(arr1[i])
      i += 1 
    else:
      new_arr.append(arr2[j])
      j += 1
  if i < length1:
    new_arr.extend(arr1[i:])
  elif j < length2:
    new_arr.append(arr2[j:])
  return new_arr

def ms(arr):
  # 归并排序
  if len(arr) < 2:
    return arr

  mid = int(len(arr)/ 2)
  l = ms(arr[:mid])
  r = ms(arr[mid:])
  
  return mergeSorted(l, r)