常用的排序算法

最近在leetcode上刷题,想回顾一下计算机编程的基本功排序。常用的排序算法(内部排序),按大类分可分为以下几种:插入排序、交换排序、选择排序、归并排序和计数排序五大类。下面用python代码简单实现一下这几种排序算法。

插入排序

插入排序(Insertion Sort)比较简单直观,原理是将为排序数据,在已排序序列中从后往前扫描,找到相应位置插入。

直接插入排序(Straight Insertion Sort)

1
2
3
4
5
6
7
8
def insertion_sort(nums):
for i in range(1, len(nums)):
j, key = i - 1, nums[i]
while j >= 0 and key < nums[j]:
nums[j+1] = nums[j]
j = j - 1

nums[j+1] = key

其他插入排序

交换排序

交换排序也是一种非常基础的算法,主要包含冒泡排序和快速排序。

冒泡排序(Bubble Sort)

1
2
3
4
5
def bubble_sort(nums):
for i in range(0, len(nums)-1):
for j in range(0, len(nums)-1-i):
if nums[j] > nums[j+1]:
nums[j], nums[j+1] = nums[j+1], nums[j]

快速排序(Quick Sort)

快速排序,又称分区交换排序,简称快排,是对冒泡排序的一种改进。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def quick_sort(nums, low, high):
if low >= high: return

pivot = nums[low] # 选数列第一个元素作为"基准"
i, j = low, high
while i < j:
while i < j and nums[j] >= pivot:
j = j - 1
nums[i] = nums[j]

while i < j and nums[i] <= pivot:
i = i + 1
nums[j] = nums[i]
nums[i] = pivot

quick_sort(nums, low, i-1)
quick_sort(nums, i+1, high)

选择排序

堆排序(Heap Sort)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def heap_sort(nums):
# 堆调整
def max_heapify(nums, i, length):
parent = i
child = 2 * i + 1
if child >= length:
return
if child + 1 < length and nums[child] < nums[child+1]:
child += 1
if nums[parent] < nums[child]:
nums[parent], nums[child] = nums[child], nums[parent]
max_heapify(nums, child, length)

# 初始化,构造大顶堆
for i in range(len(nums) // 2 - 1, -1, -1):
max_heapify(nums, i, len(nums))

# 堆排序
for j in range(len(nums) - 1, 0, -1):
nums[0], nums[j] = nums[j], nums[0]
max_heapify(nums, 0, j)

归并排序(Merge Sort)

快速排序虽然排序效率高,但是不稳定,时间复杂度介于O(nlogn)跟O(n2)之间。
而归并排序可以稳定在O(nlogn)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def mergeSort(nums):
if len(nums) == 1:
return nums

mid = len(nums) // 2
left = mergeSort(nums[:mid])
right = mergeSort(nums[mid:])
result = []
while left and right:
if left[0] <= right[0]:
result.append(left.pop(0))
else:
result.append(right.pop(0))
if left:
result += left
if right:
result += right
return result

参考

  1. 《数据结构(C语言版)》——严蔚敏、吴伟民
  2. https://zh.wikipedia.org/wiki/快速排序
  3. https://blog.csdn.net/wthfeng/article/details/78037228

使用shell批量更改文件名

问题由来
由于5D3默认使用的文件名前缀是【5P7A】,在拍了一大堆照片后才注意到这个前缀。后来在相机中重新设置文件名前缀为【IMG_】,但是已经拍摄的照片文件名前缀没法在相机中更改。所以只能在电脑中通过程序批量更改这些文件名。于是想到了shell。

屏幕截图

解决办法

1
for i in `ls -a|grep 5P7A`;do mv $i ${i/5P7A/IMG_};done

一行代码搞定。

Scala 中几种常用集合操作符

Scala 中的几种常用的集合操作符

  • ::
  • :+/+:
  • ++
  • :::

几种操作符的说明以及用法

一、::
两个冒号,表示往一个集合的头部添加元素,构造一个新的集合。x::list 表示往 list 队列的头部添加元素 x

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//创建一个List
scala> val list = List(1,2)
list: List[Int] = List(1, 2)

//创建不变量x
scala> val x = 3
x: Int = 3

//将x插入到list头部
scala> x::list
res16: List[Int] = List(3, 1, 2)

// :: 的另一种使用形式
scala> list.::(x)
res17: List[Int] = List(3, 1, 2)

二、:+ 和 +:
冒号和加和组合的操作符,冒号在左边和冒号在右边的区别是分别是:1. list:+x 在集合尾部添加元素;2. x+:list在集合头部添加元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//将x插入到list尾部
scala> list:+x
res18: List[Int] = List(1, 2, 3)

//将x插入到list头部
scala> x+:list
res19: List[Int] = List(3, 1, 2)

//也可以这样使用
scala> list.+:(x)
res20: List[Int] = List(3, 1, 2)

scala> list.:+(x)
res21: List[Int] = List(1, 2, 3)

//创建一个 Seq 类型集合
scala> val seq = Seq(1, 2, 3)
seq: Seq[Int] = List(1, 2, 3)

//seq调用 :+
scala> seq.:+(5)
res29: Seq[Int] = List(1, 2, 3, 5)

其中 +: 和 :: 类似,但是 :: 可以用于 pattern match,而 +: 不支持。

三、++
两个加号,表示连接两个集合。例如,list++list1

1
2
3
4
5
6
7
8
9
10
scala> list1
res25: List[Int] = List(3, 4)

//list 加上 list1 中的元素
scala> list++list1
res26: List[Int] = List(1, 2, 3, 4)

//list1 加上 list 中的元素
scala> list1++list
res27: List[Int] = List(3, 4, 1, 2)

四、:::
三个冒号,表示连接两个 List 类型的集合。

1
2
3
4
5
6
7
8
9
10
11
12
13
//创建seq1
scala> val seq1 = Seq(4, 5)
seq1: Seq[Int] = List(4, 5)

//seq调用 ::: 去连接seq1,报错
scala> seq:::seq1
<console>:10: error: value ::: is not a member of Seq[Int]
seq:::seq1
^

//::: 只能用于连接两个 List 类型的集合
scala> list:::list1
res31: List[Int] = List(1, 2, 3, 4)

开始使用OpenSUSE

【前言】
之前一直在用Ubuntu和CentOS,最近看到github上有位大神强烈推荐OpenSUSE这个系统。于是,顺着一直想找个新的Linux发行版玩玩的想法,搭上了openSUSE的这般顺风车。

【开始】
上openSUSE的官网下载了最新的版本,openSUSE leap 42.1。这里我并不了解这个版本号的意义,也不清楚openSUSE的上一个版本是多少。直接下载了最新的稳定版42.1,开始了openSUSE的征程!

Mac 下安装 MySQLdb

环境
系统版本: Mac OS X EI Caption (version 10.11.1)
Python 版本: 2.7.10
virtualenv (14.0.6)

问题
安装 MySQLdb 出现 mysql_config not found
解决以上问题后,又出现 Reason: image not found
通过以下命令可以解决该问题
sudo ln -s /usr/local/mysql/lib/libmysqlclient.18.dylib /usr/lib/libmysqlclient.18.dylib
但是,执行这条命令后又会出现 ln: /usr/lib/libmysqlclient.18.dylib: Operation not permitted
这个问题。

最后,找到 stackoverflow 上给出的解决方案。
执行一下命令,即可解决问题。
/usr/local/mysql/lib/libmysqlclient.18.dylib /usr/local/lib/libmysqlclient.18.dylib

参考文章:
http://blog.csdn.net/janronehoo/article/details/25207825
http://stackoverflow.com/questions/10557507/rails-mysql-on-osx-library-not-loaded-libmysqlclient-18-dylib

如何在MySQL中实现row_number函数

很久之前给自己挖的坑,现在来把它补完。
MySQL的统计函数比较稀缺,很多经典的统计函数如row_number这样的函数在MySQL是没有的,不确定最新版本会不会增加。
为了实现这个功能,需要在查询中启用临时变量。
比如对这张Employee表加上行号:
| Id | Salary |
| :– | :—– |
| 1 | 100 |
| 2 | 200 |
| 3 | 300 |
代码如下:

1
2
3
4
5
6
7
SET @row_number = 0;

SELECT
(@row_number:[email protected]_number + 1) AS num, id, salary
FROM
employee
LIMIT 10;

也可以这样写:

1
2
3
4
5
SELECT 
(@row_number:[email protected]_number + 1) AS num, id, salary
FROM
employee,(SELECT @row_number:=0) AS t
LIMIT 10;

参考文章:
https://segmentfault.com/a/1190000004566152

在 Linux 上挂载硬盘

1.先执行如下命令 df -h 查看当前系统磁盘信息。

1
2
3
4
5
6
7
8
9
10
[email protected]:/opt/hadoop-2.6.2/etc/hadoop# df -h
Filesystem Size Used Avail Use% Mounted on
/dev/vda1 25G 4.4G 19G 19% /
none 4.0K 0 4.0K 0% /sys/fs/cgroup
udev 7.9G 12K 7.9G 1% /dev
tmpfs 1.6G 408K 1.6G 1% /run
none 5.0M 0 5.0M 0% /run/lock
none 7.9G 0 7.9G 0% /run/shm
none 100M 0 100M 0% /run/user
/dev/vdc1 50G 52M 47G 1% /data

2.执行 fdisk -l 查看系统中是否存在未挂载磁盘。

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
[email protected]:/opt/hadoop-2.6.2/etc/hadoop# fdisk -l

Disk /dev/vda: 26.8 GB, 26843545600 bytes
255 heads, 63 sectors/track, 3263 cylinders, total 52428800 sectors
Units = sectors of 1 * 512 = 512 bytes
Sector size (logical/physical): 512 bytes / 512 bytes
I/O size (minimum/optimal): 512 bytes / 512 bytes
Disk identifier: 0x0008d3a3

Device Boot Start End Blocks Id System
/dev/vda1 * 2048 52426751 26212352 83 Linux

Disk /dev/vdb: 17.2 GB, 17179869184 bytes
255 heads, 63 sectors/track, 2088 cylinders, total 33554432 sectors
Units = sectors of 1 * 512 = 512 bytes
Sector size (logical/physical): 512 bytes / 512 bytes
I/O size (minimum/optimal): 512 bytes / 512 bytes
Disk identifier: 0x000d5b4e

Device Boot Start End Blocks Id System
/dev/vdb1 63 33543719 16771828+ 82 Linux swap / Solaris

Disk /dev/vdc: 53.7 GB, 53687091200 bytes
255 heads, 63 sectors/track, 6527 cylinders, total 104857600 sectors
Units = sectors of 1 * 512 = 512 bytes
Sector size (logical/physical): 512 bytes / 512 bytes
I/O size (minimum/optimal): 512 bytes / 512 bytes
Disk identifier: 0x000e4ad7

Device Boot Start End Blocks Id System
/dev/vdc1 63 104856254 52428096 83 Linux

Disk /dev/vdd: 2147.5 GB, 2147483648000 bytes
14 heads, 61 sectors/track, 4911362 cylinders, total 4194304000 sectors
Units = sectors of 1 * 512 = 512 bytes
Sector size (logical/physical): 512 bytes / 512 bytes
I/O size (minimum/optimal): 512 bytes / 512 bytes
Disk identifier: 0xd15b19e1

Device Boot Start End Blocks Id System
/dev/vdd1 2048 4194303999 2097150976 83 Linux

Disk /dev/vde: 2147.5 GB, 2147483648000 bytes
14 heads, 61 sectors/track, 4911362 cylinders, total 4194304000 sectors
Units = sectors of 1 * 512 = 512 bytes
Sector size (logical/physical): 512 bytes / 512 bytes
I/O size (minimum/optimal): 512 bytes / 512 bytes
Disk identifier: 0xef776a1b

Device Boot Start End Blocks Id System
/dev/vde1 2048 4194303999 2097150976 83 Linux

3.对磁盘分区。
执行 fdisk /dev/vdd1 命令,对磁盘进行分区。
依次输入,n,p,1,两次回车,再输入 wq 分区自动进行,并且很快完成。

4.查看分区 fdisk -l 可以看到,分区已经新建。

5.格式化新分区,输入 mkfs.ext3 /dev/xvdb1 进行格式化分区。

6.添加分区信息
使用“echo ‘/dev/xvdb1 /mnt ext3 defaults 0 0’ >> /etc/fstab”(不含引号)命令写入新分区信息。
然后使用“cat /etc/fstab”命令查看,出现以下信息就表示写入成功。

注:ubuntu12.04不支持barrier,所以正确写法是:echo ‘/dev/xvdb1 /mnt ext3 barrier=0 0 0’ >> /etc/fstab

  • 如果需要把数据盘单独挂载到某个文件夹,比如单独用来存放网页,可以修改以上命令中的/mnt部分

7.挂载分区
使用“mount -a”命令挂载新分区,然后用“df -h”命令查看,出现以下信息就说明挂载成功,可以开始使用新的分区了。

参考文章:
http://help.aliyun.com/knowledge_detail/5974154.html

在 Mac 上配置 Hadoop-2.6.2 和 Hive-1.2.1 遇到问题

问题描述:
在 Mac 上安装配置完 Hadoop-2.6.2 后,再安装 Hive-1.2.1 并启动,出现以下错误信息。

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
gjl: ~/bin/apache-hive-1.2.1-bin $bin/hive

Logging initialized using configuration in jar:file:/Users/gaojunliang/bin/apache-hive-1.2.1-bin/lib/hive-common-1.2.1.jar!/hive-log4j.properties
[ERROR] Terminal initialization failed; falling back to unsupported
java.lang.IncompatibleClassChangeError: Found class jline.Terminal, but interface was expected
at jline.TerminalFactory.create(TerminalFactory.java:101)
at jline.TerminalFactory.get(TerminalFactory.java:158)
at jline.console.ConsoleReader.<init>(ConsoleReader.java:229)
at jline.console.ConsoleReader.<init>(ConsoleReader.java:221)
at jline.console.ConsoleReader.<init>(ConsoleReader.java:209)
at org.apache.hadoop.hive.cli.CliDriver.setupConsoleReader(CliDriver.java:787)
at org.apache.hadoop.hive.cli.CliDriver.executeDriver(CliDriver.java:721)
at org.apache.hadoop.hive.cli.CliDriver.run(CliDriver.java:681)
at org.apache.hadoop.hive.cli.CliDriver.main(CliDriver.java:621)
at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:57)
at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
at java.lang.reflect.Method.invoke(Method.java:606)
at org.apache.hadoop.util.RunJar.run(RunJar.java:221)
at org.apache.hadoop.util.RunJar.main(RunJar.java:136)

Exception in thread "main" java.lang.IncompatibleClassChangeError: Found class jline.Terminal, but interface was expected
at jline.console.ConsoleReader.<init>(ConsoleReader.java:230)
at jline.console.ConsoleReader.<init>(ConsoleReader.java:221)
at jline.console.ConsoleReader.<init>(ConsoleReader.java:209)
at org.apache.hadoop.hive.cli.CliDriver.setupConsoleReader(CliDriver.java:787)
at org.apache.hadoop.hive.cli.CliDriver.executeDriver(CliDriver.java:721)
at org.apache.hadoop.hive.cli.CliDriver.run(CliDriver.java:681)
at org.apache.hadoop.hive.cli.CliDriver.main(CliDriver.java:621)
at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:57)
at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
at java.lang.reflect.Method.invoke(Method.java:606)
at org.apache.hadoop.util.RunJar.run(RunJar.java:221)
at org.apache.hadoop.util.RunJar.main(RunJar.java:136)

解决办法:
将 Hive 中的 jline 从 2.x 版本降级到 1.x 之后,将 Hadoop 中 share/hadoop/yarn/lib 目录下的 jline 升级到 2.x 版本。

Mac OS X 10.11 上安装 MySQLdb 出现问题

问题描述:
更新Mac OS X 10.11后安装MySQLdb,进入ipython交互命令后,输入import MySQLdb

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
In [1]: import MySQLdb
---------------------------------------------------------------------------
ImportError Traceback (most recent call last)
<ipython-input-1-dd22983d5391> in <module>()
----> 1 import MySQLdb

/Library/Python/2.7/site-packages/MySQL_python-1.2.4b4-py2.7-macosx-10.10-intel.egg/MySQLdb/__init__.py in <module>()
17 from MySQLdb.release import __version__, version_info, __author__
18
---> 19 import _mysql
20
21 if version_info != _mysql.version_info:

ImportError: dlopen(/Library/Python/2.7/site-packages/MySQL_python-1.2.4b4-py2.7-macosx-10.10-intel.egg/_mysql.so, 2): Library not loaded: libmysqlclient.18.dylib
Referenced from: /Library/Python/2.7/site-packages/MySQL_python-1.2.4b4-py2.7-macosx-10.10-intel.egg/_mysql.so
Reason: image not found

问题原因:
由于EI Capitan 增加了System Integrity Protection 的功能,阻止了写入的操作的,默认是开启的,需要关闭。

解决办法:
重启电脑,开机时按住 cmd + R,进入 Recovery 模式。然后打开终端工具 ,输入命令:csrutil disable,然后再次重启电脑。
重启后,打开terminal输入以下命令:

1
sudo ln -s /usr/local/mysql/lib/libmysqlclient.18.dylib /usr/lib/libmysqlclient.18.dylib

如果不关闭写入操作,将会出现以下情况:

1
ln: /usr/lib/libmysqlclient.18.dylib: Operation not permitted

引用:
http://segmentfault.com/q/1010000003026543