r912. 排序数组

给你一个整数数组 nums，请你将该数组升序排列。三个都是nlogn的复杂度

快排：

算法步骤

  1. 从数列中挑出一个元素，称为 “基准”（pivot）;
  2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。称为分区（partition）操作；
  3. 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；

随机选一个On，二分法排每个logn

  1. //快排递归版本，时间nlogn,最坏n^2,空间logn，不稳定
  2. func sortArray(nums []int) []int {
  3.     quickSort(nums, 0 , len(nums) - 1)
  4.     return nums
  5. }
  7. func quickSort(nums []int, left, right int) {
  8.     if left > right {
  9.         return
  10.     }
  12.     i, j, base := left, right, nums[left]               //优化点，随机选基准
  14.     for i < j {
  15.         for nums[j] >= base && i < j {                    //nums[j],值大小,且=号
  16.             j--
  17.         }
  18.         for nums[i] <= base && i < j {
  19.             i++
  20.         }
  21.         nums[i], nums[j] = nums[j], nums[i]
  22.     }
  23.     nums[i], nums[left] = nums[left], nums[i]
  25.     quickSort(nums, left, i - 1)                        //i放在最后，因为i和left交换
  26.     quickSort(nums, i + 1, right)
  27. }

堆排序：

算法步骤

  1. 将无需序列构建成一个堆，根据升序降序需求选择大顶堆;
  2. 将堆顶元素与末尾元素交换，将最大元素”沉”到数组末端;
  3. 重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。

堆排序是一种选择排序，整体主要由构建初始堆+交换堆顶元素和末尾元素并重建堆两部分组成。其中构建初始堆经推导复杂度为O(n)，在交换并重建堆的过程中，需交换n-1次，而重建堆的过程中，根据完全二叉树的性质，[log2(n-1),log2(n-2)…1]逐步递减，近似为nlogn。所以堆排序时间复杂度一般认为就是O(nlogn)级

//堆排序：时间nlogn,空间O1，不稳定
func sortArray(nums []int) []int {
    heapSort(nums)
    return nums
}

//2，开始堆排
func heapSort(nums []int) []int {
    end := len(nums) - 1
    for i := end / 2; i >= 0; i-- {
        sink(nums, i, end)
    }
    for i := end; i >= 0; i-- {
        nums[0], nums[i] = nums[i], nums[0]
        end--
        sink(nums, 0, end)
    }
    return nums
}


//3，调用sink 下沉函数r
func sink(heap []int, root, end int) {
    for {
        child := root * 2 + 1
        if child > end {
            return
        }
        if child < end && heap[child] <= heap[child + 1] {
            child++
        }
        if heap[root] > heap[child] {
            return
        }

        heap[root], heap[child] = heap[child], heap[root]
        root = child
    }
}

归并排序：

  1. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
  2. 设定两个指针，最初位置分别为两个已经排序序列的起始位置；
  3. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
  4. 重复步骤 3 直到某一指针达到序列尾；
  5. 将另一序列剩下的所有元素直接复制到合并序列尾。

归并排序我们采用递归去实现（也可采用迭代的方式去实现）。分&治法 の典型应用
利用完全二叉树特性的排序，一般性能都不会太差，每次合并操作的平均时间复杂度为O(n)，而完全二叉树的深度为|log2n|。总的平均时间复杂度为O(nlogn)。

//归并排序：时间nlogn, 空间On，稳定
func sortArray(nums []int) []int {
    return mergeSort(nums)                            //不用返回nums，稍有不同
}

func mergeSort(nums []int) []int {
    if len(nums) <= 1 {
        return nums
    }

    mid := len(nums) / 2                            //1，分治法：divide 分为两段；left前半段，right后半段
    left := mergeSort(nums[:mid])
    right := mergeSort(nums[mid:])

    return merge(left, right)                        //2，合并两段数据
}

func merge(left, right []int) []int {
    result := make([]int, len(left) + len(right))    //新建一个数组，长度为前后两段和
    l, r, i := 0, 0, 0

    for l < len(left) && r < len(right) {            //3，两边数组合并游标
        if left[l] < right[r] {                        //前半段游标 和 后半段游标 比较
            result[i] = left[l]
            l++
        } else {
            result[i] = right[r]
            r++
        }
        i++
    }
    copy(result[i: ], left[l: ])                        //4，剩余部分合并
    copy(result[i +len(left) -l: ], right[r: ])

    return result
}

测试函数

//1，随意写一个乱序数组，测试
package main

import "fmt"

func main() {
    num1:= []int{10, 9, 10, 30, 2, 5, 45, 8, 63, 234, 12, 12345}
    fmt.Println(sortArray(num1))
}


//1, 带其他参数的数组
package main
import ("fmt")

func main() {
    arr := []int{1, 9, 10, 30, 2, 5, 45, 8, 63, 234, 12, 12345}
    k := 4
    fmt.Println(getLeastNumbers(arr,k))
}



//3，随机生成数组，测试前后变化
package main
import(
    "fmt"
    "math/rand"
)

func main() {
    s1 := make([]int, 0, 16)

    for i := 0; i < 16; i++ {
        s1 = append(s1, rand.Intn(100))
    }
    fmt.Println(s1)

    quickSort(s1)
    fmt.Println(s1)
}