バブル、挿入、選択ソートの分析とまとめ

1:分析ソートアルゴリズムの3つの次元は何ですか.
答:実行効率(時間、空間複雑度)、メモリ消費、アルゴリズム安定性
2:アルゴリズム実行効率という次元からどの3つの面から測定しますか.
答え:最悪と平均複雑度、時間複雑度係数、定数と低次、比較と交換、移動回数が望ましい.
3:その場でソートする概念は何ですか.
答え:ソートする場合、ソート要素グループを除いて、追加のスペースは使用されません.つまり、その場でソートします.
4:並べ替えの安定性、安定性並べ替えアルゴリズムと不安定性並べ替えアルゴリズムの違いはどこですか.
答え:同じ要素に対して、ソート前後の位置は変わらず、安定アルゴリズムです.安定と不安定の違いは,同じ要素がソート前後の位置で変化するか否かである.
5:配列の満序度、秩序度、逆序度の概念は何ですか.計算方法
答:秩序度とは秩序要素の個数を指し、逆順序度とは逆順序要素対の個数を指し、満順序度とは後続の要素対を並べ替える個数を指し、両者の和は満順序度である.
6:バブルソートの実現構想はどうですか.バブルソートアルゴリズムを実現してください.
答え:隣接する要素を比較して、秩序があれば交換しないで、逆順序で交換して、最後の要素まで、このように条件を満たす要素が最終的な位置に移動することを保証することができます.次のラウンドは2番目の要素から始まり、最後から2番目の要素までです.コード:BubleSort.go

package main

import (
    "fmt"
)

func main() {
    var arr [5]int = [5]int{1,3,2,5,2}
    var arrLength = len(arr)
    for i:=0;i< arrLength;i++ {
        flag := false
        //            ，         
        for j:=1;j arr[j+1]) {
                arr[j],arr[j+1] = arr[j+1],arr[j]
                flag = true
            }
        }
        if(!flag) {
            break
        }
    }
    fmt.Println(arr)
}

7:バブルソートはなぜその場ソートアルゴリズムなのか、なぜ安定ソートアルゴリズムなのか、最悪が最もよく、平均時間の複雑度はそれぞれいくらですか.
答え:余分なスペースを使用しません.同じ元素は比較的交換しないと安定し,交換しないと安定しない.最良O(N),最悪O(n 2),平均O(N 2)
8:挿入ソートの実現構想はどうですか.挿入ソートアルゴリズムを実現してください.
答え:並べ替え対象の要素グループを並べ替え区と未並べ替え区に分け、未並べ替え区の要素を一度に並べ替え区に挿入し、並べ替え区が常に秩序を保つことを保証し、未並べ替え区が空のInsertSortであることを知っている.go

package main

import "fmt"

func main() {
    arr := [5]int{5,4,3,2,1}
    arrLength := len(arr)
    for i:= 1;i< arrLength;i++ {
        tempValue := arr[i]
        j := i - 1
        for ;j>=0;j-- {  //          
            if(arr[j] > tempValue) { //      
                arr[j+1] = arr[j] //    
            }
        }
        arr[j+1] = tempValue 
    }
    fmt.Println(arr)
}

9:挿入ソートはなぜその場ソートアルゴリズムなのか、最悪で、平均複雑度はそれぞれいくらですか.
答え:余分なスペースソートは使用されていません.最良O(n),平均O(n 2)
10:選択ソートの実現構想はどうですか.選択ソートアルゴリズムを実現してください.
答え:ソート対象の要素グループをソート済み領域と未ソート領域に分け、未ソート領域に条件を満たす要素を挿入してソート領域の最後に、未ソート領域が空になるまで挿入します.

package main 

import "fmt"

func main() {
    arr := [5]int{5,4,3,2,1}
    arrLength := len(arr)

    for i:=0;i

11:ソートを選択したのはなぜその場ソートアルゴリズムなのか、なぜ安定ソートアルゴリズムではないのか、最悪で、平均時間の複雑度はそれぞれいくらですか.
答え:余分なスペースが使用されていないことを選択します.エレメントがソートされた領域を挿入すると、ソートされていない領域の最初のエレメントと条件を満たすエレメントが交換され、交換によって同じエレメントの位置が変化する可能性があります.最良O(n 2),最悪O(n 2),平均O(n 2).
12:挿入ソートは泡ソートよりも優れていますか?
バブルソート交換には3回の付与が必要であり、ソート交換を挿入するには1回の付与が必要であり、オーバーヘッド挿入が小さく、ソートを挿入する最適化空間が大きい.