八大排序算法
分类方式
一.交换排序：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)
二、快速排序
1.递归排序算法
思路：
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)三、直接插入排序
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)(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四、希尔排序
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
五、简单选择排序
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)六、堆排序
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七、归并排序
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)
八、基数排序
1.思路
# -*- coding: UTF-8 -*-
