数据结构(5) 第五天快速排序、归并排序、堆排序、高级数据结构介绍:平衡二叉树、红黑树、B/B+树

时间：2019-04-04 19:41:23 阅读：200 评论：0 收藏：0 [点我收藏+]

01 上次课程回顾

希尔排序又叫减少增量排序

increasement = increasement / 3 + 1

02 快速排序思想

思想: 分治法 + 挖坑填数

分治法: 大问题分解成各个小问题,对小问题求解,使得大问题得以解决

03 快速排序代码实现

let arr = [23,123,34,5,123,5,5,3,2,3,1,46,234,123,123]

function quicksort(arr,start,end)

{

let i = start

let j = end

// 设置递归退出条件

if(start >= end) return

let benchmark = arr[start]

while(i != j)

{

while(i<j && arr[j] >= benchmark)

{

j--;

}

while(i<j && arr[i] <= benchmark)

{

i++;

}

if(i<j)

{

let t = arr[i]

arr[i] = arr[j]

arr[j] = t

}

arr[start] = arr[i]

arr[i] = benchmark

quicksort(arr,start,i-1)

quicksort(arr,i+1,end)

}

quicksort(arr,0,arr.length-1)

console.log(arr)

04 归并排序

归并排序基本思想: 将两个有序序列合并成一个有序序列

技术分享图片

将两个合成一个有序序列

06 堆排序思路

完全二叉树

知道完全二叉树(complete binary tree)的先序序列就可以确定它的唯一结构:

技术分享图片

堆:

大顶堆:

父节点比两个子节点大

小顶堆:

父节点比两个子节点都小

堆就是完全二叉树不过要满足条件:

给了我们一个数组就相当于给了我们一个完全二叉树他还不满足堆的条件

通过调整堆,初始化堆

数组个数除以2正好是最后一个子树

然后在这个子树里面进行交换形成堆

技术分享图片

08 web闲聊

socket套接字

补:高级数据结构:

二叉排序树:

一棵树左边比结点小右边比结点大

用来查找。

平衡二叉树:

二叉排序树可能退化成一种链表。

平衡二叉树左右子树差不能大于一(小于等于)

反转:

红黑树

技术分享图片

节点颜色: 红,黑
根节点必须是黑色的
红节点下边不能挂红结点
每一条路径的黑结点个数相等
NULL结点默认是黑色的

B树,B+树:

应用场景:

操作的不是内存里的数据

操作的是硬盘里的数据

高度有限

子节点很多(孩子最少几千个,不是二叉树)

应用:操作系统的文件系统数据库的数据文件

数据结构(5) 第五天快速排序、归并排序、堆排序、高级数据结构介绍:平衡二叉树、红黑树、B/B+树

原文：https://www.cnblogs.com/eret9616/p/10656418.html

踩

(0)

评论一句话评论（0）

分享档案

更多>

2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)

数据结构(5) 第五天 快速排序、归并排序、堆排序、高级数据结构介绍:平衡二叉树、红黑树、B/B+树

数据结构(5) 第五天快速排序、归并排序、堆排序、高级数据结构介绍:平衡二叉树、红黑树、B/B+树