42.Go语言·数据结构·排序
2019-06-20 本文已影响0人
一枼落知天下
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))
}
