一、排序的基本概念和分类所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。排序算法，就是如何使得记录按照要求排列的方法。排序的稳定性：经过某种排序后，如果两个记录序号同等，且两者在原无序记录中的先后秩序依然保持不变，则称所使用的排序方法是稳定的，反之是不稳定的。内排序和外排序内排序：排序过程中，待排序的所有记录全部放在内存中外排序：排序过程中，使用到了外部存储。通常讨论的都是内排序。影响内排序算法性能的三个因素： 时间复杂度：即时间性能，高效率的排序算法应该是具有尽可能少的关键字比较次数和记录的移动次数 空间复杂度：主要是执行算法所需要的辅助空间，越少越好。 算法复杂性。主要是指代码的复杂性。根据排序过程中借助的主要操作，可把内排序分为： 插入排序 交换排序 选择排序 归并排序按照算法复杂度可分为两类： 简单算法：包括冒泡排序、简单选择排序和直接插入排序 改进算法：包括希尔排序、堆排序、归并排序和快速排序以下的七种排序算法只是所有排序算法中最经典的几种，不代表全部。二、 冒泡排序冒泡排序（bubble sort）：时间复杂度o(n^2)交换排序的一种。其核心思想是：两两比较相邻记录的关键字，如果反序则交换，直到没有反序记录为止。其实现细节可以不同，比如下面3种：1.最简单排序实现:bubble_sort_simple2.冒泡排序:bubble_sort3.改进的冒泡排序:bubble_sort_advance
#!/usr/bin/env python
# -*- coding:utf-8 -*-
# author: liu jiang
# python 3.5
# 冒泡排序算法
class sqlist:
def init(self, lis=none):
self.r = lis
def swap(self, i, j):
“””定义一个交换元素的方法，方便后面调用。”””
temp = self.r[i]
self.r[i] = self.r[j]
self.r[j] = temp
def bubble_sort_simple(self):
“””
最简单的交换排序，时间复杂度o(n^2)
“””
lis = self.r
length = len(self.r)
for i in range(length):
for j in range(i+1, length):
if lis[i] > lis[j]:
self.swap(i, j)
def bubble_sort(self):
“””
冒泡排序，时间复杂度o(n^2)
“””
lis = self.r
length = len(self.r)
for i in range(length):
j = length-2
while j >= i:
if lis[j] > lis[j+1]:
self.swap(j, j+1)
j -= 1
def bubble_sort_advance(self):
“””
冒泡排序改进算法，时间复杂度o(n^2)
设置flag，当一轮比较中未发生交换动作，则说明后面的元素其实已经有序排列了。
对于比较规整的元素集合，可提高一定的排序效率。
“””
lis = self.r
length = len(self.r)
flag = true
i = 0
while i < length and flag:
flag = false
j = length - 2
while j >= i:
if lis[j] > lis[j + 1]:
self.swap(j, j + 1)
flag = true
j -= 1
i += 1
def str(self):
ret = “”
for i in self.r:
ret += ” %s” % i
return ret
if name == ‘main’:
sqlist = sqlist([4,1,7,3,8,5,9,2,6])
# sqlist.bubble_sort_simple()
# sqlist.bubble_sort()
sqlist.bubble_sort_advance()
print(sqlist)
三、简单选择排序简单选择排序（simple selection sort）:时间复杂度o(n^2)通过n-i次关键字之间的比较，从n-i+1个记录中选出关键字最小的记录，并和第i（1 temp and j >= 0:
lis[j+1] = lis[j]
j -= 1
lis[j+1] = temp
def str(self):
ret = “”
for i in self.r:
ret += ” %s” % i
return ret
if name == ‘main’:
sqlist = sqlist([4, 1, 7, 3, 8, 5, 9, 2, 6, 0])
sqlist.insert_sort()
print(sqlist)
该算法需要一个记录的辅助空间。最好情况下，当原始数据就是有序的时候，只需要一轮对比，不需要移动记录，此时时间复杂度为o(n)。然而，这基本是幻想。
#!/usr/bin/env python
# -*- coding:utf-8 -*-
# author: liu jiang
# python 3.5
# 希尔排序
class sqlist:
def init(self, lis=none):
self.r = lis
def shell_sort(self):
“””希尔排序”””
lis = self.r
length = len(lis)
increment = len(lis)
while increment > 1:
increment = int(increment/3)+1
for i in range(increment+1, length):
if lis[i] < lis[i - increment]:
temp = lis[i]
j = i - increment
while j >= 0 and temp < lis[j]:
lis[j+increment] = lis[j]
j -= increment
lis[j+increment] = temp
def str(self):
ret = ""
for i in self.r:
ret += " %s" % i
return ret
if name == 'main':
sqlist = sqlist([4, 1, 7, 3, 8, 5, 9, 2, 6, 0,123,22])
sqlist.shell_sort()
print(sqlist)
六、堆排序堆是具有下列性质的完全二叉树：每个分支节点的值都大于或等于其左右孩子的值，称为大顶堆；每个分支节点的值都小于或等于其做右孩子的值，称为小顶堆；因此，其根节点一定是所有节点中最大（最小）的值。
#!/usr/bin/env python
# -*- coding:utf-8 -*-
# author: liu jiang
# python 3.5
# 堆排序
class sqlist:
def init(self, lis=none):
self.r = lis
def swap(self, i, j):
“””定义一个交换元素的方法，方便后面调用。”””
temp = self.r[i]
self.r[i] = self.r[j]
self.r[j] = temp
def heap_sort(self):
length = len(self.r)
i = int(length/2)
# 将原始序列构造成一个大顶堆
# 遍历从中间开始，到0结束，其实这些是堆的分支节点。
while i >= 0:
self.heap_adjust(i, length-1)
i -= 1
# 逆序遍历整个序列，不断取出根节点的值，完成实际的排序。
j = length-1
while j > 0:
# 将当前根节点，也就是列表最开头，下标为0的值，交换到最后面j处
self.swap(0, j)
# 将发生变化的序列重新构造成大顶堆
self.heap_adjust(0, j-1)
j -= 1
def heap_adjust(self, s, m):
“””核心的大顶堆构造方法，维持序列的堆结构。”””
lis = self.r
temp = lis[s]
i = 2*s
while i = lis[i]:
break
lis[s] = lis[i]
s = i
i *= 2
lis[s] = temp
def str(self):
ret = “”
for i in self.r:
ret += ” %s” % i
return ret
if name == ‘main’:
sqlist = sqlist([4, 1, 7, 3, 8, 5, 9, 2, 6, 0, 123, 22])
sqlist.heap_sort()
print(sqlist)
堆排序的运行时间主要消耗在初始构建堆和重建堆的反复筛选上。其初始构建堆时间复杂度为o(n)。正式排序时，重建堆的时间复杂度为o(nlogn)。所以堆排序的总体时间复杂度为o(nlogn)。堆排序对原始记录的排序状态不敏感，因此它无论最好、最坏和平均时间复杂度都是o(nlogn)。在性能上要好于冒泡、简单选择和直接插入算法。空间复杂度上，只需要一个用于交换的暂存单元。但是由于记录的比较和交换是跳跃式的，因此，堆排序也是一种不稳定的排序方法。此外，由于初始构建堆的比较次数较多，堆排序不适合序列个数较少的排序工作。七、归并排序归并排序（merging sort）：建立在归并操作上的一种有效的排序算法,该算法是采用分治法（pide and conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
#!/usr/bin/env python
# -*- coding:utf-8 -*-
# author: liu jiang
# python 3.5
# 归并排序
class sqlist:
def init(self, lis=none):
self.r = lis
def swap(self, i, j):
“””定义一个交换元素的方法，方便后面调用。”””
temp = self.r[i]
self.r[i] = self.r[j]
self.r[j] = temp
def merge_sort(self):
self.msort(self.r, self.r, 0, len(self.r)-1)
def msort(self, list_sr, list_tr, s, t):
temp = [none for i in range(0, len(list_sr))]
if s == t:
list_tr[s] = list_sr[s]
else:
m = int((s+t)/2)
self.msort(list_sr, temp, s, m)
self.msort(list_sr, temp, m+1, t)
self.merge(temp, list_tr, s, m, t)
def merge(self, list_sr, list_tr, i, m, n):
j = m+1
k = i
while i lis[high]:
self.swap(low, high)
if lis[m] > lis[high]:
self.swap(high, m)
if lis[m] > lis[low]:
self.swap(m, low)
pivot_key = lis[low]
# temp暂存pivot_key的值
temp = pivot_key
while low < high:
while low < high and lis[high] >= pivot_key:
high -= 1
# 直接替换，而不交换了
lis[low] = lis[high]
while low < high and lis[low]