全文所說排序默認(rèn)升序
- 插入排序
- 直接插入
- 二分插入
- 希爾排序
- 交換排序
- 冒泡排序
- 快速排序
- 選擇排序
- 簡單選擇排序
- 堆排序
- 歸并排序
一垃僚、插入排序
選擇一個(gè)元素插入到有序序列中去邢隧，使序列仍保持有序
1.直接插入排序：從序列中選擇一個(gè)元素 p ，依次和它前面的每個(gè)元素 f 比較冈在，如果 p < f倒慧，就把 f 向后移動(dòng)，直到最終 p >= f，則將p的值放在當(dāng)前 f 的后面
func SInsertSort(arr []int) {
for i:=1;i<len(arr);i++ {
p := arr[i]
j := i-1
for j>=0 && p < arr[j] {
arr[j+1] = arr[j]
j--
}
arr[j+1] = p
}
}
最壞時(shí)間復(fù)雜度：元素arr[i]要和前面的每一個(gè)元素比較纫谅，比較次數(shù)為 i*i炫贤。
所以 1 + 2 +... + n-1 = O(n^2) =
平均時(shí)間復(fù)雜度：因?yàn)閍rr[i]的平均比較次數(shù)為 。
所以 ≈
=
空間復(fù)雜度：S(n) = O(1)
穩(wěn)定性：穩(wěn)定（原來相等的元素相對(duì)位置不會(huì)邊）
2.二分插入排序：
利用二分查找確定應(yīng)該插入的位置付秕，可以較少比較次數(shù)兰珍，但是元素移動(dòng)次數(shù)不會(huì)減少
func BInsertSort(arr []int) {
for i := 1; i < len(arr); i++ {
p := arr[i]
left := 0
right := i - 1
for right >= left {
mid := (left + right) / 2
if p < arr[mid] {
right = mid - 1
} else {
left = mid + 1
}
}
for j := i - 1; j >= left; j-- { //left就是p應(yīng)該放置的位置
arr[j+1] = arr[j]
}
arr[left] = p
}
fmt.Println("二分插入", arr)
}
left就是p最終放置位置的原因：
right >= left 最后一次為true時(shí)，只能是right-left == 0询吴；或者right-left=1掠河；分析這兩種情況，可以發(fā)現(xiàn)left都應(yīng)該是最終放置位置猛计。
因?yàn)橹皇菧p少了一些比較的次數(shù)唠摹，移動(dòng)次數(shù)還是不變，所以耗時(shí)是要少一些奉瘤，但復(fù)雜度肯定仍舊是
最壞時(shí)間復(fù)雜度： =
平均時(shí)間復(fù)雜度： =
空間復(fù)雜度：S(n) = O(1)
穩(wěn)定性：穩(wěn)定（原來相等的元素相對(duì)位置不會(huì)邊）
3.希爾排序：二分和直插的移動(dòng)過程勾拉，都是每次移動(dòng)一步，比如第9個(gè)元素盗温，確定其最終該放置在arr[2]藕赞，那就要依次移動(dòng)[2,8]的所有元素，要移動(dòng)7次卖局。希爾排序的出發(fā)點(diǎn)是希望降低移動(dòng)次數(shù)斧蜕。希爾排序是設(shè)計(jì)想法是多次排序，剛開始每次移動(dòng)一大步砚偶，使其離最終位置比較接近惩激。
過程：確定一組降序的增量序列，比如9蟹演，5风钻，3，1酒请，依次用來對(duì)原序列進(jìn)行排序骡技。比如用9排序，將如下位置的元素排序
[0] [9] [18] [27]... 排序,假如為abcd羞反，排序后變成[0]=c, [9]=a, [18]=b, [27]=d
[1] [10] [19] [28]... 排序
[2] [11] [20] [29]... 排序
....
用增量5對(duì)新序列再次排序
[0] [5] [10] [15]...
[1] [6] [11] [16]...
[2] [7] [12] [17]...
5排序就是把a(bǔ)fk三個(gè)之間交換位置布朦，bgl三個(gè)之間交換位置...
func ShellSort(arr []int) {
ds := []int{9, 5, 3, 1}
for i := 0; i < len(ds); i++ {
d := ds[i]
for j := d; j < len(arr); j++ {
p := arr[j]
k := j - d
for k >= 0 && p < arr[k] { // 對(duì)每個(gè)子序列進(jìn)行直接插入排序，也可以改成二分或其他
arr[k+d] = arr[k]
k -= d
}
arr[k+d] = p
}
}
fmt.Println("希爾排序", arr)
}
// 希爾+二分插入
func ShellSort(arr []int) {
ds := []int{3, 1}
for i := 0; i < len(ds); i++ {
d := ds[i]
for j := d; j < len(arr); j++ {
p := arr[j]
left := j % d
right := j - d
for right >= left {
mid := ((right-left)/d/2)*d + left
if p < arr[mid] {
right = mid - d
} else {
left = mid + d
}
}
for k := j - d; k >= left; k -= d {
arr[k+d] = arr[k]
}
arr[left] = p
}
}
fmt.Println("希爾排序", arr)
}
增量序列的選取要求：
- 遞減
- 最后一個(gè)值必須是1
時(shí)間復(fù)雜度： 與增量序列的選取有關(guān)昼窗，分析難度較大是趴，下面是幾個(gè)序列的結(jié)論
空間復(fù)雜度：S(n) = O(1)穩(wěn)定性：不穩(wěn)定。比如 1澄惊，3唆途，2富雅，2' 增量序列選 2，1肛搬，得到 1 2' 2 3
二没佑、交換排序
比較元素的大小，根據(jù)結(jié)果交換位置
1.冒泡排序
下降法：從開頭向后掃描温赔，將大的放到后面去
上升法：從末尾向前掃描蛤奢，將小的放到前面去
func BubbleSort() {
arr := []int{
9, 5, 47, 11, 19, 6, 34, 31, 2, 10,
}
for sortedLen := 0; sortedLen < len(arr)-1; sortedLen++ {
for j := len(arr) - 1; j >= 1+sortedLen; j-- {
p := arr[j]
if p < arr[j-1] {// 上升法，把小的換到前
arr[j] = arr[j-1]
arr[j-1] = p
}
}
}
fmt.Println("冒泡排序", arr)
}
缺點(diǎn)：該序列已經(jīng)全部有序時(shí)陶贼，程序不能感知到啤贩。比如 1,2,5,3，第一次上升后就已經(jīng)全部有序了拜秧。
改進(jìn)：
func BubbleSort() {
arr := []int{
9, 5, 47, 11, 19, 6, 34, 31, 2, 10,
}
sortedLen := 0
hasUnSorted := true
for hasUnSorted {
hasUnSorted = false
for j := len(arr) - 1; j >= 1+sortedLen; j-- {
p := arr[j]
if p < arr[j-1] {
arr[j] = arr[j-1]
arr[j-1] = p
hasUnSorted = true
}
}
sortedLen++
}
fmt.Println("冒泡排序", arr)
}
該版本還有缺點(diǎn)痹屹，每次可能還會(huì)和已經(jīng)有序的部分比較一下。比如4,5,6,9,8,7腹纳，第一輪從頭到尾交換后痢掠，得到4,5,6,7,9,8, 第二輪比較就應(yīng)該在7之后的位置停止
下面是一個(gè)改進(jìn)驱犹，記錄了上一輪冒泡將最小元素放在了x處嘲恍，下一次上升的上限就應(yīng)該是停止處之后（記作x+1）。
func BubbleSort() {
arr := []int{
9, 5, 47, 11, 19, 6, 34, 31, 2, 10,
}
i := 0
for i <= len(arr)-2 {
j := len(arr) - 2
for j >= i {
p := arr[j]
if p > arr[j+1] {
arr[j] = arr[j+1]
arr[j+1] = p
}
j--
}
i = j + 2
}
fmt.Println("冒泡排序", arr)
}
最壞時(shí)間復(fù)雜度：任意兩個(gè)元素之間都逆序雄驹，最多就有個(gè)逆序佃牛，每次交換能減少一個(gè)逆序。
=
平均時(shí)間復(fù)雜度： 逆序平均為医舆，所以
=
≈
空間復(fù)雜度：S(n) = O(1)
穩(wěn)定性：穩(wěn)定（原來相等的元素相對(duì)位置不會(huì)邊）
2.快速排序
快速排序俘侠，任意選擇一個(gè)元素，將比它大的放在其后蔬将，比它小的放在它前面爷速。然后再分別對(duì)前后兩端再次執(zhí)行此操作。
func QuickSort(arr []int, i int, j int) {
v := arr[i]
pv := i
d := "end"
for j > i {
if d == "end" {
if arr[j] < v {
arr[i] = arr[j]
pv = j
i++
d = "start"
} else {
j--
}
}
if d == "start" {
if arr[i] > v {
arr[j] = arr[i]
pv = i
j--
d = "end"
} else {
i++
}
}
}
arr[pv] = v
if pv-1-i > 0 {
QuickSort(arr, i, pv-1)
}
if j-pv-1 > 0 {
QuickSort(arr, pv+1, j)
}
}
arr := []int{
9, 5, 47, 11, 19, 6, 34, 31, 2, 10,
}
QuickSort(arr, 0, len(arr)-1)
fmt.Println(arr)
最好時(shí)間復(fù)雜度：O(nlogn)
最壞時(shí)間復(fù)雜度：O(n^2)
平均時(shí)間復(fù)雜度：O(nlogn)
空間復(fù)雜度：O(logn)
三霞怀、選擇排序
每次選出最大或最小的放到后面或前面
1.簡單選擇排序
func SimpleSelectSort(arr []int) {
for i:=0;i<len(arr)-1;i++ {
min := i
for j:=i+1;j<len(arr);j++ {
if arr[j] < arr[min] {
min = j
}
}
v := arr[i]
arr[i] = arr[min]
arr[min] = v
}
}
時(shí)間復(fù)雜度： =
空間復(fù)雜度：S(n) = O(1)
穩(wěn)定性：穩(wěn)定（原來相等的元素相對(duì)位置不會(huì)邊）
2.堆排序
堆是一種特殊的完全二叉樹惫东，如果 父節(jié)點(diǎn)p子節(jié)點(diǎn)c，稱大根堆毙石。父節(jié)點(diǎn)p
子節(jié)點(diǎn)c廉沮，稱小根堆。
堆排序就是將序列排成堆（利用順序存儲(chǔ)的話徐矩，只需要調(diào)整序列位置即可）滞时，這樣根結(jié)點(diǎn)就是最大值（大根堆），然后將根結(jié)點(diǎn)和尾結(jié)點(diǎn)交換滤灯，這樣就最大元素就放在了正確的位置上坪稽，然后再重新堆化前面的序列曼玩，再選出當(dāng)前堆的最大，放到倒數(shù)第二個(gè)位置上...
舉例說明：
原始序列[]int{9, 5, 47, 11, 19, 6, 34, 31, 2, 10,}待使用堆排序方法排序刽漂。
將其看作一棵順序存儲(chǔ)的完全二叉樹
從最后一個(gè)非葉結(jié)點(diǎn)開始向前遍掃描演训，遇到不符合堆序的就調(diào)整順序。
- arr[4]=19贝咙，符合堆序（大于它的所有子節(jié)點(diǎn)）
- arr[3]=11样悟，不符合堆序，arr[3] < arr[7]庭猩，交換arr[3]和arr[7]窟她，得到arr[3]=31,arr[7]=11
- arr[2]=47，符合堆序
- arr[1]=5蔼水，不符合堆序震糖，arr[1]<arr[3]=31，交換arr[1]和arr[3]趴腋，得到arr[1]=31吊说，arr[3]=5。此時(shí)arr[3]=5<arr[7]=11优炬，再次不符合堆序颁井，交換arr[3]和arr[7]，得到arr[3]=11,arr[7]=5
- arr[0]=9蠢护，不符合堆序雅宾，arr[0]<arr[2]...
這樣就得到了堆化好的序列 []int{47,31,34,11,19,6,9,5,2,10,}
完成了堆化之后，只需要重復(fù) “找最大值(即當(dāng)前堆根)” + “和堆尾元素交換位置” + “堆長度-1” + “重新堆化”葵硕，n-1遍即可眉抬。
第一步，交換arr[0]和arr[9]懈凹，堆范圍從arr[0]~arr[9]變成arr[0]~arr[8]
第二步蜀变，重新堆化，只需從根開始調(diào)整就行
重復(fù)...
func HeapSort() {
arr := []int{
9, 5, 47, 11, 19, 6, 34, 31, 2, 10,
}
for i := (len(arr) - 2) / 2; i >= 0; i-- {
// (len(arr) - 2)/2是最后一個(gè)結(jié)點(diǎn)的父節(jié)點(diǎn)介评，也就是最后一個(gè)非葉結(jié)點(diǎn)
heapfy(arr, i, len(arr)-1)
}
for j := 0; j < len(arr)-1; j++ {
max := arr[0]
arr[0] = arr[len(arr)-1-j]
arr[len(arr)-1-j] = max
heapfy(arr, 0, len(arr)-1-j-1)
}
fmt.Println("堆排序", arr)
}
func heapfy(arr []int, root int, end int) {
leftSon := 2*root + 1
if leftSon > end {
return
}
rightSon := 2*root + 2
max := leftSon
v := arr[root]
if rightSon <= end && arr[rightSon] > arr[leftSon] {
max = rightSon
}
if v < arr[max] {
arr[root] = arr[max]
arr[max] = v
if max*2+1 <= end {
heapfy(arr, max, end)
}
}
}
完全二叉樹的順序存儲(chǔ)库北，通常從數(shù)組位置1開始存儲(chǔ)，這樣比較方便計(jì)算父子結(jié)點(diǎn)位置威沫。如果一個(gè)結(jié)點(diǎn)在數(shù)組中的index是i贤惯，那其左子結(jié)點(diǎn)是2i，右子是2i+1棒掠，父結(jié)點(diǎn)是i/2（向下取整）孵构。如果要從0開始存儲(chǔ)的話，每個(gè)元素的index都會(huì)減少1烟很，i變成i-1颈墅，設(shè)i-1=k蜡镶，2i變成2i-1=2k+1，... 可以推出新的關(guān)系是 原結(jié)點(diǎn)k恤筛，左子節(jié)點(diǎn)2k+1官还， 右子結(jié)點(diǎn)2k+2 父結(jié)點(diǎn) (k-1)/2 (下整)
平均時(shí)間復(fù)雜度：O(nlogn)
最壞時(shí)間復(fù)雜度：O(nlogn)
空間復(fù)雜度：O(1)
穩(wěn)定性：不穩(wěn)定
歸并排序
歸并排序是利用分治思想，欲排序abcd毒坛，先將ab望伦，cd分別排序，然后再合并兩個(gè)有序表煎殷。
func MergeSort(arr []int) {
if len(arr) < 2 {
return
}
if len(arr) == 2 {
v := arr[0]
if v > arr[1] {
arr[0] = arr[1]
arr[1] = arr[0]
}
return
}
mid := len(arr) / 2
MergeSort(arr[:mid])
MergeSort(arr[mid:])
merge(arr)
}
func merge(arr []int) {
mid := len(arr) / 2
i := 0
j := mid
k := 0
tempArr := make([]int, len(arr))
for i < mid && j < len(arr) {
if arr[i] <= arr[j] {
tempArr[k] = arr[i]
i++
k++
} else {
tempArr[k] = arr[j]
j++
k++
}
}
for i < mid {
tempArr[k] = arr[i]
i++
k++
}
for j < len(arr) {
tempArr[k] = arr[j]
j++
k++
}
for i2, v := range tempArr {
arr[i2] = v
}
}
非遞歸版本如下：
func MergeSort(arr []int) {
segLen := 1
for segLen < len(arr) {
for i := 0; i < len(arr); i += 2 * segLen {
merge(arr, i, i+segLen)
}
segLen *= 2
}
fmt.Println("歸并排序", arr)
}
func merge(arr []int, start1 int, start2 int) {
if start2 > len(arr)-1 {
return
}
segLen := start2 - start1
end2 := start2 + segLen - 1
if end2 > len(arr)-1 {
end2 = len(arr) - 1
}
p1 := start1
p2 := start2
i := 0
tempArr := make([]int, end2-start1+1)
for p1 < start2 && p2 <= end2 {
if arr[p1] <= arr[p2] {
tempArr[i] = arr[p1]
i++
p1++
} else {
tempArr[i] = arr[p2]
i++
p2++
}
}
for p1 < start2 {
tempArr[i] = arr[p1]
i++
p1++
}
for p2 <= end2 {
tempArr[i] = arr[p2]
i++
p2++
}
for j := 0; j < len(tempArr); j++ {
arr[start1+j] = tempArr[j]
}
}
時(shí)間復(fù)雜度：O(nlogn)
空間復(fù)雜度：O(n)
穩(wěn)定性：穩(wěn)定
