分类 排序算法 下的文章

分类方式

一.交换排序：1.冒泡排序，2.快速排序
二.插入排序：3.直接插入排序，4.希尔排序
三.选择排序：5.简单选择排序，6.堆排序
四.7.归并排序
五.8.基数排序

python实现

一、冒泡排序

思路：
两层循环：
第一层代表最右边最大数的位置。
第二层用来对比交换找出剩下的最大数

def sort(arr):
    l = len(arr)
    # 遍历所有数组元素
    for i in range(l):
        for j in range(0, l-i-1):
            if arr[j] > arr[j+1] :
                arr[j], arr[j+1] = arr[j+1], arr[j]
arr = [64, 34, 25, 12, 22, 11, 90]
sort(arr)
print (arr)
Python
Copy

二、快速排序

1.递归排序算法

思路：
quickSort.gif

2.非递归排序算法

思路：和递归比较像，用栈来存划分区间，
在先找一个锚点，一最右边为例，通过锚点来划分子区间
参考：https://zhuanlan.zhihu.com/p/60756341

# -*- coding: UTF-8 -*-
# 递归排序算法
def sort(b):
    """快速排序"""
    if len(b) < 2:
        return b
    # 选取基准，随便选哪个都可以，选中间的便于理解
    mid = b[len(b)// 2]
    # 定义基准值左右两个数列
    left, right = [], []
    # 从原始数组中移除基准值
    b.remove(mid)
    for item in b:
        # 大于基准值放右边
        if item >= mid:
            right.append(item)
        else:
            # 小于基准值放左边
            left.append(item)
    # 使用迭代进行比较
    return sort(left) + [mid] + sort(right)

#非递归排序算法
def quicksortUnRecur( nums, beg, end):
        if beg >= end:
            return nums
        stack = [beg, end]
        while stack:
            beg, end = stack.pop(0), stack.pop(0)
            if beg >= end:
                continue
            i, pivot = beg-1, nums[end]
            for j in range(beg, end+1):
                if nums[j] <= pivot:
                    i += 1
                    nums[i], nums[j] = nums[j], nums[i]
            stack.extend([beg, i-1, i+1, end])

b = [11, 99, 33, 69, 77, 88, 55, 11, 33, 36, 39, 66, 44, 22]
print sort(b)
Python
Copy

三、直接插入排序

insertionSort.gif

1.思路

它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

2.两种写法

有两种写法但是本质是一样的：
(1)标准的：不交换

  • 设置一层循环,可以从0，也可以从1，都一样
  • 然后设一个变量key=arr[i]，key用来记录，不交换，让后加while

(2)参考冒泡排序：交换

  • 设置一层循环,可以从0，也可以从1，都一样
  • 在设置一层循环，注意使用倒叙range(i-1, -1, -1)，然后进行交换

(1)标准的：不交换

# -*- coding: UTF-8 -*-
def sort(arr): 
    l = len(arr)
    for i in range(1, l): 
        key = arr[i] 
        j = i-1
        while j >=0 and key < arr[j] : 
                arr[j+1] = arr[j] 
                j -= 1
        arr[j+1] = key 
arr = [12, 11, 13, 5, 6] 
sort(arr) 
print(arr)
Python
Copy

(2)参考冒泡排序：交换

# -*- coding: UTF-8 -*-
def insert(arr):
    l = len(arr)
    for i in range(l):
        for j in range(i-1, -1, -1):
            if arr[j] > arr[j+1]:
                arr[j+1], arr[j] = arr[j], arr[j+1]
            else:
                break
arr = [9, 5, 6, 7, 8 ]
insert(arr)
print arr
Python
Copy

四、希尔排序

Sorting_shellsort_anim.gif

1.思路

希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法

# -*- coding: UTF-8 -*-

def shellSort(arr):
    n = len(arr)
    gap = int(n / 2)
    while gap > 0:
        for i in range(gap, n):
            temp = arr[i]
            j = i
            while j >= gap and arr[j - gap] > temp:
                arr[j] = arr[j - gap]
                j -= gap
            arr[j] = temp
        gap = int(gap / 2)


arr = [12, 34, 54, 2, 3]
shellSort(arr)
print arr
Python
Copy

五、简单选择排序

selectionSort.gif

1.思路

选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。

# -*- coding: UTF-8 -*-
def selectsort(arr):
    l = len(arr)
    for i in range(l):
        min_idx = i
        for j in range(i + 1, l):
            if arr[min_idx] > arr[j]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
        
arr = [64, 25, 12, 22, 11]
selectsort(arr)
print (arr)
Python
Copy

六、堆排序

1.思路
# -*- coding: UTF-8 -*-
def heapify(arr, n, i): 
    largest = i  
    l = 2 * i + 1     # left = 2*i + 1 
    r = 2 * i + 2     # right = 2*i + 2 
  
    if l < n and arr[i] < arr[l]: 
        largest = l 
  
    if r < n and arr[largest] < arr[r]: 
        largest = r 
  
    if largest != i: 
        arr[i],arr[largest] = arr[largest],arr[i]  # 交换
  
        heapify(arr, n, largest) 
  
def heapSort(arr): 
    n = len(arr) 
  
    # Build a maxheap. 
    for i in range(n, -1, -1): 
        heapify(arr, n, i) 
  
    # 一个个交换元素
    for i in range(n-1, 0, -1): 
        arr[i], arr[0] = arr[0], arr[i]   # 交换
        heapify(arr, i, 0) 
  
arr = [ 12, 11, 13, 5, 6, 7] 
heapSort(arr)
print arr
Python
Copy

七、归并排序

20180715160830460.png

1.思路

归并排序采用分而治之的原理：
一、将一个序列从中间位置分成两个序列；
二、在将这两个子序列按照第一步继续二分下去；
三、直到所有子序列的长度都为1，也就是不可以再二分截止。这时候再两两合并成一个有序序列即可。

# -*- coding: UTF-8 -*-
def merge(a, b):
    c = []
    h = j = 0
    while j < len(a) and h < len(b):
        if a[j] < b[h]:
            c.append(a[j])
            j += 1
        else:
            c.append(b[h])
            h += 1

    if j == len(a):
        for i in b[h:]:
            c.append(i)
    else:
        for i in a[j:]:
            c.append(i)

    return c


def merge_sort(lists):
    if len(lists) <= 1:
        return lists
    middle = len(lists)/2
    left = merge_sort(lists[:middle])
    right = merge_sort(lists[middle:])
    return merge(left, right)


if __name__ == '__main__':
    a = [4, 7, 8, 3, 5, 9]
    print merge_sort(a)
Python
Copy

八、基数排序

1.思路
# -*- coding: UTF-8 -*-
Python
Copy

12095757-775cf861406644bfad60ff2763f499e4.png
WX20201020-200832@2x.png
WX20201020-200847@2x.png