插入排序
(defun insertion-sort (arr symbol)
"
arr is of type LIST
symbol must be `>` or `<`
執(zhí)行時(shí)間 執(zhí)行次數(shù)
for j = 1 until arr.length c1 n
key = arr[j] c2 n - 1
i = j - 1 c4 n - 1
n
while i >= 0 and arr[i] > key c5 Σ Tj
j=1
n
arr[i + 1] = a[i] c6 Σ (Tj - 1)
j=1
n
i = i - 1 c7 Σ (Tj - 1)
j=1
a[i + 1] = key c8 n - 1
"
(let ((len (length arr)))
(do ((j 1 (1+ j)))
((>= j len) arr)
(let ((key (nth j arr)))
(do ((i (- j 1) (1- i)))
((not (and (>= i 0) (funcall symbol (nth i arr) key))) (setf (nth (+ i 1) arr) key))
(setf (nth (+ i 1) arr) (nth i arr)))))))
/**
* insert sort
*
* @param arr
* @return sorted array
*/
def `insert-sort` (arr: Array[Int]): Array[Int] = {
for (i <- 0 until arr.length) {
var j = i
val k = arr(j)
while (j > 0 && arr(j) > arr(j - 1)) {
arr(j) = arr(j - 1)
arr(j - 1) = k
j = j - 1
}
}
arr
}
歸并排序
; 分治法思想：
; 將原問(wèn)題分解為幾個(gè)規(guī)模較小但類似于原問(wèn)題的子問(wèn)題
; 遞歸求解這些子問(wèn)題
; 最后合并這些子問(wèn)題的解來(lái)簡(jiǎn)歷原問(wèn)題的解
; 并歸排序算法完全遵守分治模式缀皱，即
; 分解：分解待排序的n個(gè)元素的序列成各具n/2個(gè)元素的兩個(gè)子序列
; 解決：使用并歸排序遞歸地排序兩個(gè)子序列
; 合并：合并兩個(gè)已排序的子序列以產(chǎn)生已排序的答案
; 而它的關(guān)鍵操作就是“合并”：兩個(gè)'已排序'序列的合并
; 下面她倘，可以定義一個(gè)輔助函數(shù)merge(arr, l, m , r)來(lái)完成合并
(defun ~merge (arr l m r)
"
`包CL已經(jīng)含有merge名稱的函數(shù) 此處需要換一個(gè)名稱`
arr(ay) - 數(shù)組
l - left 下標(biāo)
m - mid 下標(biāo)
r - right 下標(biāo)
MERGE(array, l, m, r)
n1 = m - l + 1
n2 = r - m
let al[n1] and ar[n2] be new arrays
for i = 0 until n1
al[i] = array[l + i]
for j = 0 until n2
ar[j] = array[m + j + 1]
i = 0, j = 0
for k = l to r
case i < n1 and j < n2
if al[i] <= ar[j]
array[k] = al[i]
i = i + 1
else
array[k] = ar[j]
j = j + 1
case i < n1
array[k] = al[i]
i = i + 1
case j < n2
array[k] = ar[j]
j = j + 1
"
(let* ((n1 (+ 1 (- m l)))
(n2 (- r m))
(n3 (+ n1 n2))
(al (make-array `(,n1) :initial-element nil))
(ar (make-array `(,n2) :initial-element nil)))
(dotimes (i n1)
(setf (svref al i) (aref arr (+ i l))))
(dotimes (j n2)
(setf (svref ar j) (aref arr (+ j m 1))))
(let ((i 0)
(j 0))
(do ((k l (1+ k)))
((>= k (+ n3 l)) arr)
(cond ((and (< i n1) (< j n2))
(if (<= (aref al i) (aref ar j))
(progn
(setf (aref arr k) (aref al i))
(setf i (+ i 1)))
(progn
(setf (aref arr k) (aref ar j))
(setf j (+ j 1)))))
((< i n1)
(progn
(setf (aref arr k) (aref al i))
(setf i (+ i 1))))
((< j n2)
(progn
(setf (aref arr k) (aref ar j))
(setf j (+ j 1)))))))))
; 在~merge函數(shù)中桨仿，3個(gè)for循環(huán)運(yùn)行時(shí)間都跟數(shù)組長(zhǎng)度相關(guān)
; 其余步驟可用常量c代替
; 所以次函數(shù)時(shí)間復(fù)雜度可以簡(jiǎn)化成
; c1 * n1 + c2 * n2 + c3 * n3 + c ==> 線性階 ==> O(n)
(defun merge-sort (arr l r)
"
歸并排序數(shù)組A[l ... r]
如果l >= r髓涯，則表示子數(shù)組最多只有一個(gè)元素，可以當(dāng)作已排列數(shù)組序列
MERGE-SORT(arr, l, r)
if l < r
m = |(l + r) / 2|
MERGE-SORT(arr, l, m)
MERGE-SORT(arr, (m + 1), r)
MERGE(arr, l, m, r)
"
(if (< l r)
(let ((m (floor (+ l r) 2)))
(merge-sort arr l m)
(merge-sort arr (+ m 1) r)
(~merge arr l m r))))
/**
* 數(shù)組arr以下標(biāo)m為分界點(diǎn),[1 - m](m - r]杏愤，必須有序一致
* @param arr
* @param l
* @param m
* @param r
* @return sorted array
*/
def merge (arr: Array[Int], l: Int, m: Int, r: Int): Array[Int] = {
val n1 = m - l + 1
val n2 = r - m
val left = new Array[Int](n1)
val right = new Array[Int](n2)
for (i <- 0 until n1)
left(i) = arr(l + i)
for (j <- 0 until n2)
right(j) = arr(m + 1 + j)
var i = 0
var j = 0
var end = 0
for (k <- l to r) {
end match {
case 1 => {
arr(k) = right(j)
j = j + 1
}
case 2 => {
arr(k) = left(i)
i = i + 1
}
case _ => {
if (i > n1 - 1) {
arr(k) = right(j)
j = j + 1
end = 1
} else if (j > n2 - 1) {
arr(k) = left(i)
i = i + 1
end = 2
} else if (left(i) < right(j)) {
arr(k) = left(i)
i = i + 1
} else {
arr(k) = right(j)
j = j + 1
}
}
}
}
arr
}
def `merge-sort` (arr: Array[Int], l: Int, r: Int): Array[Int] = {
if (l < r) {
val m: Int = math.floor((l + r) / 2).toInt
`merge-sort`(arr, l, m)
`merge-sort`(arr, m + 1, r)
merge(arr, l, m, r)
}
arr
}
堆排序
;;;; 6 堆排序
;;;; 6.1 堆
; 如果輸入數(shù)組中僅有常數(shù)個(gè)元素需要在排序過(guò)程中存儲(chǔ)在數(shù)組外
; 則稱排序算法是原址的(in place)
; 插入排序是一種原址排序
; 而歸并排序中扬卷， merge過(guò)程并不是原址的
; 堆排序是原址的颤介，時(shí)間復(fù)雜度為O(nlgn)期贫，它具有插入排序和歸并排序的優(yōu)點(diǎn)
(defun parent (i)
"根據(jù)節(jié)點(diǎn)下標(biāo)求父節(jié)點(diǎn) i [0 ...]
"
(if (= i 0)
0
(floor (/ (- i 1) 2))))
(defun left (i)
"i [0 ...]"
(+ (* 2 i) 1))
(defun right (i)
"i [0 ...]"
(* 2 (+ i 1)))
; 二叉堆的兩種形勢(shì)：
; 最大堆：除了根以外的所有節(jié)點(diǎn)i都滿足 A[parent(i)] >= A[i]
; 最小堆：除了根以外的所有節(jié)點(diǎn)i都滿足 A[parent(i)] <= A[i]
; 堆排序算法中跟匆，一般使用最大堆，最小堆通常用于有限隊(duì)列
; 如果把堆看成一棵樹(shù)通砍，如果包含n個(gè)元素的堆可以看成一棵完全二叉樹(shù)
; 那么該堆的高度就是lgn玛臂，堆結(jié)構(gòu)上的一些基本操作的運(yùn)行時(shí)間至多與樹(shù)的高度成正比
; 即時(shí)間復(fù)雜度為O(lgn)
;;;; 6.2 維護(hù)堆的性質(zhì)
(defun max-heapify (arr i &optional (root-index 0))
"
用于維護(hù)最大堆性質(zhì)的重要過(guò)程
arr - 數(shù)組
i - 下標(biāo)(相對(duì)數(shù)組, 以起始下標(biāo)為準(zhǔn)的新數(shù)組)
root-index - 起始下標(biāo)(整個(gè)數(shù)組)
輸入數(shù)組arr和下標(biāo)i
調(diào)用該函數(shù)時(shí)烤蜕，假設(shè)父節(jié)點(diǎn)left(i)和right(i)的二叉樹(shù)都是最大堆
但A[i]可能小于其孩子，這就違背了最大堆的性質(zhì)
MAX-HEAPIFY通過(guò)讓A[i]的值在最大堆中逐漸降級(jí)
從而使得以下標(biāo)i為根節(jié)點(diǎn)的子樹(shù)重新遵守最大堆的性質(zhì)
MAX-HEAPIFY (A, i, root-index)
l = left(i) + root-index
r = right(i) + root-index
heap-size = A.heap-size - root-index
new-i = i + root-index
if l - root-index < heap-size and A[l] > A[new-i]
largest = l
else
largest = new-i
if r - root-index < heap-size and A[r] > A[largest]
largest = r
if largest != new-i
exchange A[new-i] with A[largest]
MAX-HEAPIFY (A, largest, root-index)
對(duì)于一個(gè)以i為根節(jié)點(diǎn)迹冤，大小為n的子樹(shù)讽营，MAX-HEAPIFY的時(shí)間代價(jià)包括：
調(diào)整A[i]/A[left(i)]/A[right(i)]的關(guān)系的時(shí)間代價(jià)O(1)
在加上一棵以i的一個(gè)孩子節(jié)點(diǎn)為根節(jié)點(diǎn)的子樹(shù)運(yùn)行MAX-HEAPIFY的時(shí)間代價(jià)(假設(shè)遞歸調(diào)用會(huì)發(fā)生)
因?yàn)槊總€(gè)孩子子樹(shù)的大小至多為2n/3(最壞情況發(fā)生在樹(shù)的最底層恰好半滿的時(shí)候)
T(n) <= T(2n/3) + O(1) ==> T(n) = O(lgn)
"
(let ((heap-size (- (length arr) root-index))
(l (+ (left i) root-index))
(r (+ (right i) root-index))
(new-i (+ i root-index))
(largest (+ i root-index))
(dummy nil))
(if (and (< (- l root-index) heap-size) (> (aref arr l) (aref arr new-i)))
(setf largest l))
(if (and (< (- r root-index) heap-size) (> (aref arr r) (aref arr largest)))
(setf largest r))
(if (/= largest new-i)
(progn
(setf dummy (aref arr new-i))
(setf (aref arr new-i) (aref arr largest))
(setf (aref arr largest) dummy)
(max-heapify arr largest root-index))
arr)))
#+test
(let ((arr (vector 16 4 10 14 7 9 3 2 8 1)))
; arr result vector(16 14 10 8 7 9 3 2 4 1)
(max-heapify arr 1))
#+test
(let ((arr (vector 16 4 10 14 7 9 3 2 8 1)))
; arr result vector(16 4 10 14 7 9 3 8 2 1)
(max-heapify arr 0 7))
;;;; 6.3 建堆
(defun build-max-heap (arr root-index)
;i為相對(duì)數(shù)組里的下標(biāo)，取值范圍[0 ... ]
(do ((i (- (length arr) 1) (1- i)))
((< i 0) arr)
(max-heapify arr i root-index)))
#+test
(let ((arr (vector 4 1 3 2 16 9 10 14 8 7)))
; result: (vector 16 14 10 8 7 9 3 2 4 1)
(build-max-heap arr))
#+test
(let ((arr (vector 4 1 3 2 16 9 10 14 8 7)))
; result: (vector 4 1 3 2 16 9 14 10 8 7)
(build-max-heap arr 5))
; 每次調(diào)用 max-heapify的時(shí)間復(fù)雜度是lgn
; build-max-heap需要O(n)次這樣的調(diào)用
; 因此總的時(shí)間復(fù)雜度就是O(nlgn)
; 這個(gè)上界雖然正確 但不是漸進(jìn)緊確的
; 但是根據(jù)如下性質(zhì)可以得到一個(gè)更緊確的界：
; 包含n個(gè)元素的堆的高度為floor(lgn)泡徙，高度為h的堆最多包含celing(n/2^(h+1))個(gè)節(jié)點(diǎn)
; 最終可以推導(dǎo)出 build-max-heap為O(n)
; 目前不太清楚 build-max-heap => O(n) --!
;;;; 6.4 堆排序算法
(defun heap-sort (arr)
"
build-max-heap初始化整體數(shù)組為最大堆
在相對(duì)數(shù)組里橱鹏，首元素為最大，每次維護(hù)首元素下標(biāo)后的元素的最大堆性質(zhì)
HEAP-SORT(A)
BUILD-MAX-HEAP(A, 0)
for i = 0 until A.length
MAX-HEAPIFY(A, 0, i)
"
;(do ((i 0 (1+ i)))
; ((>= i (length arr)) arr)
; (build-max-heap arr i)) ; 時(shí)間復(fù)雜度 O(n^2)堪藐，棄用
(build-max-heap arr 0) ;O(n) or O(nlgn)蚀瘸，但最終對(duì)heap-sort的時(shí)間復(fù)雜度無(wú)影響
(do ((i 1 (1+ i)))
((>= i (length arr)) arr)
(max-heapify arr 0 i)) ;O(nlgn)
)
/*
* 用數(shù)組存儲(chǔ)二叉堆，用下標(biāo)計(jì)算表示出對(duì)應(yīng)的父結(jié)點(diǎn)庶橱，左孩子，右孩子
*/
def parent(i: Int): Int = {
i match {
case i: Int if i <= 0 => 0
case _ => math.floor((i - 1) / 2).toInt
}
}
def left(i: Int): Int = (i * 2) + 1
def right(i: Int): Int = (i + 1) * 2
def exchange (arr: Array[Int], i: Int, j: Int) {
val tmp = arr(i)
arr(i) = arr(j)
arr(j) = tmp
}
/**
* 最大堆
* @param arr 數(shù)組
* @param i 相對(duì)下標(biāo)贪惹，以根下標(biāo)為準(zhǔn)的新數(shù)組
* @param root 根下標(biāo)
* @return
*/
def `max-heapify` (arr: Array[Int], i: Int, root: Int = 0): Array[Int] = {
val l = left(i) + root
val r = right(i) + root
val heapsize = arr.length - root
val index = i + root
var largest = index
if (l - root < heapsize && arr(l) > arr(largest))
largest = l
if (r - root < heapsize && arr(r) > arr(largest))
largest = r
if (largest != index) {
exchange(arr, index, largest)
`max-heapify`(arr, largest, root)
}
arr
}
def `build-max-heap` (arr: Array[Int], root: Int = 0): Array[Int] = {
for (i <- arr.length - 1 to 0 by -1) {
`max-heapify`(arr, i)
}
arr
}
def `heap-sort` (arr: Array[Int]): Array[Int] = {
`build-max-heap`(arr)
for (i <- 0 to arr.length - 1) {
`max-heapify`(arr, 0, i)
}
arr
}
快速排序
;;;; 快速排序
; 快速排序的最壞時(shí)間復(fù)雜度為O(n^2)苏章，雖然最壞時(shí)間復(fù)雜度很差
; 但在實(shí)際排序應(yīng)用中是最好的選擇
; 它的期望復(fù)雜度是nlgn，而且也是原址排序
;;;; 7.1 快速排序描述
; 與歸并排序一樣奏瞬，它采用了分治思想枫绅，下面是快速排序?qū)?shù)組A[l ... r]三步分治過(guò)程：
; 分解：數(shù)組A[l...r]被劃分成為兩個(gè)(可能為空)子數(shù)組A[l...m-1]和A[m+1...r]
; 使得A[l...m-1]中的任一元素都小于等于A[m]，而A[m]也小于等于A[m+1...r]中的任一元素
; 其中硼端，計(jì)算下標(biāo)m也是劃分的一部分
; 解決：通過(guò)遞歸調(diào)用快速排序并淋，對(duì)子數(shù)組A[l...m-1]和A[m+1...r]進(jìn)行排序
; 合并：因?yàn)樽訑?shù)組都是原址排序的，所以不需要合并操作：數(shù)組A[l...r]已經(jīng)有序
(defun quick-sort (arr l r)
"
QUICK-SORT(A, l, r)
if l < r
m = PARTITION(A, l, r)
QUICK-SORT(A, l, m - 1)
QUICK-SORT(A, m + 1, r)
"
(let ((m nil))
(if (< l r)
(progn
(setf m (partition arr l r))
(quick-sort arr l (- m 1))
(quick-sort arr (+ m 1) r)))
arr))
(defun partition (arr l r)
"
PARTITION(A, L, R)
k = A[R]
i = L
for j = L to R - 1
if A[j] <= x
exchange A[i] with A[j]
i = i + 1
exchange A[i] with A[R]
return i
大致思路就是這樣珍昨，數(shù)組A[L...I...J...R]
區(qū)間[L...I]存放比key小或者等于的元素
區(qū)間[I...J]存放比key大的元素
區(qū)間[J...R]是未比較元素
當(dāng)J接近到R時(shí)县耽，由于最終有一步是i = i + 1
所以下標(biāo)i此時(shí)的元素是大于key值的，交換他們之后
數(shù)組就變成這樣的情況：
以下標(biāo)i為界镣典，前面部分都是比它小或者等的兔毙，后面部分都是大于它的
"
(let ((k (aref arr r))
(i l)
(dummy nil))
(do ((j l (1+ j)))
((>= j r))
(if (< (aref arr j) k)
(progn
(setf dummy (aref arr i))
(setf (aref arr i) (aref arr j))
(setf (aref arr j) dummy)
(setf i (+ i 1)))))
(setf dummy (aref arr i))
(setf (aref arr i) (aref arr r))
(setf (aref arr r) dummy)
(values i arr)))
;;;; 7.3 快速排序隨機(jī)化版本
; 前面的快速排序中，輸入數(shù)據(jù)的所有排列都是等概率的兄春，但在實(shí)際工作中
; 這種情況不會(huì)總成立澎剥，所以在算法中引入隨機(jī)化性，使得所有輸入輸入都能獲得較好的期望性能
; 下面是隨機(jī)版本的快速排序的偽代碼實(shí)現(xiàn)：
; RANDOMIZED-PARTITION(A, p, r)
; i = RANDOM(p, r)
; exchange A[r] with A[i]
; return PARTION(A, p, r)
;
; RANDOMIZED-QUICKSORT(A, p, r)
; if p < r
; q = RANDOMIZED-PARTITION(A, p, r)
; RANDOMIZED-QUICKSORT(A, p, q - 1)
; RANDOMIZED-QUICKSORT(A, q + 1, r)
def partition (arr: Array[Int], left: Int, right: Int): Int = {
val k = arr(right)
var i = left
for (j <- left to right - 1) {
if (arr(j) <= k) {
/*exchange arr(i) and arr(j)*/
val tmp = arr(i)
arr(i) = arr(j)
arr(j) = tmp
i = i + 1
}
}
arr(right) = arr(i)
arr(i) = k
i
}
def `quick-sort`(arr: Array[Int], left: Int, right: Int): Array[Int] = {
if (left < right) {
val mid = partition(arr, left, right)
`quick-sort`(arr, left, mid - 1)
`quick-sort`(arr, mid + 1, right)
}
arr
}
計(jì)數(shù)排序
; 在排序的最終結(jié)果中赶舆，各元素之間的次序依賴于它們的比較關(guān)系哑姚，這樣的排序算法稱為`比較排序`
; 在之前筆記中涉及到的算法，包括`插入芜茵，歸并叙量，快速，堆`排序夕晓，都屬于比較排序
; 計(jì)數(shù)排序運(yùn)用的是運(yùn)算而不是比較來(lái)確定排序順序的
;;;; 8.2 計(jì)數(shù)排序
; 計(jì)數(shù)排序基本思想：對(duì)于每一個(gè)輸入元素宛乃，確定小于x的元素的個(gè)數(shù)
; 利用這一信息，可以直接把元素放在數(shù)組對(duì)應(yīng)的下標(biāo)中
(defun counting-sort (arr)
"
COUNTING-SORT(A, B, k)
//數(shù)組B存放排序的輸出
let C[0...k] be a new array //提供臨時(shí)存儲(chǔ)空間
for i = 0 until k
C[i] = 0 //初始化C的元素
for j = 0 until A.length
C[A[j]] = C[A[j]] + 1 //C[i]代表A[n]元素個(gè)數(shù)(A[n] == i，i = 0, 1 ... k)
for i = 0 until k
C[i+1] = C[i+1] + C[i] //對(duì)每一個(gè)i=0,1...k征炼，統(tǒng)計(jì)多少輸入元素是小于或等于i的
for j = A.length - 1 downto 0
B[C[A[j]] - 1] = A[j]
C[A[j]] = C[A[j]] - 1 //把每個(gè)元素A[j]放到它在輸出數(shù)值B中的正確位置
//如果所有元素互異析既，對(duì)于每一個(gè)A[j]值來(lái)說(shuō)
//C[A[j]]就是A[j]在輸出數(shù)值中的最終正確位置
//這是因?yàn)橛蠧[A[j]]個(gè)元素小于或等于A[j]
//但有可能所有元素不是互異的
//所以將每一個(gè)值A(chǔ)[j]放入B中后，都要將C[A[j]]值減一
//這樣谆奥，如果遇到下一個(gè)值等于A[j]的元素時(shí)
//可以直接放在輸出數(shù)組B中A[j]的前一個(gè)位置
計(jì)數(shù)排序的一個(gè)重要性質(zhì)是它是穩(wěn)定的：具有相同值的元素在輸出數(shù)組中的相對(duì)次序與它們?cè)谳斎霐?shù)組中的相對(duì)次序相同
代碼實(shí)現(xiàn)上用到了比較性質(zhì)眼坏，用于確定k值
而且由于編程語(yǔ)言的特性
加上對(duì)偏移的計(jì)算
實(shí)現(xiàn)上跟偽代碼略微不同
顯然，每重循環(huán)都是線性時(shí)間酸些，最終時(shí)間復(fù)雜度表示為O(n)
但不是原址排序宰译，空間換時(shí)間
如果計(jì)算出來(lái)的k值過(guò)大，也就是說(shuō)存在過(guò)大的輸入元素魄懂，就需要對(duì)空間和時(shí)間進(jìn)行考慮了
"
(labels ((maximum (arr max i)
(if (< i 0)
max
(maximum arr
(if (or (null max) (> (aref arr i) max))
(aref arr i)
max)
(1- i))))
(minimum (arr min i)
(if (< i 0)
min
(minimum arr
(if (or (null min) (< (aref arr i) min))
(aref arr i)
min)
(1- i))))
(fn-offset (num)
(if (< num 0)
(abs num)
(- 0 num))))
(let* ((len (length arr))
(offset (fn-offset (minimum arr nil (1- len))))
(k (+ 1 (+ (maximum arr nil (1- len)) offset)))
(arr-tmp (make-array `(,k) :initial-element 0))
(arr-out (make-array len)))
(dotimes (j len)
(setf (aref arr-tmp (+ offset (aref arr j))) (+ (aref arr-tmp (+ offset (aref arr j))) 1)))
(dotimes (i (1- k))
(setf (aref arr-tmp (+ i 1)) (+ (aref arr-tmp (+ i 1)) (aref arr-tmp i))))
(do ((j (1- len) (- j 1)))
((< j 0) arr-out)
(setf (aref arr-out (1- (aref arr-tmp (+ offset (aref arr j))))) (aref arr j))
(setf (aref arr-tmp (+ offset (aref arr j))) (- (aref arr-tmp (+ offset (aref arr j))) 1))))))
or
def `counting-sort` (a: Array[Int]): Array[Int] = {
/*
* 假設(shè)數(shù)據(jù)分布在[0 - 9]中沿侈，且數(shù)據(jù)個(gè)數(shù)不超過(guò)區(qū)間長(zhǎng)度
*/
val min = 0
val max = 9
val c = new Array[Int](max - min + 1)
val b = new Array[Int](a.length)
for (i <- 0 until c.length) c(i) = 0
for (i <- 0 until a.length) c(a(i)) = c(a(i)) + 1
for (i <- 1 until c.length) c(i) = c(i) + c(i - 1)
for (i <- a.length - 1 to 0 by -1) {
b(c(a(i)) - 1) = a(i)
c(a(i)) = c(a(i)) - 1
}
b
}
