排序算法详解与python实现

2017-11-05  本文已影响1235人  Crystalajj

Note:
写后感：
理解算法思想很重要！
理解算法思想很重要！
理解算法思想很重要！
之后尝试自己独立码代码对算法的理解更深刻！

本文章所有算法默认从小到大排序。

1. 冒泡排序(Bubble Sort)

自然语言描述

按照列表中待排序的先后顺序，依次比较相邻的两个数，若两者是升序则不做任何操作，否则交换两者位置。

核心算法举例

以第一趟为例
1 5 7 3 9 2 6 8 1 与 5比较，不变
1 5 7 3 9 2 6 8 5 与 7比较，不变
1 5 3 7 9 2 6 8 7 与 3比较，交换位置
1 5 3 7 9 2 6 8 7 与 9比较，不变
1 5 3 7 2 9 6 8 9 与 2比较， 交换位置
1 5 3 7 2 6 9 8 9 与 6比较，交换位置
1 5 3 7 2 6 8 9 9 与 8比较，交换位置
所以第一趟结束后，排序结果为
1 5 3 7 2 6 8 9 9为最大数，后续不需要比较

算法优劣分析

算法实现

#-*-coding=UTF-8-*-
class BubbleSort:
    def __init__(self,list_=[]):
        self.list_ = list_
    def get_current_list(self):
        return self.list_
    def ascent_sort(self):
        for i in range(0,len(self.list_)-1):
            for j in range(0, len(self.list_)-i-1):
                if self.list_[j]>self.list_[j+1]:
                    temp = self.list_[j]
                    self.list_[j] = self.list_[j+1]
                    self.list_[j+1] = temp

#实例化
list1 = BubbleSort([1,8,4,9,2])
print list1.get_current_list()
list1.ascent_sort()
print list1.get_current_list()

2. 选择排序算法(Selection Sort)

自然语言描述

核心算法举例

第二趟比较为例(以找最小数为例)
此时min_index = 1
1 7 5 9 4
7 与 5 作比较，min_index更新为2
5 与 9 作比较，min_index不变
5 与 4 作比较，min_index更新为4
将index = 4与index=1的元素交换位置
1 4 5 9 7

算法优劣分析

算法实现

#-*-coding = utf-8-*-
class SelectionSort:
    def __init__(self,list_=[]):
        self.list_ = list_
    def get_current_list(self):
        return self.list_
    def ascent_sort(self):
        for i in range(0,len(self.list_)-1):
            min_index, swap_temp = i, i
            for j in range(i, len(self.list_)-1):
                if self.list_[min_index] > self.list_[j+1]:
                    min_index = j + 1
            swap_temp = self.list_[min_index]
            self.list_[min_index] = self.list_[i]
            self.list_[i] = swap_temp
        return self.list_
#实例化
list1 = SelectionSort([1,7,4,9,2])
print list1.get_current_list()
list1.ascent_sort()
print list1.get_current_list()

3. 直接插入算法(Insertion Sort)

自然语言描述

在前面已经排好序的列表中插入新元素。步骤：

核心算法举例

第二趟比较为例
此时 current_value = 1
5 7 1
current_value = 1 与7作比较
5 7 7
current_value = 1 与5作比较
5 5 7
将 current_value = 1 插入
1 5 7

算法优劣分析

插入排序适用于数量较小，部分或者全部排序过的列表。尽管插入排序的时间复杂度也是O(n²)，但一般情况下，插入排序会比冒泡排序快一倍，要比选择排序还要快一点。并且，直接插入排序在对几乎已经排好序的数据操作时，效率高，可以达到线性排序的效率。

算法实现

#-*-coding = UTF-8-*-
class InsertionSort:
    def __init__(self,list_=[]):
        self.list_ = list_
    def get_current_list(self):
        return self.list_
    def ascent_sort(self):
        for i in range(1,len(self.list_)):
            position = i
            current_value = self.list_[i]
            while position>0 and self.list_[position-1]>current_value:
                self.list_[position] = self.list_[position-1]
                position = position - 1
            self.list_[position] = current_value
        return self.list_
#实例化
list1 = InsertionSort([1,9,3,7])
print list1.get_current_list()
list1.ascent_sort()
print list1.get_current_list()

4. 希尔排序(Shell Sort)

自然语言描述

直接插入算法一趟只能为数据移动一位，比较低效。希尔排序作为直接插入算法的优化，又称缩小增量排序、递减增量排序。

以步长分区，对跳过步长的数进行直接插入算法排序，直至步长为1。

步长是希尔排序的精髓，已知的最好步长序列是由Sedgewick提出的 1，5，19，41，109，...

核心算法举例

原列表：[4,6,8,2,9,3,7,5,1]
步长增量：9/2=4, 4/2=2, 2/2=1 (Note: 取列表长度的一半作为最初步长，这里的步长使用的是Donald Shell的建议)
第一趟(步长为4)：

原列表 4 6 8 2 9 3 7 5 1，分组后为：
4 6 8 2
9 3 7 5
1
排序后为：
1 3 7 2
4 6 8 5
9
即排序后列表顺序为：

1 3 7 2 4 6 8 5 9

第二趟(步长为2)

待排序列表1 3 7 2 4 6 8 5 9，分组后为：
1 3
7 2
4 6
8 5
9
排序后为：
1 2
4 3
7 5
8 6
9
即排序后列表顺序为：
1 2 4 3 7 5 8 6 9

第三趟(步长为1), 即直接插入排序

待排序列表1 2 4 3 7 5 8 6 9
排序后列表顺序为：1 2 3 4 5 6 7 8 9

算法优劣分析

算法实现

巧记：将直接插入算法的步长从1改为gap，加入限制条件gap > 0即可

#-*-coding = utf-8 -*-
class ShellSort():
    def __init__(self, list_=[]):
        self.list_ = list_
    def get_current_list(self):
        return self.list_
    def ascent_sort(self):
        gap = len(self.list_)/2
        while gap > 0:
            for i in range(gap, len(self.list_)):
                current_value = self.list_[i]
                position = i    
                while position >0 and self.list_[position - gap] > current_value:
                    self.list_[position] = self.list_[position - gap]
                    position = position - gap
                self.list_[position] = current_value
            gap = gap/2
        return self.list_

list1 = ShellSort([1,9,3,2,5,8])
print list1.get_current_list()
list1.ascent_sort()
print list1.get_current_list()

5. 归并排序(Merge Sort)

自然语言描述

将两个有序表合并成一个有序表。归并排序算法依赖于归并操作。


from Wikipedia

两个有序表，left = [0,3,5,7], right = [1,4]，
合成的有序列表result = []
left[0] < right[0] ----> result = [0]
left[1] > right[0] ----> result = [0,1]
left[1] < right[1] ----> result = [0,1,3]
left[2] > right[1] ----> result = [0,1,3,4]
此时right[]为空，将left[]剩余的元素依次放入result列表中：result = [0,1,3,4,5,7]

两种核心算法

递归法

递归算法思想参考这里

设计递归，将复杂的问题分解为最小规模子问题。

  • 将列表分解为 两个更小的列表。
  • 递归分解，将更小的列表继续分解，直到达到最小规模，也就是只有一个元素的时候。
  • 对已经排序好的列表 进行合并。单个元素的列表，认为是已经排序好的。
from Wikipedia
递归python实现
#-*-coding=utf-8-*-
#递归算法
def mergeSort(seq=[]):
    if len(seq) == 1:
        return seq
    else:
        mid = len(seq)/2
        left = []
        right = []
        left = mergeSort(seq[:mid])
        right = mergeSort(seq[mid:])
        return merge(left,right)
#将排好序的
def merge(left=[],right=[]):
    #i, j are index for left and right seperately
    i, j = 0,0
    result = []
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i = i + 1
        else:
            result.append(right[j])
            j = j + 1
    #将剩余的部分依次加入result
    result = result + left[i:]
    result = result + right[j:]
    return result

#实例化
list1 = [2,6,8,1,3,9,4]
print list1
print mergeSort(list1)
#time consume
import random,time
start_time = time.time()
seq = random.sample(range(10000), 10000) #random.sample(取值范围, 获取的个数)
result = mergeSort(seq)
print 'Time consume:{}'.format(time.time()-start_time)
非递归法（迭代法）

从最小的子问题开始解决，直到复杂的问题。要搞清每次排序归并的对象。


非递归算法（迭代法）

第一次：我们将数组分为 8个子数组 每个数组 1 个元素，对相邻的两个数组进行排序合并。
第二次：我们将数组分为 4个子数组 每个数组 2 个元素，对相邻的两个数组进行排序合并。
第三次：我们将数组分为 2个子数组 每个数组 4 个元素，对相邻的两个数组进行排序合并。
至此：排序完毕。
分析
第一步：每一次子数组的元素个数

k = 1 #子数组的个数
while k <len(seq):
k = k*2

第二步：确定要合并的两个相邻数组的区间[low:mid)[mid:height)

low = low(之前的low) +2k
mid = low(现在的low)+k
height = low(现在的low) + 2k
并且，
height不能越界（不能超过数组长度）；
mid不能大于height（mid大于height说明此时子数组个数不足k，那么这个时候该子数组不给予拆分直接pass，下图给予说明）

来自http://www.jianshu.com/p/3f27384387c1
非递归python实现
#-:-coding=utf-8-*-
class MergeSort:
    def __init__(self,seq=[]):
        self.seq = seq
    def get_current_seq(self):
        return self.seq
    def ascent_sort(self):
        k = 1         #子数组元素的个数
        while k < len(self.seq):
            low = 0
            while low < len(self.seq):
                height = min(low + 2*k, len(self.seq))
                mid = low + k
                if mid < height:
                    '''mergeSort'''
                    left = self.seq[low:mid]
                    right = self.seq[mid:height]
                    result =[]
                    i,j = 0,0
                    while i < len(left) and j < len(right):
                        if left[i] < right[j]:
                            result.append(left[i])
                            i += 1
                        else:
                            result.append(right[j])
                            j += 1
                    result = result + left[i:]
                    result = result + right[j:]
                    '''将原始数组的[low,height)替代为已经排好序的数组'''
                    self.seq[low:height] = result
                low = low + 2*i

            k *= 2
        return self.seq
list1 = MergeSort([3,5,2,1])
print list1.get_current_seq()
list1.ascent_sort()
print list1.get_current_seq()

6. 堆排序(HeapSort)

堆排序是对简单选择排序的一种优化。
堆的定义及性质见这里。

堆的主要性质：

堆排序需要解决两个主要的问题：

上一篇 下一篇

猜你喜欢

热点阅读