golangは常用並べ替えアルゴリズムを実現します.


並べ替えを簡単に選択
原理は詳しく述べています.並べ替えられていない配列の中で、最大または最小の要素を選択し、並べ替えられた配列の最初の配列が空です.
import (
    "fmt"
)
//      
func simpleSelectSort(nums []int) {
    for i := 0; i < len(nums); i++ {
        min := i
        for j := i + 1; j < len(nums); j++ {
            if nums[min] > nums[j] {
                min = j
            }
        }
        if min != i {
            tmp := nums[min]
            nums[min] = nums[i]
            nums[i] = tmp
        }
    }
}
//test
func main()
{
    var nums = []int{7, 8, 11, 4, 9, 3, 15}
    fmt.Println("nums before insertSort:%s", nums)
    simpleSelectSort(nums)
    fmt.Println("nums after insertSort:%s", nums)
}
並べ替えの直接挿入
原理の説明:並べ替えられていない配列要素の中で、データを取って並べ替えられた配列に記入し、並べ替えられた配列を形成し、配列長は1の配列を並べ替えられた配列とします.
import (
    "fmt"
)
//    
func insertSort(nums []int) {
    for i := 1; i < len(nums); i++ {
        for j := 0; j < i; j++ {
            if nums[i] < nums[j] {
                tmp := nums[i]
                nums[i] = nums[j]
                nums[j] = tmp
            }
        }
    }
}
//test
func main()
{
    var nums = []int{7, 8, 11, 4, 9, 3, 15}
    fmt.Println("nums before insertSort:%s", nums)
    insertSort(nums)
    fmt.Println("nums after insertSort:%s", nums)
}
泡の並べ替え
原理は詳しく述べます.隣接する二つの要素を比較して、順序が逆なら交換します.一輪の対比を経て、最大または最小の元素は先端に浮遊し、len(nums)-1ラウンドを経て、numsは秩序配列に変化します.
import (
    "fmt"
)
//    
func bubbleSort(nums []int) {
    for i := 1; i < len(nums); i++ { //   len(nums)-1   
        for j := 0; j < len(nums)-i; j++ {
            if nums[j] > nums[j+1] {
                tmp := nums[j]
                nums[j] = nums[j+1]
                nums[j+1] = tmp
            }
        }
    }
}
//test
func main()
{
    var nums = []int{7, 8, 11, 4, 9, 3, 15}
    fmt.Println("nums before insertSort:%s", nums)
    bubbleSort(nums)
    fmt.Println("nums after insertSort:%s", nums)
}
クイックソート
原理説明:分割して実行するステップ:
  • は、まず数列から一つの数を基準数として取り出します.
  • パーティションプロセスは、この数より大きい数を全部その右側に置いて、それより小さいか等しい数は全部その左側に置きます.
  • は、各区間が一つの数(各区間が整然としている)まで、左右の区間に第二のステップを繰り返します.
    import (
        "fmt"
    )
    //    
    func quickSort(nums []int, start int, end int) {
        //    
        if start >= end {
            return
        }
        tmp := nums[start] //           
        left := start
        right := end
        //    
        for left < right {
            for tmp < nums[right] && left < right {
                right = right - 1
            }
            //here,tmp<=nums[right]  ---> tmp == nums[left]
            nums[left] = nums[right]
            //now, nums[right] is empty
            for tmp > nums[left] && left < right {
                left = left + 1
            }
            //here, tmp >=nums[left]    ---> tmp = nums[right]
            nums[right] = nums[left]
            //now, nums[left] is empty
        }
        nums[left] = tmp
    
        quickSort(nums, start, left-1) //left array sort
        quickSort(nums, left+1, end)   //right array sort
    }
    
    //test
    func main()
    {
        var nums = []int{7, 8, 11, 4, 9, 3, 15}
        fmt.Println("nums before insertSort:%s", nums)
        quickSort(nums, 0, lens(nums))
        fmt.Println("nums after insertSort:%s", nums)
    }
    並べ替えの統合
    原理説明:分割して実行するステップ:
  • は、配列をいくつかの順序配列(配列要素は1つの配列である)
  • に分割する.
  • は、順序配列を2つずつ秩序化配列に結合し、1つの配列
  • に統合するまで、配列に統合する.
    import (
        "fmt"
    )
    //    
    func mergeSort(nums []int, start int, boundce int, end int) {
        if start >= end { //    
            return
        }
        mergeSort(nums, start, start+(boundce-start)/2, boundce) //        
        mergeSort(nums, boundce+1, boundce+(end-boundce)/2, end) //        
        var tmp = make([]int, end-start+1, end-start+1)
        i := 0
        //    
        for i <= end-start {
            tmp[i] = nums[i+start]
            i = i + 1
        }
        //      
        i = 0                                      //           
        j := boundce - start + 1                   //         
        ii := start                                //         
        for i <= boundce-start && j <= end-start { //    
            /*                 */
            for i <= boundce-start && tmp[i] <= tmp[j] {
                nums[ii] = tmp[i]
                ii = ii + 1
                i = i + 1
            }
            //here --> tmp[i] > tmp[j]
            /*                 */
            for j <= end-start && tmp[j] <= tmp[i] {
                nums[ii] = tmp[j]
                ii = ii + 1
                j = j + 1
            }
        }
        //    
        //      
        if i == boundce-start+1 {
            for j <= end-start {
                nums[ii] = tmp[j]
                ii = ii + 1
                j = j + 1
            }
        }
        //      
        if j == end-start+1 {
            for i <= boundce-start {
                nums[ii] = tmp[i]
                ii = ii + 1
                i = i + 1
            }
        }
    }
    
    //test
    func main()
    {
        var nums = []int{7, 8, 11, 4, 9, 3, 15}
        fmt.Println("nums before insertSort:%s", nums)
        mergeSort(nums, 0, len(nums)/2-1, len(nums)-1)
        fmt.Println("nums after insertSort:%s", nums)
    }
    積み上げ順序
    原理スタックの並べ替えのいくつかの操作:1.ビルド2.ヒープ調整3.積み上げ順序の具体的な原理は《白話経典アルゴリズムシリーズの7つの山と積み上げ順序》を参照してください.
    package main
    
    import (
        "fmt"
    )
    //    :          ,             
    //2*n + 1     , 2*n + 2     
    func adjust(nums []int, pos int, len int) {
        tmp := pos
        j := 2*pos + 1
        for j < len {
            //       
            if j+1 < len {
                if nums[j+1] > nums[j] {
                    j++
                }
                if nums[tmp] < nums[j] {
                    nums[tmp], nums[j] = nums[j], nums[tmp]
                }
            } else {
                if nums[tmp] < nums[j] {
                    nums[tmp], nums[j] = nums[j], nums[tmp]
                }
            }
            //         ,  
            tmp = j
            j = j*2 + 1
        }
    }
    
    //    
    func buildHeap(nums []int) {
        len := len(nums)
        for i := len/2 - 1; i >= 0; i-- { //           “ ”,    “ ”     , len/2          ,       “ ”
            adjust(nums, i, len) //        
        }
    }
    
    /**
    *    
    */
    func heapSort(nums []int) {
        tmp := len(nums)
        if tmp == 0 {
            return
        }
        buildHeap(nums)
        for i := 0; i < len(nums); i++ {
            nums[tmp-1], nums[0] = nums[0], nums[tmp-1] //    
            tmp--
            adjust(nums, 0, tmp) //           ,     
        }
    }
    
    //test
    func main() {
        var nums = []int{7, 8, 11, 4, 9, 3, 15}
        fmt.Println("nums before insertSort:%s", nums)
        heapSort(nums)
        fmt.Println("nums after insertSort:%s", nums)
    }