基于python的七种经典排序算法（推荐）

一、排序的基本概念和分类

所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。排序算法，就是如何使得记录按照要求排列的方法。

排序的稳定性：

经过某种排序后，如果两个记录序号同等，且两者在原无序记录中的先后秩序依然保持不变，则称所使用的排序方法是稳定的，反之是不稳定的。

内排序和外排序

内排序：排序过程中，待排序的所有记录全部放在内存中

外排序：排序过程中，使用到了外部存储。

通常讨论的都是内排序。

影响内排序算法性能的三个因素：

根据排序过程中借助的主要操作，可把内排序分为：

按照算法复杂度可分为两类：

以下的七种排序算法只是所有排序算法中最经典的几种，不代表全部。

二、 冒泡排序

冒泡排序（Bubble sort）：时间复杂度O(n^2)

交换排序的一种。其核心思想是：两两比较相邻记录的关键字，如果反序则交换，直到没有反序记录为止。

其实现细节可以不同，比如下面3种：

1.最简单排序实现:bubble_sort_simple

2.冒泡排序:bubble_sort

3.改进的冒泡排序: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 retif __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)