大话数据结构第九章—排序

大家好，又见面了，我是你们的朋友全栈君。

马上要把大话数据结构这本书看完啦，现在已经对数据结构有了一种系统上的了解，后面的事情就疯狂练习力扣上的编程题目啦，第九章是本书的最后一章，却是以前我学数据结构最先学的部分—–排序。

排序

网页搜索之后的排序，商品页面的排序，是如何做到的呢？

本章将介绍7种排序算法：

冒泡排序，简单选择排序，直接插入排序属于简单算法。

快速排序，归并排序（merge sort），希尔排序，堆排序属于改进算法。

本文中都是升序排序哦~

1.冒泡排序

#bubble sorted
def bubble(array):
    if array == None or len(array) == 0:
        return -1
    for i in range(len(array)-1):
        for j in range(len(array)-1):
            if array[j] > array[j+1]:
                array[j],array[j+1] = array[j+1],array[j]
    return array

时间复杂度：o（n^2）

空间复杂度：o（1）

2.简单选择排序

选择一个数作为最小数，（比如选第一个数作为min），在后续数组中找到最小的数字，并交换位置。若没有，跳到第二个数字，继续进行比较。

代码如下：

#selection sort
def select(array):
    if array == None or len(array) == 0:
        return -1
    for i in range(len(array)-1):
        min_index = i
        for j in range(i,len(array)):
            if array[min_index] > array[j]:
                array[min_index],array[j] = array[j],array[min_index]
    return array

时间复杂度：o（n^2）

空间复杂度：o（1）

3.直接插入排序

插入排序（Insertion Sort）是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

所以insert需要的时间复杂度是o（n），排序（找插入空位）的时间复杂度是o（n），当然如果用binary search找空位的时间复杂度是o（logn）,总体的时间复杂度为o（n^2）或者是o（nlogn）。

代码如下：

def insert(list_a):
    for i in range(1,len(list_a)):
        cur = list_a[i]
        k = i

        while cur < list_a[k-1] and k > 0:#寻找空位
           list_a[k] = list_a[k-1]
           k -= 1                        #k记录的当前空位的位置

        list_a[k] = cur#插入

    return list_a

插入排序由于需要挪动空位后的元素，所以需要游标（存储现在正在进行插入的数据元素），需要记录元素下标。寻找插入空位这个代码得记住，感觉可以用在其他地方。

前三种方法都是简单的排序算法，比较他们的最坏的时间复杂度（序列初始为逆序），直接插入算法性能比冒泡和简单选择排序的性能要好。

4 堆排序（heap）

堆是具有下列性质的完全二叉树：

每个节点的值都大于或等于其左右孩子节点的值，叫大顶堆；

每个节点的值都小于或等于其左右孩子节点的值，称为小顶堆。

堆排序算法的步骤：

以大顶堆为例

1 将待排序的序列构成大顶堆。

2 此时最大值就是堆顶的根节点，将其移走（其实是将其与堆数组的末尾元素交换，此时末尾元素就是最大值）

3 将剩余的n-1个序列重新构造成一个堆，这样就可以得到从小到大的排序的有序序列。

要解决的关键问题就是如何建立堆！

建立堆（以实现小顶堆为例）

如何用数组来表示一个完全二叉树？

完全二叉树孩子节点和父亲节点的数组索引关系是酱紫的：

left_node = parent_node * 2 + 1

right_node = parent_node * 2 + 2

parent_node = (child_node – 1) // 2

所以需要实现让完全二叉树的每个节点都小于孩子节点才能建立小顶堆。

将一个随机数组变成小顶堆的python代码如下：

def min_heap(array,i):
    left = i*2+1
    right = i*2+2
    smaller = i
    if left < len(array) and array[left] < array[smaller]:
        smaller = left
    if right < len(array) and array[right] < array[smaller]:
        smaller = right
    if smaller != i:
        array[smaller],array[i] = array[i],array[smaller]
        min_heap(array,smaller)

def build_heap(arr):
    for i in range(len(arr)//2,-1,-1):
        min_heap(arr,i)
    return arr

时间复杂度o(nlogn)。

如果你要往已经生成的小顶堆中加入数据元素：

def push(array,i):
#这里的i是输入序列的最后一位的索引值，也是你要插入的数据。
    parent = (i-1)//2
    large = i
    if parent >= 0 and array[parent] > array[i]:
        large = parent
    if large != i:
        array[large],array[i]= array[i],array[large]
        push(array,large)

时间复杂度都是o（logn）。

python中heapq包，专门完成堆的一些操作。

import heapq

heap = []                  #生成的是小顶堆

heappush(heap,item)

item = heappop(heap)

item = heap[0]

heapify(x) #将list转换为heap

item = heapreplace(heap,item) #先pop再插入item

有了这些可以应用它做一些编程题目：

比如实现堆排序，寻找序列中的最小k项，合并k个有序序列等。

5 归并排序

先分割序列，再将分割后的序列进行合并

def merge(a,b):
    c = []
    index_a,index_b = 0,0
    while index_a < len(a) and index_b < len(b):
        if a[index_a] > b[index_b]:
            c.append(b[index_b])
            index_b += 1
        elif a[index_a] <= b[index_b]:
            c.append(a[index_a])
            index_a += 1

    if index_a < len(a):
        c.extend(a[index_a:])
    if index_b < len(b):
        c.extend(b[index_b:])

    return c

def merge_sort(list_a):

    if len(list_a) == 0 or len(list_a) == 1:
        return list_a

    mid = len(list_a)//2
    a = merge_sort(list_a[:mid])
    b = merge_sort(list_a[mid:])

    return merge(a,b)

时间复杂度：o（nlogn）

6 快速排序

通过一趟排序将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序的目的。这是不稳定的算法，因为时间复杂度最坏o(n^2)，最好和平均情况是o(nlogn)。

def paixu(a,b):
    c = a+b
    p = (len(a)+len(b))//2
    end = len(a)+len(b)-1
    for start in range(p):
        for i in range(p, end + 1):
            if c[start] >= c[i] and start <= len(a) - 1:
                c[start], c[i] = c[i], c[start]
    return c


def q_paixu(a):
    if len(a) <= 1:
        return a
    else:
        p = len(a)//2
        j = q_paixu(a[0:p])
        b = q_paixu(a[p:len(a)])

    return paixu(j,b)

7 希尔排序

它就是直接插入排序的进阶、这个网址解释的很清楚。

https://blog.csdn.net/u014745194/article/details/72783357

关于这七个排序算法的稳定性和时间复杂度：

https://www.cnblogs.com/nannanITeye/archive/2013/04/11/3013737.html

选择排序、快速排序、希尔排序、堆排序不是稳定的排序算法，

冒泡排序、插入排序、归并排序和基数排序是稳定的排序算法。

首先，排序算法的稳定性大家应该都知道，通俗地讲就是能保证排序前两个相等的数据其在序列中的先后位置顺序与排序后它们两个先后位置顺序相同。再简单具体一点，如果A i == A j，Ai 原来在 Aj 位置前，排序后 Ai  仍然是在 Aj 位置前。 

插入排序：第n趟前n+1个有序

选择排序：第n趟前n个位置正确

快速排序：第n趟有n个元素位置正确

堆排序：第n趟前或后n个位置正确