排序算法

• • 1.插入排序
  • 2. 希爾排序
  • 3. 選擇排序
  • 4 .堆排序

1.插入排序

func insertSort(arr []int) {// 將數組分為已經排序好的區間[0, bound), 和未排序好的區間[bound,length]for i := 0; i < len(arr); i++ {end := i-1cur := arr[i]// 如果遇到了比cur大的元素就需要往后搬for end >= 0 && arr[end] > cur {arr[end+1] = arr[end]end--}arr[end+1] = cur} }

時間復雜度O(n^2)
空間復雜度O(1)

2. 希爾排序

希爾排序就是將插入排序多分了幾個組, 對每個組都使用插入排序
常常使用的gap = len(arr)/2, 之后再依次除以2

func insertSortWithGap(arr []int, gap int) {for i := 0; i < len(arr); i++ {end := i-gapcur := arr[i]for end >= 0 && arr[end] > cur {arr[end+gap] = arr[end]end -= gap}arr[end+gap] = cur} }func shellSort(arr []int) {// 如果會插入排序那么希爾排序也就會, 希爾排序就是將插入排序分堆利用gap來分組塊// 常用的gap就是長度依次除2gap := len(arr)/2for gap > 0 {insertSortWithGap(arr, gap)gap /= 2} }

3. 選擇排序

將當前下標先看做最小值, 然后依次從[i, len(arr)-1]的位置找到一個最小值的下標

func selectSort(arr []int) {if arr == nil || len(arr) < 2 {return}// 每次定義一個position, 用來找到后面的數組中的最小值for i := 0; i < len(arr)-1; i++ {// 以本次的i為下標先當做最小的元素position := ifor j := position+1; j < len(arr); j++ {if arr[j] < arr[position] {position = j}}arr[i], arr[position] = arr[position], arr[i]} }

O(n^2)
O(1) 常數級變量
還有一種可以改進的選擇排序思想, 就是在找最小值的下標時, 同時找到最大值的下標與最后的元素交換, 這樣就可以減少循環的次數

4 .堆排序

堆排和快排是兩個最重要的排序也是面試中考的最多的, 一定要動手實現幾次,
想要練習堆排, 建議可以去做力扣215題

func heapSort(arr []int) {size := len(arr)createHeap(arr, size)for i := len(arr)-1 ; i >= 0; i-- {arr[0], arr[i] = arr[i], arr[0]size--shiftDown(arr, 0, size)} }func createHeap(arr []int, size int) {// 堆排序的核心思想就是, 先建立一個大跟堆, 再依次將數組第一個元素和最后一個元素交換, 直至堆的大小0// 從第一個非葉子結點開始建堆root := (len(arr)-1-1) >> 1 // size == len(arr) size-1是最后一個元素的下標, 那么他的父親結點就是 parent = (size-1-1)/2for ; root >= 0; root-- {// 依次按照每一個節點向下調整shiftDown(arr, root, size)} }func shiftDown(arr []int, parent int, size int) {// 首先找到左孩子child := parent*2 + 1for child < size {// 一直向下調整// 判斷左子樹和右子數哪個大if child+1 < size && arr[child] < arr[child+1] {child += 1}// 判斷父親的值和孩子的值哪個大, 大了的話 就需要交換if arr[parent] < arr[child] {arr[parent], arr[child] = arr[child], arr[parent]}else {// 不需要交換直接breakbreak}parent = childchild = 2*parent +1} }

時間復雜度O(n*logn)
空間O(1)(忽略遞歸使用的棧空間)

總結

以上是生活随笔為你收集整理的排序算法(上)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。