算法导论笔记（四）—— 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 >>

vv