基于python的七种经典排序算法

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

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

排序的稳定性：

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

内排序和外排序

内排序：排序过程中，待排序的所有记录全部放在内存中 外排序：排序过程中，使用到了外部存储。 通常讨论的都是内排序。

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

? ? ?

时间复杂度：即时间性能，高效率的排序算法应该是具有尽可能少的关键字比较次数和记录的移动次数

空间复杂度：主要是执行算法所需要的辅助空间，越少越好。

算法复杂性。主要是指代码的复杂性。

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

? ? ? ?

插入排序

交换排序

选择排序

归并排序

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

? ?

简单算法：包括冒泡排序、简单选择排序和直接插入排序

改进算法：包括希尔排序、堆排序、归并排序和快速排序

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

二、 冒泡排序

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

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

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

1. 2. 3.

最简单排序实现:bubble_sort_simple

冒泡排序:bubble_sort

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