42.Go语言·数据结构·排序

main.go

// Go语言·数据结构·排序
package main

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

var content string = `
————————————————Go语言·数据结构·排序————————————————————
一、排序
    1.冒泡排序  O(n²)   https://www.jianshu.com/p/eb74b2161f61
    2.选择排序  O(n^2)
        内部排序，从欲排序的数据中，按指定的规则选择一个最小的

    3.插入排序  O(n^2)
    4.快速排序  O(nlogn)
               减少咯比较，交换次数
        除以2 /2 递减

`

func main() {

    // var intArr [5]int = [...]int{24,69,80,57,33}
    // fmt.Println("排序前：",intArr)
    // QuickSort(&intArr)
    // fmt.Println("排序后：",intArr)

    var arr [8000000]int
    for i := 0; i < 8000000; i++ {
        arr[i] = rand.Intn(900000)
    }
    start := time.Now().Unix()
    //调用快速排序
    QuickSort(0, len(arr) - 1, &arr)
    end := time.Now().Unix()
    fmt.Println("main..")
    fmt.Printf("快速排序法耗时%d秒 \n", end - start)

}


//快速排序
//说明
//1. left 表示 数组左边的下标
//2. right 表示数组右边的下标
//3  array 表示要排序的数组
func QuickSort(left int, right int, array *[8000000]int) {
    l := left
    r := right
    // pivot 是中轴， 支点
    pivot := array[(left + right) / 2]
    temp := 0

    //for 循环的目标是将比 pivot 小的数放到 左边
    //  比 pivot 大的数放到 右边
    for ; l < r; {
        //从  pivot 的左边找到大于等于pivot的值
        for ; array[l] < pivot; {
            l++
        }
        //从  pivot 的右边边找到小于等于pivot的值
        for ; array[r] > pivot; {
            r--
        }
        // 1 >= r 表明本次分解任务完成, break
        if l >= r { 
            break
        }
        //交换
        temp = array[l]
        array[l] = array[r]
        array[r] = temp
        //优化
        if array[l]== pivot  {
            r--
        }
        if array[r]== pivot {
            l++         
        }
    }
    // 如果  1== r, 再移动下
    if l == r {
         l++
         r--
    }
    // 向左递归
    if left < r {
        QuickSort(left, r, array)
    }
    // 向右递归
    if right > l {
        QuickSort(l, right, array)
    }
}

/**
 * 插入排序
 *  var intArr [5]int = [...]int{24,69,80,57,33}
    fmt.Println("排序前：",intArr)
    insertSort(&intArr)
    fmt.Println("排序后：",intArr)
 */
func insertSort(intArr *[5]int) {
    // 完成一次交换，给第二个元素找到合适的位置并插入
    // // 第一次
    // insertVal := intArr[1]
    // insertIndex := 1-1

    // // 从大到小
    // for insertIndex>=0 && intArr[insertIndex] <insertVal {
    //  intArr[insertIndex+1] = intArr[insertIndex]
    //  insertIndex--
    // }
    // // 插入
    // if insertIndex +1 != 1{
    //  intArr[insertIndex+1] = insertVal
    // }


    // // 第二次
    // insertVal = intArr[2]
    // insertIndex = 2-1

    // // 从大到小
    // for insertIndex>=0 && intArr[insertIndex] <insertVal {
    //  intArr[insertIndex+1] = intArr[insertIndex]
    //  insertIndex--
    // }
    // // 插入
    // if insertIndex +1 != 2{
    //  intArr[insertIndex+1] = insertVal
    // }


    // // 第三次
    // insertVal = intArr[3]
    // insertIndex = 3-1

    // // 从大到小
    // for insertIndex>=0 && intArr[insertIndex] <insertVal {
    //  intArr[insertIndex+1] = intArr[insertIndex]
    //  insertIndex--
    // }
    // // 插入
    // if insertIndex +1 != 3{
    //  intArr[insertIndex+1] = insertVal
    // }


    // // 第四次
    // insertVal = intArr[4]
    // insertIndex = 4-1

    // // 从大到小
    // for insertIndex>=0 && intArr[insertIndex] <insertVal {
    //  intArr[insertIndex+1] = intArr[insertIndex]
    //  insertIndex--
    // }
    // // 插入
    // if insertIndex +1 != 4{
    //  intArr[insertIndex+1] = insertVal
    // }
    
    // 归纳
    for i:=1;i<len(intArr);i++{

        insertVal := intArr[i]
        insertIndex := i-1

        // 从大到小
        for insertIndex>=0 && intArr[insertIndex] <insertVal {
            intArr[insertIndex+1] = intArr[insertIndex]
            insertIndex--
        }

        // 插入
        if insertIndex +1 != i{
            intArr[insertIndex+1] = insertVal
        }
    }
}



/**
 * 选择排序
 *  var intArr [5]int = [...]int{24,69,80,57,13}
    fmt.Println("排序前：",intArr)
    selectSorting(&intArr)
    fmt.Println("排序后：",intArr)
 */
func selectSorting(intArr *[5]int) {
    // 标准的访问方式：
    // (*intArr)[0] = 2333  等价于  intArr[0] = 2333
    // 1.将第一个最大值 和intArr[0]交换
    // 
    // 
    // // 第一次：
    // max := intArr[0]
    // maxInde :=0
    // // 2.遍历
    // for i := 0+1; i <len(intArr) ; i++ {
    //  if max < intArr[i] {  //比较
    //      max = intArr[i]
    //      maxInde = i
    //  }
    // }
    // // 交换
    // if maxInde != 0 {
    //  intArr[0],intArr[maxInde] = intArr[maxInde],intArr[0]
    // }


    // // 第二次：
    // max = intArr[1]
    // maxInde =1
    // for i := 1+1; i <len(intArr) ; i++ {
    //  if max < intArr[i] {  //比较
    //      max = intArr[i]
    //      maxInde = i
    //  }
    // }
    // // 交换
    // if maxInde != 1 {
    //  intArr[1],intArr[maxInde] = intArr[maxInde],intArr[1]
    // }


    // // 第三次：
    // max = intArr[2]
    // maxInde =2
    // for i := 2+1; i <len(intArr) ; i++ {
    //  if max < intArr[i] {  //比较
    //      max = intArr[i]
    //      maxInde = i
    //  }
    // }
    // // 交换
    // if maxInde != 2 {
    //  intArr[2],intArr[maxInde] = intArr[maxInde],intArr[2]
    // }


    // // 第四次：
    // max = intArr[3]
    // maxInde =3
    // for i := 3+1; i <len(intArr) ; i++ {
    //  if max < intArr[i] {  //比较
    //      max = intArr[i]
    //      maxInde = i
    //  }
    // }
    // // 交换
    // if maxInde != 3 {
    //  intArr[3],intArr[maxInde] = intArr[maxInde],intArr[3]
    // }
    
    // 归纳
    for j:=0;j<len(intArr)-1;j++{
        max := intArr[j]
        maxInde :=j
        for i := j+1; i <len(intArr) ; i++ {
        if max < intArr[i] {  //比较
                max = intArr[i]
                maxInde = i
            }
        }
        // 交换
        if maxInde != j {
            intArr[j],intArr[maxInde] = intArr[maxInde],intArr[j]
        }
    }
}



/**
 * [bubbleSorting 冒泡排序 Bubble Sorting]
 * 从小到大
 * 思路（思想）-》代码（语法）
 * 经过len(intArr)-1论比较
 * 每一轮：比较的次数是递减[4,3,2,1]=len(intArr)-1-第几轮(从零开始的)
 * 即前面的一个数与后面的一个数比较  如果前面的数大就交换
 * @author Jhou Shuai
 * @datetime 2019-05-30T09:53:33+0800
 * @example:
 * var intArr [5]int = [...]int{24,69,80,57,13}
 * bubbleSorting(&intArr)
 */
func bubbleSorting(intArr *[5]int) {
    // 第一轮：
    // 第1次：24与69  [24,69,80,57,13]
    // 第2次：69与80  [24,69,80,57,13]
    // 第3次：80与57  80>57 [24,69,57,80,13]
    // 第4次：80与13  80>13 [24,69,57,13,80]
    // for j := 0; j< 4; j++ {
    //     if (*intArr)[j] > (*intArr)[j+1] {
    //         (*intArr)[j]   = (*intArr)[j] + (*intArr)[j+1]
    //         (*intArr)[j+1] = (*intArr)[j] - (*intArr)[j+1]
    //         (*intArr)[j]   = (*intArr)[j] - (*intArr)[j+1]
    //     }
    // }


    // 第二轮：
    // 第1次：24与69  [24,69,57,13,80]
    // 第2次：69与57  69>57 [24,57,69,13,80]
    // 第3次：69与13  69>13 [24,57,13,69,80]
    // for j := 0; j< 3; j++ {
    //     if (*intArr)[j] > (*intArr)[j+1] {
    //         (*intArr)[j]   = (*intArr)[j] + (*intArr)[j+1]
    //         (*intArr)[j+1] = (*intArr)[j] - (*intArr)[j+1]
    //         (*intArr)[j]   = (*intArr)[j] - (*intArr)[j+1]
    //     }
    // }

    // 第三轮：
    // 第1次：24与57  [24,57,13,69,80]
    // 第2次：57与13  57>13 [24,13,57,69,80]
    // for j := 0; j< 2; j++ {
    //     if (*intArr)[j] > (*intArr)[j+1] {
    //         (*intArr)[j]   = (*intArr)[j] + (*intArr)[j+1]
    //         (*intArr)[j+1] = (*intArr)[j] - (*intArr)[j+1]
    //         (*intArr)[j]   = (*intArr)[j] - (*intArr)[j+1]
    //     }
    // }

    // 第四轮：
    // 第1次：24与13 24>13 [13,24,57,69,80]
    // for j := 0; j< 1; j++ {
    //     if (*intArr)[j] > (*intArr)[j+1] {
    //         (*intArr)[j]   = (*intArr)[j] + (*intArr)[j+1]
    //         (*intArr)[j+1] = (*intArr)[j] - (*intArr)[j+1]
    //         (*intArr)[j]   = (*intArr)[j] - (*intArr)[j+1]
    //     }
    // }
    intArrLen := len(intArr)
    for i := 0; i < intArrLen-1; i++ {
        for j := 0; j< intArrLen-1-i; j++ {
            if (*intArr)[j] > (*intArr)[j+1] {
                (*intArr)[j]   = (*intArr)[j] + (*intArr)[j+1]
                (*intArr)[j+1] = (*intArr)[j] - (*intArr)[j+1]
                (*intArr)[j]   = (*intArr)[j] - (*intArr)[j+1]
            }
        }
    }
    fmt.Println((*intArr))
}