## dawnchengx 查看完整档案

|    |
_ | |__ _ _ __ _ | '_ \| | | |/ _` | | |_) | |_| | (_| | |_.__/ \__,_|\__, | |___/ 个人简介什么都没有

### 个人动态

dawnchengx 发布了文章 · 2018-12-27

1.1 比较排序：

1.2 非比较排序：

## 2.基础概念解读

2.1 时间复杂度

O(n^2) 大O 表示该排序算法增量情况 <= n^2
o(n^2) 小o 表示该排序算法增量情况 < n^2
θ(n^2) 希腊字母theta 表示该排序算法增量情况 == n^2
ω(n^2) 希腊字母小欧米伽 表示该排序算法增量情况 > n^2
Ω(n^2) 希腊字母大欧米伽 表示该排序算法增量情况 >= n^2

2.2 稳定性

2.3 逆序对

## 4.代码实现（Java）

https://github.com/dawnchengx...

## 5.伪代码实现

5.1 基础冒泡排序

``````BasicBubbleSort(A)
for i=1 to A.length-1
for j=A.length down to i + 1
if A[j] < A[j-1]
exchange A[j] with A[j-1]``````

5.2 优化冒泡排序

``````OptimizeBubbleSort(A)
for i=1 to A.length-1
didSwap = false;
for j=A.length down to i + 1
if A[j] < A[j-1]
exchange A[j] with A[j-1]
didExchange = true
if didExchange == true
return``````

5.3 基础快速排序

``````BasicQuickSort(A, p, r)
if p < r
q = BasicPartition(A, p, r)
BasicQuickSort(A, p, q-1)
BasicQuickSort(A, q+1, r)

BasicPartition(A, p, r)
x = A[r]
i = p-1
for j=p to r-1
if A[j] <= x
i = i + 1
exchange A[i] with A[j]
exchange A[i+1] with A[r]
return i + 1``````

5.4 递归优化快速排序

``````RecuOptimizeQuickSort(A, sort, end)
if start < end
mid = RecuOptimizePartition(A, start, end)
RecuOptimizeQuickSort(A, start, mid-1)
RecuOptimizeQuickSort(A, start+1, end)
RecuOptimizePartition(A, start, end)
生成介于start和end之间的三个不重复的随机数r1,r2,r3
取A[r1],A[r2],A[r3]这三个数的中位数，并将该中位数的下标赋值给r0
x = A[r0]
i = start - 1
for j = start to end - 1
if A[j] <= x
i = i + 1
exchange A[i] with A[j]
exchange A[i+1] with A[end]
return i+1``````

5.5 循环优化快速排序

``````LoopOptimizeQuickSort(A)
stack = []
start = 0
end = A.length - 1
stack.push(start)
stack.push(end)
while stack.isNotEmpty()
end = stack.pop()
start = stack.pop()
if start < end
base = LoopOptimizePartition(A, start, end)
// 右半边
stack.push(base+1)
stack.push(end)
// 左半边
stack.push(start)
stack.push(base-1)
LoopOptimizePartition(A, start, end)
生成介于start和end之间的三个不重复的随机数r1,r2,r3
取A[r1],A[r2],A[r3]这三个数的中位数，并将该中位数的下标赋值给r0
x = A[r0]
i = start - 1
for j = start to end - 1
if A[j] <= x
i = i + 1
exchange A[i] with A[j]
exchange A[i+1] with A[end]
return i+1``````

5.6 基础插入排序

``````InsertionSort(A)
for j=2 to A.length
key = A[j]
i = j - 1
while i > 0 and A[i] > key
A[i+1] = A[i]
i = i - 1
A[i+1] = key``````

5.7 希尔优化插入排序

``````ShellInsertionSort(A)
increment = A.length
do {
increment = increment/3 + 1
for j = increment to A.length
key = A[j]
i = j - increment
while 0 <= i and A[i] > key
A[i+increment] = A[i]
i = i - increment
A[i+increment] = key
}while(1 < increment);``````

5.8 选择排序

``````SelectionSort(A)
for i=1 to n-1
min = i
for j=i+1 to n
if A[min] > A[j]
min = j
exchange A[min] with A[i]``````

5.9 二叉堆排序

``````HeapSort(A)
BuildMaxHeap(A)
for i = A.length downto 2
exchange A[1] with A[i]
A.heap-size = A.heap-size - 1
MaxHeapify(A, 1)
BuildMaxHeap(A)
A.heap-size = A.length
for i = A.length/2 downto 1
MaxHeapify(A, i)
MaxHeapify(A, i)
l = LEFT(i)
r = RIGHT(i)
if l <= a.heap-size and A[l] > A[i]
largest = l
else largest = i
if r <= A.heap-size and A[r] > A[largest]
largest = r
if largest != i
exchange A[i] with A[largest]
MaxHeapify(A, largest)
LEFT(i)
return 2i
RIGHT(i)
return 2i+1``````

5.10 多叉堆排序
5.11 归并排序

``````MergeSort(A, p, r)
if p < r
q = (p+r)/2 (向下取整)
MergeSort(A, p, q)
MergeSort(A, q+1, r)
Merge(A, p, q, r)
Merge(A, p, q, r)
n1 = q - p + 1
n2 = r - q
let L[1..n1+1] and R[1..n2 + 1] be new arrays
for i = 1 to n1
L[i] = A[p + i - 1]
for j = 1 to n2
R[j] = A[q + j]
L[n1+1] = 正无穷大
R[n2+1] = 正无穷大
i = 1
j = 1
for k = p to r
if L[i] <= R[j]
A[k] = L[i]
i = i + 1
else
A[k] = R[j]
j = j + 1``````

5.12 计数排序

``````CountingSort(A, B, k)
let C[0...k] be a new array
for i = 0 to k
C[i] = 0
for j = 1 to A.length
C[A[j]] = C[A[j]] + 1
for i = 1 to k
C[i] = C[i] + C[i-1]
for j = A.length downto 1
B[C[A[j]]] = A[j]
C[A[j]] = C[A[j]] - 1        ``````

5.13 基数排序
https://www.jianshu.com/p/68b...
5.14 桶排序

``````https://www.cnblogs.com/zer0Black/p/6169858.html
BucketSort(A)
n = A.length
let B[0.. n-1] be a new array
for i = 0 to n-1
make B[i] an empty list
for i = 1 to n
insert A[i] into list B[<nA[i]向下取整>]
for i = 0 to n-1
sort list B[i] with insertion sort
concatenate the lists B[0],B[1],...,B[n-1] together in order``````

dawnchengx 发布了文章 · 2018-12-17

## 一、Redis使用禁忌

Redis作为常驻内存的存储器，相对于常驻硬盘MySQL多了很多隐藏的禁忌，一不小心就会影响线上业务。

## 为什么会阻塞：

Redis作为高性能内存服务器在处理命令时为何使用单线程呢？

a. 导致主从切换

## a. flushallflushdb

flushall会清空所有db的数据
flushdb会清空当前db的所有数据

``````害怕生产环境被经验不足的工程师误操作怎么办？
① 使用 rename-command将flushall和flushdb改为一个随机字符串

① 如果AOF还没有重写，则在AOF中删除flushall或者flushdb

② 如果RDB还没有生成，马上备份RDB，然后载入RDB即可``````

## b. keys

keys会一次性获取所有的Redis key，如果一个Redis实例中的key很多就会执行很久，阻塞其他命令执行。

``````如果需要去遍历key该怎么办呢？
① 用scan去迭代遍历，比如每次取50个

① 使用 rename-command将keys改为一个随机字符串``````

c. hgetall

``````如果需要去遍历hash该怎么办呢？
① 用hscan去迭代遍历，比如每次取50个``````

d. del

``````4.x版本可以使用unlink开启新线程异步删除，但是要注意复制线程所带来的内存开销和cpu开销，在内存和cpu有足够剩余空间时才能使用

hash，可以使用hscan逐个删除
list，可以一个一个pop，或者使用LTRIM一次删除较少数据
set, 可以使用sscan逐个删除
zset，可以使用zscan逐个删除``````

e. sort

a. cpu饱和
cpu跑满，命令无法继续处理
b. 持久化阻塞
RDB和AOF重写时，需要fork当前线程，如果fork操作时间很长，就会阻塞主线程
AOF做fsync时，如果主线程发现距离上一次fsync成功超过2秒，为了数据安全性它会阻塞知道后台线程执行fsync操作完成。

dawnchengx 关注了专栏 · 2018-12-09

## 腾讯云技术社区

dawnchengx 关注了专栏 · 2018-12-09

## 前端修炼之路

dawnchengx 关注了专栏 · 2018-12-09

## ES2049 Studio

dawnchengx 关注了专栏 · 2018-12-09

## PHP安全实践

dawnchengx 关注了用户 · 2018-12-09

## 命名最头痛 @george_es

a == b ? a : b

dawnchengx 关注了专栏 · 2018-12-09

## 树莓派

dawnchengx 关注了专栏 · 2018-12-09

## 开源分布式关系型数据库 TiDB

TiDB 是一款定位于在线事务处理/在线分析处理（ HTAP: Hybrid Transactional/Analytical Processing）的融合型数据库产品，实现了一键水平伸缩，强一致性的多副本数据安全，分布式事务，实时 OLAP 等重要特性。同时兼容 MySQL 协议和生态，迁移便捷，运维成本极低。

dawnchengx 关注了专栏 · 2018-12-09

## 前端工匠公众号

#### 认证与成就

• 获得 1 次点赞
• 获得 0 枚徽章 获得 0 枚金徽章, 获得 0 枚银徽章, 获得 0 枚铜徽章

(ﾟ∀ﾟ　)

(ﾟ∀ﾟ　)