Sort Array

终于刷完了 5 种最常见的排序算法 , 后续尝试优化 , 并且还有其他高级排序算法的尝试

Leetcode Sort Array

快速排序

复盘

go的切片是引用类型 , 不需要取地址

Leetcode Sort Array

画图 定义 伪代码

思考写下来的乱七八糟字符图断电丢失了..... 尝试用keynote画 , 感觉清晰很多
partition过程:

Leetcode Sort Array Leetcode Sort Array Leetcode Sort Array

结果

func sortArray(nums []int) []int {
    quickSort(nums, 0, len(nums)-1)
    return nums
}

func quickSort(nums []int, start int, end int) {
    if start >= end {
        return
    }

    p := partition(nums, start, end)
    quickSort(nums, start, p-1)
    quickSort(nums, p+1, end)
}

func partition(nums []int, start int, end int) int {
    p := start
    j := start + 1
    i := start

    v := nums[p]

    for j <= end {
        if nums[j] < v {
            tmp1 := nums[j]
            nums[j] = nums[i+1]
            nums[i+1] = tmp1

            i++
            j++
        } else if nums[j] >= v {
            j++
        }
    }

    tmp2:=nums[i]
    nums[i]=nums[p]
    nums[p]=tmp2

    p=i
    return p
}

归并排序

复盘

对中位数的定义出了差错 , 之前二分查找的时候也是 , 只考虑到了两边的情况

( l +r ) /2

还有可以优化的地方

变量名定义乱七八糟 , 虽然在图里明确了

先写单个步骤,再加循环体和约束 , code complete 也讲过 , 复杂循环结构的编写

画图 / 定义 / 伪代码

这步很多都没做好呢 , 晚上看看bobo老师是怎么写的

Leetcode Sort Array Leetcode Sort Array Leetcode Sort Array

结果

func sortArray(nums []int) []int {
    endIndex := len(nums) - 1
    return mergeSort(nums, 0, endIndex)
}

func mergeSort(nums []int, i1 int, i2 int) []int {
    if i1 == i2 {
        return []int{nums[i1]}
    }
    if i1 > i2 {
        return []int{}
    }


    //return merge(mergeSort(nums, i1, i2/2), mergeSort(nums, i2/2+1 , i2))

    mid := (i1+i2)/2
    return merge(mergeSort(nums,i1,mid),mergeSort(nums,mid+1,i2))
}

func merge(sort1 []int, sort2 []int) []int {
    newArr := make([]int, len(sort1)+len(sort2))

    ls := 0
    le := len(sort1) - 1

    rs := 0
    re := len(sort2) - 1

    np := 0

    for ls<=le && rs<=re {
        if sort2[rs] < sort1[ls] {
            newArr[np] = sort2[rs]
            rs++
        } else {
            newArr[np] = sort1[ls]
            ls++
        }
        np++
    }

    for ls<=le {
        newArr[np]=sort1[ls]
        ls++
        np++
    }

    for rs<=re {
        newArr[np]=sort2[rs]
        rs++
        np++
    }
    return newArr
}

其他基本排序算法

// bubble
func sortArray1(nums []int) []int {
    n := len(nums)-1
    for i:=0;i<=n;i++ {
        for j:=1;j<=n;j++ {
            if nums[j-1]>nums[j] {
                tmp:=nums[j]
                nums[j]=nums[j-1]
                nums[j-1]=tmp
            }
        }
    }
    return nums
}

// select
func sortArray2(nums []int) []int {
    n := len(nums)-1
    for i:=0;i<=n;i++ {
        max:=nums[0]
        index:=0
        limit:=n-i;
        for j:=0;j<=limit;j++{
            if nums[j]>max {
                max=nums[j]
                index=j
            }
        }
        tmp:=nums[index]
        nums[index]=nums[limit]
        nums[limit]=tmp
    }

    return nums
}

//insert swap
func sortArray3(nums []int) []int {
    n := len(nums)-1
    for i:=1;i<=n;i++ {
        for j:=i-1;j>=0;j--{
            if nums[j]>nums[j+1] {
                tmp:=nums[j]
                nums[j]=nums[j+1]
                nums[j+1]=tmp
            }
        }
    }
    return nums
}

//insert optimization TODO;