排序NB三人组

快速排序，堆排序，归并排序

1、快速排序

方法其实很简单：分别从初始序列“6  1  2 7  9  3  4  5 10  8”两端开始“探测”。先从右往左找一个小于6的数，再从左往右找一个大于6的数，然后交换他们。

这里可以用两个变量i和j，分别指向序列最左边和最右边。我们为这两个变量起个好听的名字“哨兵i”和“哨兵j”。刚开始的时候让哨兵i指向序列的最左边（即i=1）

指向数字6。让哨兵j指向序列的最右边（即j=10），指向数字8。

首先哨兵j开始出动。因为此处设置的基准数是最左边的数，所以需要让哨兵j先出动，这一点非常重要（请自己想一想为什么）。

哨兵j一步一步地向左挪动（即j--），直到找到一个小于6的数停下来。接下来哨兵i再一步一步向右挪动（即i++），直到找到一个数大于6的数停下来。

最后哨兵j停在了数字5面前，哨兵i停在了数字7面前。

再继续：

第二次交换结束，“探测”继续。哨兵j继续向左挪动，他发现了3（比基准数6要小，满足要求）之后又停了下来。

哨兵i继续向右移动，糟啦！此时哨兵i和哨兵j相遇了，哨兵i和哨兵j都走到3面前。说明此时“探测”结束。我们将基准数6和3进行交换。交换之后的序列如下。

到此第一轮“探测”真正结束。此时以基准数6为分界点，6左边的数都小于等于6，6右边的数都大于等于6。回顾一下刚才的过程，

其实哨兵j的使命就是要找小于基准数的数，而哨兵i的使命就是要找大于基准数的数，直到i和j碰头为止。

 OK，解释完毕。现在基准数6已经归位，它正好处在序列的第6位。此时我们已经将原来的序列，以6为分界点拆分成了两个序列，左边的序列是“3  1 2  5  4”，右边的序列是“9  7  10  8”。接下来还需要分别处理这两个序列。因为6左边和右边的序列目前都还是很混乱的。不过不要紧，我们已经掌握了方法，接下来只要模拟刚才的方法分别处理6左边和右边的序列即可。现在先来处理6左边的序列现吧。

 

 

left right

取一个数，从左边找一个数比该数大，从右边找比该

 

def partition(li,left,right):    tmp = li[left]    while left
     
      = tmp:# 从右边找比tmp小的数            right -=1 # 往左走一步        li[left] = li[right] # 把右边的值写到左边        print(li,'right')        while left
     

 

 

总共有logn层，每一层复杂度为n------>  时间复杂度O(nlogn)

 2、堆排序

序比快速排序的时

 

 

A是根节点，

叶子节点 是没有子节点的点  b c h i p q k l m n 

树的深度，最深有几层，如图有4层

树的度 就是这个树最多的节点数

 

 什么是二叉树

满二叉树和完全二叉树

二叉树的存储方式：

 

9编号为0  左孩子节点8的编号为1；右孩子7的编号为2

 大根堆和小根堆

堆的概念：

 

堆是一个完全二叉树

堆中每一个节点的值都必须大于等于(或小于等于)其子树中每一个节点的值

---------------

 

其实我们的堆排序算法就是抓住了堆的这一特点，每次都取堆顶的元素，将其放在序列最后面，然后将剩余的元素重新调整为最大堆，依次类推，最终得到排序的序列。

给定一个列表array=[16,7,3,20,17,8]，对其进行堆排序。

首先根据该数组元素构建一个完全二叉树，得到

每次所有堆的最后一个放堆顶

 i  j hight都是索引值

堆建完之后堆顶是最大的元素

# 堆排序def sift(li, low, high):    """    :param li: 列表    :param low: 堆的根节点位置    :param high: 堆的最后一个元素的位置    :return:    """    i = low # i最开始指向根节点     父节点    j = 2 * i + 1 # j开始是左孩子    tmp = li[low] # 把堆顶存起来    while j <= high: # 只要j位置有数        if j + 1 <= high and li[j+1] > li[j]: # 如果右孩子有并且比较大            j = j + 1  # j指向右孩子        if li[j] > tmp: # 如果左孩子或者右孩子大于tmp            li[i] = li[j] # 大的放堆顶            i = j           # 往下看一层　变成新的父节点            j = 2 * i + 1   # 新的子节点        else:       # tmp更大，把tmp放到i的位置上            li[i] = tmp     # 把tmp放到某一级领导位置上            break    else:        li[i] = tmp  # 把tmp放到叶子节点上def heap_sort(li):    n = len(li)    # //除法不管操作数为何种数值类型，总是会舍去小数部分，返回数字序列中比真正的商小的最接近的数字。    # range(start, stop[, step])    # 比如 range(5,-1,-1)  [5,4,3,2,1,0] 倒叙    # 创建堆    for i in range((n-2)//2, -1, -1):        # i表示建堆的时候调整的部分的根的下标        print(i)        sift(li, i, n-1)    # 建堆完成了---挨个出数    for i in range(n-1, -1, -1):        # i 指向当前堆的最后一个元素        li[0], li[i] = li[i], li[0]        sift(li, 0, i - 1) # i-1是新的highli = [i for i in range(100)]import randomrandom.shuffle(li)  # 打乱顺序print(li)heap_sort(li)print(li)

 -----------

 

-------------------

 

 堆排序--python内置模块

import heapq

# python 堆排序内置模块import heapq  # q-->queue优先队列import randomli = list(range(100))random.shuffle(li)print(li)heapq.heapify(li) # 建堆n = len(li)for i in range(n):    print(heapq.heappop(li),end=',')

堆排序-----topk问题 

问题描述：有 N (N>1000000)个数,求出其中的前K个最小的数（又被称作topK问题）。

思路3：大根堆

大根堆维护一个大小为K的数组，目前该大根堆中的元素是排名前K的数，其中根是最大的数。此后，每次从原数组中取一个元素与根进行比较，如小于根的元素，则将根元素替换并进行堆调整（下沉），即保证大根堆中的元素仍然是排名前K的数，且根元素仍然最大；否则不予处理，取下一个数组元素继续该过程。该算法的时间复杂度是O(N*logK)，一般来说企业中都采用该策略处理topK问题，因为该算法不需要一次将原数组中的内容全部加载到内存中，而这正是海量数据处理必然会面临的一个关卡。如果能写出代码，offer基本搞定。

# 堆排序def sift(li, low, high):    """    :param li: 列表    :param low: 堆的根节点位置    :param high: 堆的最后一个元素的位置    :return:    """    i = low # i最开始指向根节点    j = 2 * i + 1 # j开始是左孩子    tmp = li[low] # 把堆顶存起来    while j <= high: # 只要j位置有数        if j + 1 <= high and li[j+1] < li[j]: # 如果右孩子有并且比较大            j = j + 1  # j指向右孩子        if li[j] < tmp: # 如果左孩子或者右孩子大于tmp            li[i] = li[j] # 大的放堆顶            i = j           # 往下看一层            j = 2 * i + 1        else:       # tmp更大，把tmp放到i的位置上            li[i] = tmp     # 把tmp放到某一级领导位置上            break    else:        li[i] = tmp  # 把tmp放到叶子节点上def topk(li,k):    heap = li[0:k]    for i in range((k-2)//2,-1,-1):        sift(heap,i,k-1)    # 1.建堆    for i in range(k,len(li)-1):        if li[i]>heap[0]:            heap[0] = li[i]            sift(heap,0,k-1)    # 2.遍历    for i in range(k-1,-1,-1):        heap[0],heap[i] = heap[i],heap[0]        sift(heap,0,i-1)    # 3.出数    return heapli = [i for i in range(100)]import randomrandom.shuffle(li)  # 打乱顺序# 取出前10个数print(topk(li,10))

还有没有更简单的算法呢？答案是肯定的。

思路4：快速排序

利用快速排序的分划函数找到分划位置K，则其前面的内容即为所求。该算法是一种非常有效的处理方式，时间复杂度是O(N)（证明可以参考算法导论书籍）。对于能一次加载到内存中的数组，该策略非常优秀。如果能完整写出代码，那么相信面试官会对你刮目相看的。

归并排序

时间复杂度：O(nlogn)

空间复杂度：O(n)

假设两段有序的情况下

def merge(li,low,mid,high):    i = low    j = mid + 1    ltmp = []    while i<=mid and j<=high:        if li[i]

首先弄清楚递归的概念

# 递归的数据结构式栈先进后出def calc(n):    v = int(n/2)    print(v)    if v > 0:        calc(v)    print(n)calc(10)521012510

当遇到递归结束即然后执行递归后面的程序

print((0+1)//2) # 0print((1+2)//2) # 1

归并排序代码：

def merge(li,low,mid,high):    i = low    j = mid + 1    ltmp = []    while i<=mid and j<=high:        if li[i]

NB三人组小结