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

所謂排序，就是使一串記錄，按照其中的某個或某些關(guān)鍵字的大小，遞增或遞減的排列起來的操作。排序算法，就是如何使得記錄按照要求排列的方法。

排序的穩(wěn)定性：

經(jīng)過某種排序后，如果兩個記錄序號同等，且兩者在原無序記錄中的先后秩序依然保持不變，則稱所使用的排序方法是穩(wěn)定的，反之是不穩(wěn)定的。

內(nèi)排序和外排序

內(nèi)排序：排序過程中，待排序的所有記錄全部放在內(nèi)存中

外排序：排序過程中，使用到了外部存儲。

通常討論的都是內(nèi)排序。

影響內(nèi)排序算法性能的三個因素：

根據(jù)排序過程中借助的主要操作，可把內(nèi)排序分為：

按照算法復(fù)雜度可分為兩類：

以下的七種排序算法只是所有排序算法中最經(jīng)典的幾種，不代表全部。

二、 冒泡排序

冒泡排序（Bubble sort）：時間復(fù)雜度O(n^2)

交換排序的一種。其核心思想是：兩兩比較相鄰記錄的關(guān)鍵字，如果反序則交換，直到?jīng)]有反序記錄為止。

其實現(xiàn)細節(jié)可以不同，比如下面3種：

1.最簡單排序?qū)崿F(xiàn):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):    """定義一個交換元素的方法，方便后面調(diào)用。"""    temp = self.r[i]    self.r[i] = self.r[j]    self.r[j] = temp  def bubble_sort_simple(self):    """    最簡單的交換排序，時間復(fù)雜度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):    """    冒泡排序，時間復(fù)雜度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):    """    冒泡排序改進算法，時間復(fù)雜度O(n^2)    設(shè)置flag，當(dāng)一輪比較中未發(fā)生交換動作，則說明后面的元素其實已經(jīng)有序排列了。    對于比較規(guī)整的元素集合，可提高一定的排序效率。    """    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)