-

package main

import (
    "fmt"
    "math/rand"
    "sort"
)

func main() {
    // 构建数据
    // > 乱序数组
    // > > -
    numbers := make([]int, 10)
    // > > -
    for i := 0; i < len(numbers); i++ {
        numbers[i] = rand.Intn(100)
    }
    // > 顺序数组
    // > > -
    sortedNumbers := append([]int{}, numbers...)
    // > > -
    sort.Ints(sortedNumbers)

    // 遍历排序并输出
    // > -
    sorters := []func([]int){
        bubbleSort, insertionSort, quickSort, selectionSort,
    }
    // > -
outer:
    for _, sorter := range sorters {
        // 验证
        for i := 0; i < 10; i++ {
            // 排序
            // > -
            maybeSortedNumbers := append([]int{}, numbers...)
            // > -
            sorter(maybeSortedNumbers)

            // 校验
            // > -
            for sortedNumberIndex, sortedNumber := range sortedNumbers {
                if maybeSortedNumbers[sortedNumberIndex] != sortedNumber {
                    // -
                    fmt.Println("disordered array")
                    // -
                    continue outer
                }
            }
        }
        // 输出结果
        fmt.Println("sorted array")
    }
}

// bubbleSort 冒泡排序
func bubbleSort(numbers []int) {
    for i := 0; i < len(numbers)-1; i++ {
        for j := 0; j < len(numbers)-1-i; j++ {
            if numbers[j] > numbers[j+1] {
                numbers[j], numbers[j+1] = numbers[j+1], numbers[j]
            }
        }
    }
}

// insertionSort 插入排序
func insertionSort(numbers []int) {
    for i := 1; i < len(numbers); i++ {
        // 记录元素
        number := numbers[i]
        // 找到合适的位置插入元素
        // > -
        j := i - 1
        // > -
        for j >= 0 && numbers[j] > number {
            // j 最小可减到 -1
            j--
        }
        // 操作
        // > 复制
        copy(numbers[j+2:], numbers[j+1:i])
        // > 插入
        numbers[j+1] = number
    }
}

// quickSort 快速排序
func quickSort(numbers []int) {
    quickSortLooper(numbers, 0, len(numbers)-1)
}

// quickSortLooper 快速排序
func quickSortLooper(numbers []int, left int, right int) {
    if left < right {
        // 记录数据
        i, j := left, right
        // 调整元素位置
        // > - | 选择 left 作为枢轴
        for i < j {
            // 查找
            // > 从右侧找到小于枢轴的元素 | 不大于就跳出循环
            for i < j && numbers[j] >= numbers[left] {
                j--
            }
            // > 从左侧找到大于枢轴的元素 | 不小于就跳出循环
            for i < j && numbers[i] <= numbers[left] {
                i++
            }
            // 交换
            numbers[i], numbers[j] = numbers[j], numbers[i]
        }
        // > 写入枢轴
        numbers[i], numbers[left] = numbers[left], numbers[i]
        // 递归处理
        // > -
        quickSortLooper(numbers, left, i-1)
        // > -
        quickSortLooper(numbers, i+1, right)
    }
}

// selectionSort 选择排序
func selectionSort(numbers []int) {
    for i := 0; i < len(numbers); i++ {
        // 记录最小元素位置
        k := i
        // 查找最小元素
        for j := i; j < len(numbers); j++ {
            if numbers[j] < numbers[k] {
                k = j
            }
        }
        // 交换最小元素和有序数组最后一个元素的位置
        numbers[i], numbers[k] = numbers[k], numbers[i]
    }
}