算法导论笔记(四)—— Chap 7 快速排序

快速排序

描述

对于数组nums[p..r]进行快速排序的三步分治步骤

  • 分解:数组被分解成两个(可能为空)子数组nums[p..q-1]和nums[q+1…r],使得前一个数组的元素都小于等于nums[q],nums[q]小于等于后一个数组中的每个元素。
  • 解决:通过递归调用快速排序,对子数组nums[p..q-1]和nums[q+1…r]进行排序
  • 合并:因为子数组都是原址排序的,所以不需要合并操作:数组nums[p..r]已经是有序

more >>

算法导论笔记(二)—— Chap 4 分治策略

分治策略

最大子数组

问题:给定数组A,寻找A的和最大的非空连续子数组

  • O(n^2)解法:A的子数组的个数共有n+n-1+n-2+….+2+1 = n(n+1)/2个。对于每个数组求和,并记录最大值,sum(A[i…j]) = sum(A[i…j-1]) + A[j]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
def max_subarray1(nums):
max_sum = min(nums)
left_idx, right_idx = 0, len(nums)
for i in range(len(nums)):
for j in range(i, len(nums)):
tmp_sum = 0
for k in range(i, j+1):
tmp_sum += nums[k]
if tmp_sum > max_sum:
max_sum = tmp_sum
left_idx = i
right_idx = j
return (left_idx, right_idx, max_sum)

more >>

算法导论笔记(一)—— Chap 2 算法基础

第2章 算法基础

插入排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
# 升序排列
import random
def insertion_sort1(nums):
'''
:type nums: List
:rtype: List
'''
for j in range(1,len(nums)):
key = nums[j]
i = j-1
while i>=0 and nums[i] > key:
nums[i+1] = nums[i]
i = i - 1
nums[i+1] = key
return nums
# 降序排列
def insertion_sort2(nums):
'''
:type nums: List
:rtype: List
'''
for j in range(1,len(nums)):
key = nums[j]
i = j-1
while i>=0 and nums[i] < key:
nums[i+1] = nums[i]
i = i - 1
nums[i+1] = key
return nums
if __name__ == '__main__':
nums = [random.randint(0,99) for _ in range(10)]
print nums
print insertion_sort1(nums)
print insertion_sort2(nums)

more >>

Shell学习笔记(一)

基本的bash shell命令

常见Linux目录名称

目录 用途
/ 虚拟目录的根目录
/bin 二进制目录,存放许多GUN用户级的工具
/boot 启动目录,存放启动文件
/dev 设备目录,Linux在这里创建用户目录
/etc 系统配置文件目录
/home 主目录,Linux在这里创建用户目录
/lib 库目录,存放系统和应用程序的库文件
/media 媒体目录,存放可移动媒体设备挂载点的地方
/mnt 挂载目录,另一个存放可移动设备挂载点的地方
/opt 可选目录,用于存放可选的软件包
/root 根主目录
/sbin 系统二进制目录,存放许多GUN管理员级工具
/tmp 临时目录,可以在该目录中创建和删除临时文件
/usr 用户安装软件的目录
/var 可变目录,用以存放经常变化的文件,比如日志文件

more >>