排序（一）比较排序

作者: 原来哥哥是万家灯火 | 来源:发表于2022-09-09 23:41 被阅读0次

排序（一）比较排序
图形化排序算法比较：快速排序、插入排序、选择排序、冒泡排序
七大排序
算法总结
【非比较类排序算法】计数排序、桶排序(PHP实现)
常用排序算法（Python实现），持续更新中
排序算法
排序算法
五种排序
一天一算法 - 基数排序

全文所说排序默认升序

插入排序
- 直接插入
- 二分插入
- 希尔排序
交换排序
- 冒泡排序
- 快速排序
选择排序
- 简单选择排序
- 堆排序
归并排序

一、插入排序
选择一个元素插入到有序序列中去，使序列仍保持有序

1.直接插入排序：从序列中选择一个元素 p ，依次和它前面的每个元素 f 比较，如果 p < f，就把 f 向后移动，直到最终 p >= f，则将p的值放在当前 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
    }
}

最坏时间复杂度：元素arr[i]要和前面的每一个元素比较，比较次数为 i*i。
所以 $T_w(n) =$ 1 + 2 +... + n-1 = O(n^2) = $O(n^2)$
平均时间复杂度：因为arr[i]的平均比较次数为 $\frac{1+i}{2}$ 。
所以 $T_e(n)$ ≈ $\frac{1}{2}T_w(n)$ = $O(n^2)$
空间复杂度：S(n) = O(1)
稳定性：稳定（原来相等的元素相对位置不会边）

2.二分插入排序：
利用二分查找确定应该插入的位置，可以较少比较次数，但是元素移动次数不会减少

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应该放置的位置
            arr[j+1] = arr[j]
        }
        arr[left] = p
    }

    fmt.Println("二分插入", arr)
}

left就是p最终放置位置的原因：
right >= left 最后一次为true时，只能是right-left == 0；或者right-left=1；分析这两种情况，可以发现left都应该是最终放置位置。

因为只是减少了一些比较的次数，移动次数还是不变，所以耗时是要少一些，但复杂度肯定仍旧是 $O(n^2)$
最坏时间复杂度： $T_w(n) =$ = $O(n^2)$
平均时间复杂度： $T_e(n)$ = $O(n^2)$
空间复杂度：S(n) = O(1)
稳定性：稳定（原来相等的元素相对位置不会边）

3.希尔排序：二分和直插的移动过程，都是每次移动一步，比如第9个元素，确定其最终该放置在arr[2]，那就要依次移动[2,8]的所有元素，要移动7次。希尔排序的出发点是希望降低移动次数。希尔排序是设计想法是多次排序，刚开始每次移动一大步，使其离最终位置比较接近。

过程：确定一组降序的增量序列，比如9，5，3，1，依次用来对原序列进行排序。比如用9排序，将如下位置的元素排序
[0] [9] [18] [27]... 排序,假如为abcd，排序后变成[0]=c, [9]=a, [18]=b, [27]=d
[1] [10] [19] [28]... 排序
[2] [11] [20] [29]... 排序
....

用增量5对新序列再次排序
[0] [5] [10] [15]...
[1] [6] [11] [16]...
[2] [7] [12] [17]...

微信图片_20220822182227.jpg

5排序就是把afk三个之间交换位置，bgl三个之间交换位置...

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] { // 对每个子序列进行直接插入排序，也可以改成二分或其他
                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)

}

增量序列的选取要求：

$d[i] \le \sqrt{arr.length}$
递减
最后一个值必须是1

时间复杂度：与增量序列的选取有关，分析难度较大，下面是几个序列的结论

image.png
空间复杂度：S(n) = O(1)
稳定性：不稳定。
比如 1，3，2，2' 增量序列选 2，1，得到 1 2' 2 3

二、交换排序
比较元素的大小，根据结果交换位置

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)
}

缺点：该序列已经全部有序时，程序不能感知到。比如 1,2,5,3，第一次上升后就已经全部有序了。
改进：

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)

}

该版本还有缺点，每次可能还会和已经有序的部分比较一下。比如4,5,6,9,8,7，第一轮从头到尾交换后，得到4,5,6,7,9,8, 第二轮比较就应该在7之后的位置停止

下面是一个改进，记录了上一轮冒泡将最小元素放在了x处，下一次上升的上限就应该是停止处之后（记作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)
}

最坏时间复杂度：任意两个元素之间都逆序，最多就有 $\frac{n(n-1)}{2}$ 个逆序，每次交换能减少一个逆序。 $T_w(n)$ = $O(\frac{n(n-1)}{2})≈\frac{n^2}{2}$

平均时间复杂度：逆序平均为 $\frac{\frac{n(n-1)}{2}+0}{2}$ ，所以 $T_e(n)$ = $\frac{1}{2}T_w(n)$ ≈ $\frac{n^2}{4}$
空间复杂度：S(n) = O(1)
稳定性：稳定（原来相等的元素相对位置不会边）

2.快速排序
快速排序，任意选择一个元素，将比它大的放在其后，比它小的放在它前面。然后再分别对前后两端再次执行此操作。

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)

最好时间复杂度：O(nlogn)
最坏时间复杂度：O(n^2)
平均时间复杂度：O(nlogn)
空间复杂度：O(logn)

image.png

三、选择排序
每次选出最大或最小的放到后面或前面

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 
    }
}

时间复杂度： $T(n)$ = $\frac{n(n-1)}{2}$
空间复杂度：S(n) = O(1)
稳定性：稳定（原来相等的元素相对位置不会边）

2.堆排序
堆是一种特殊的完全二叉树，如果父节点p $\ge$ 子节点c，称大根堆。父节点p $\le$ 子节点c，称小根堆。

堆排序就是将序列排成堆（利用顺序存储的话，只需要调整序列位置即可），这样根结点就是最大值（大根堆），然后将根结点和尾结点交换，这样就最大元素就放在了正确的位置上，然后再重新堆化前面的序列，再选出当前堆的最大，放到倒数第二个位置上...

举例说明：
原始序列[]int{9, 5, 47, 11, 19, 6, 34, 31, 2, 10,}待使用堆排序方法排序。
将其看作一棵顺序存储的完全二叉树

微信图片_20220824170807.jpg

从最后一个非叶结点开始向前遍扫描，遇到不符合堆序的就调整顺序。

arr[4]=19，符合堆序（大于它的所有子节点）
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。此时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,}

微信图片_20220824172148.jpg

完成了堆化之后，只需要重复 “找最大值(即当前堆根)” + “和堆尾元素交换位置” + “堆长度-1” + “重新堆化”，n-1遍即可。
第一步，交换arr[0]和arr[9]，堆范围从arr[0]~arr[9]变成arr[0]~arr[8]
第二步，重新堆化，只需从根开始调整就行
重复...

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是最后一个结点的父节点，也就是最后一个非叶结点
        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)
        }
    }
}

完全二叉树的顺序存储，通常从数组位置1开始存储，这样比较方便计算父子结点位置。如果一个结点在数组中的index是i，那其左子结点是2i，右子是2i+1，父结点是i/2（向下取整）。如果要从0开始存储的话，每个元素的index都会减少1，i变成i-1，设i-1=k，2i变成2i-1=2k+1，... 可以推出新的关系是原结点k，左子节点2k+1，右子结点2k+2 父结点 (k-1)/2 (下整)

平均时间复杂度：O(nlogn)
最坏时间复杂度：O(nlogn)
空间复杂度：O(1)
稳定性：不稳定

归并排序
归并排序是利用分治思想，欲排序abcd，先将ab，cd分别排序，然后再合并两个有序表。

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]
    }
}

时间复杂度：O(nlogn)
空间复杂度：O(n)
稳定性：稳定

排序（一）比较排序
全文所说排序默认升序插入排序直接插入二分插入希尔排序交换排序冒泡排序快速排序选择排序简单选择排序堆排序归并...
图形化排序算法比较：快速排序、插入排序、选择排序、冒泡排序
图形化排序算法比较：快速排序、插入排序、选择排序、冒泡排序图形化排序算法比较：快速排序、插入排序、选择排序、冒泡排序
七大排序
阅读目录分类及比较冒泡排序快速排序选择排序插入排序希尔排序归并排序堆排序 1.分类及比较 2.冒泡排序基本思想...
算法总结
一，排序算法：冒泡排序，选择排序，快速排序，归并排序，插入排序，堆排序，希尔排序冒泡排序：会重复的比较数组中相邻的...
【非比较类排序算法】计数排序、桶排序(PHP实现)
常见的经典非比较类排序算法有计数排序、桶排序。区别于比较类排序，非比较类排序利用额外的内存空间实现更快排序，算法以...
常用排序算法（Python实现），持续更新中
一、非线性时间比较类排序交换排序冒泡排序快速排序插入排序简单插入排序希尔排序选择排序简单选择排序堆排序归并...
排序算法
概述一般排序算法(以元素比较为基础) => 快速排序、归并排序、插入排序、冒泡排序、堆排序特殊排序算法 => ...
排序算法
排序算法非线性时间比较类排序交换排序冒泡排序快速排序插入排序插入排序希尔排序选择排序简单选择排序...
五种排序
排序可以分为比较排序和非比较排序。比较排序是指在排序过程中，会将所有元素的值进行比较，将小的或者是大的按照一个规律...
一天一算法 - 基数排序
介绍比较型排序和非比较型排序首先，比较型排序和非比较型排序有何不同呢？很简单，如果在排序过程中，需要比较数组中...