排序算法整理(一)

本篇文章整理了归并排序和快速排序的相关原理和python实现代码

归并排序

归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案”修补”在一起，即分而治之)。

最后合并详细过程如下：

基于python实现的代码如下：

def merge(arr, l, m, r): 
    n1 = m - l + 1
    n2 = r- m 
  
    # 创建临时数组
    L = list(arr[l:m+1])
    R = list(arr[m+1:r+1])
  
    # 归并临时数组到 arr[l..r]
    # 这里相当于合并2个排序的数组
    i,j,k = 0,0,l       
  
    while i < n1 and j < n2 : 
        if L[i] <= R[j]: 
            arr[k] = L[i] 
            i += 1
        else: 
            arr[k] = R[j] 
            j += 1
        k += 1
  
    # 拷贝 L[] 的保留元素
    while i < n1: 
        arr[k] = L[i] 
        i += 1
        k += 1
  
    # 拷贝 R[] 的保留元素
    while j < n2: 
        arr[k] = R[j] 
        j += 1
        k += 1
  
def mergeSort(arr,l,r): 
    if l < r: 
        m = int((l+(r-1))/2)
        mergeSort(arr, l, m) 
        mergeSort(arr, m+1, r) 
        merge(arr, l, m, r) 
  
if __name__ == '__main__':
      arr = [12, 11, 13, 5, 6, 7] 
      n = len(arr) 
      print("给定的数组") 
      print(arr)
      mergeSort(arr,0,n-1) 
      print("排序后的数组") 
      print(arr)

快速排序

快速排序使用分治法（Divide and conquer）策略来把一个序列（list）分为较小和较大的2个子序列，然后递归地排序两个子序列。

该方法的基本思想是：
1．先从数列中取出一个数作为基准数。
2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
3．再对左右区间重复第二步，直到各区间只有一个数。

下面图有画错的地方，应该用i,j=left,right，执行左右指针的操作，递归的是[left,i],[j,right]两部分

填坑法

交换法

def partition_tiankeng(arr,left,right):
    x = arr[left]
    i,j = left,right
    while i<j:
        while i<j and arr[j]>=x:
            j -= 1
        if i<j :
            arr[i] = arr[j]
            i += 1
        while i<j and arr[i]<x:
            i += 1
        if i<j:
            arr[j] = arr[i]
            j -= 1
    arr[i] = x
    return i

def partition_exchange(arr,left,right):
    x = arr[left]
    i,j = left,right
    while i<j:
        while i<j and arr[j]>x:
            j -= 1
        while i<j and arr[i]<=x:
            i += 1
        if i<j :
            arr[i],arr[j] = arr[j],arr[i]
    arr[i],arr[left] = arr[left],arr[i]
    return i

def quicksort(arr,left,right):
    if left<right:
        pos = partition_exchange(arr,left,right)
        quicksort(arr,left,pos-1)
        quicksort(arr,pos+1,right)


if __name__ == '__main__':
      arr = [5,2,3,1,4]
      n = len(arr) 
      quicksort(arr,0,n-1) 
      print(arr)

参考文献：
[1] https://blog.csdn.net/morewindows/article/details/6684558
[2] https://www.runoob.com/python3/python-quicksort.html
[3] https://www.runoob.com/python3/python-merge-sort.html