python实现八大排序算法（1）

排序

排序是计算机内经常进行的一种操作，其目的是将一组”无序”的记录序列调整为”有序”的记录序列。分内部排序和外部排序。若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序。反之，若参加排序的记录数量很大，整个序列的排序过程不可能完全在内存中完成，需要访问外存，则称此类排序问题为外部排序。内部排序的过程是一个逐步扩大记录的有序序列长度的过程。

看图使理解更清晰深刻：

假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，ri=rj，且ri在rj之前，而在排序后的序列中，ri仍在rj之前，则称这种排序算法是稳定的；否则称为不稳定的。

常见排序算法

快速排序、希尔排序、堆排序、直接选择排序不是稳定的排序算法，而基数排序、冒泡排序、直接插入排序、折半插入排序、归并排序是稳定的排序算法

本文将用Python实现冒泡排序、插入排序、希尔排序、快速排序、直接选择排序、堆排序、归并排序、基数排序这八大排序算法。

1. 冒泡排序（Bubble Sort）

算法原理：

已知一组无序数据a[1]、a[2]、……a[n]，需将其按升序排列。首先比较a[1]与a[2]的值，若a[1]大于a[2]则交换两者的值，否则不变。再比较a[2]与a[3]的值，若a[2]大于a[3]则交换两者的值，否则不变。再比较a[3]与a[4]，以此类推，最后比较a[n-1]与a[n]的值。这样处理一轮后，a[n]的值一定是这组数据中最大的。再对a[1]~a[n-1]以相同方法处理一轮，则a[n-1]的值一定是a[1]~a[n-1]中最大的。再对a[1]~a[n-2]以相同方法处理一轮，以此类推。共处理n-1轮后a[1]、a[2]、……a[n]就以升序排列了。降序排列与升序排列相类似，若a[1]小于a[2]则交换两者的值，否则不变，后面以此类推。 总的来讲，每一轮排序后最大（或最小）的数将移动到数据序列的最后，理论上总共要进行n(n-1）/2次交换。

优点：稳定；
缺点：慢，每次只能移动相邻两个数据。

python代码实现：

#!/usr/bin/env python#coding:utf-8'''file:python-8sort.pydate:9/1/17 9:03 AMauthor:lockeyemail:lockey@123.comdesc:python实现八大排序算法'''lst1 = [2,5435,67,445,34,4,34]def bubble_sort_basic(lst1): lstlen = len(lst1);i = 0 while i < lstlen:  for j in range(1,lstlen):   if lst1[j-1] > lst1[j]:   #对比相邻两个元素的大小，小的元素上浮    lst1[j],lst1[j-1] = lst1[j-1],lst1[j]  i += 1  print 'sorted{}: {}'.format(i, lst1) print '-------------------------------' return lst1bubble_sort_basic(lst1)