golangは常用並べ替えアルゴリズムを実現します.
並べ替えを簡単に選択
原理は詳しく述べています.並べ替えられていない配列の中で、最大または最小の要素を選択し、並べ替えられた配列の最初の配列が空です.
原理の説明:並べ替えられていない配列要素の中で、データを取って並べ替えられた配列に記入し、並べ替えられた配列を形成し、配列長は1の配列を並べ替えられた配列とします.
原理は詳しく述べます.隣接する二つの要素を比較して、順序が逆なら交換します.一輪の対比を経て、最大または最小の元素は先端に浮遊し、len(nums)-1ラウンドを経て、numsは秩序配列に変化します.
原理説明:分割して実行するステップ:は、まず数列から一つの数を基準数として取り出します. パーティションプロセスは、この数より大きい数を全部その右側に置いて、それより小さいか等しい数は全部その左側に置きます. は、各区間が一つの数(各区間が整然としている)まで、左右の区間に第二のステップを繰り返します.
原理説明:分割して実行するステップ: は、配列をいくつかの順序配列(配列要素は1つの配列である) に分割する.は、順序配列を2つずつ秩序化配列に結合し、1つの配列 に統合するまで、配列に統合する.
原理スタックの並べ替えのいくつかの操作:1.ビルド2.ヒープ調整3.積み上げ順序の具体的な原理は《白話経典アルゴリズムシリーズの7つの山と積み上げ順序》を参照してください.
原理は詳しく述べています.並べ替えられていない配列の中で、最大または最小の要素を選択し、並べ替えられた配列の最初の配列が空です.
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)
}
並べ替えの統合原理説明:分割して実行するステップ:
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)
}