目录
1、冒泡排序
2、插入排序
3、归并排序
4、快速排序
（1）普通快速排序
（2）Double快速排序
5、希尔排序
6、基数排序
7、计数排序
8、bfprt排序
1、冒泡排序package main
import (
"fmt"
"time"
)
func swap(a []int, i int, j int) {
if a[i] > a[j] {
// var temp int
temp := a[i]
a[i] = a[j]
a[j] = temp
}
}
// func sort(a []int ) {
// for i := 0; i < len(a); i++ {
// for j := 0; j < len(a)-i-1; j++ {
// if a[j] > a[j+1] {
// swap(a, j, j+1)
// }
// }
// }
// }
// 时间复杂度为O(n^2)
func Sort(a []int) {
start1 := time.Now()
for i := len(a) - 1; i > 0; i-- {
for j := 0; j < i; j++ {
if a[j] > a[j+1] {
swap(a, j, j+1)
}
}
}
// elapsed1 := time.Now().Sub(start1)
elapsed1 := time.Since(start1)
fmt.Println("该程序执行完成耗时：", elapsed1)
}
// 优化后的冒泡排序，时间复杂度为O(n)
// func optimizeSort(a []int) {
// start2 := time.Now()
// var didSwap bool
// for i := 0; i < len(a); i++ {
// didSwap = false
// for j := 0; j < len(a)-i-1; j++ {
// if a[j] > a[j+1] {
// swap(a, j, j+1)
// }
// didSwap = true
// }
// }
// if !didSwap {
// return
// }
// // elapsed2 := time.Now().Sub(start2)
// elapsed2 := time.Since(start2)
// fmt.Println("该程序优化后执行完成耗时：", elapsed2)
// }
func main() {
arr := []int{7, 3, 2, 6, 8, 1, 9, 5, 4, 10}
fmt.Println("排序前：")
fmt.Println(arr)
fmt.Println("排序后")
Sort(arr)
fmt.Println(arr)
// fmt.Println("优化排序后")
// optimizeSort(arr)
// fmt.Println(arr)
}
2、插入排序
package main
import "fmt"
func swap(a []int, i int, j int) {
temp := a[i]
a[i] = a[j]
a[j] = temp
}
func sort(a []int) {
for i := 1; i < len(a); i++ {
for j := i; j > 0 ; j-- {
if a[j] < a[j-1] {
swap(a, j, j-1)
}
}
fmt.Printf("这是第%d次循环的结果：", i)
fmt.Println(a)
}
}
func main() {
arr := []int{5, 3, 6, 8, 1, 7, 9, 4, 2}
fmt.Println("排序前：")
fmt.Println(arr)
sort(arr)
fmt.Println("排序后：")
fmt.Println(arr)
}
3、归并排序
package main
import "fmt"
// func swap(a []int, i int, j int) {
// if a[i] > a[j] {
// temp := a[i]
// a[i] = a[j]
// a[j] = temp
// }
// }
// 针对有序数组
func sort(a []int) {
i := 0
mid := len(a)/2
j := mid + 1
k := 0
temp := make([]int, len(a))
for i<=mid && j
4、快速排序
（1）普通快速排序
package main
import (
"fmt"
)
func swap(a []int, i int, j int) {
if a[i] > a[j] {
// var temp int
temp := a[i]
a[i] = a[j]
a[j] = temp
}
}
func partition(a []int, leftBound int, rightBound int) int {
pivot := rightBound
left := leftBound
right := rightBound - 1
for left <= right {
for left <= right && a[pivot] >= a[left] {
left++
}
for left <= right && a[pivot] < a[right] {
right--
}
if left < right {
swap(a, left, right)
}
}
swap(a, left, pivot)
return left
}
func sort(a []int, leftBound int, rightBound int) {
if leftBound >= rightBound {
return
}
mid := partition(a, leftBound, rightBound)
sort(a, leftBound, mid-1)
sort(a, mid+1, rightBound)
}
func main() {
arr := []int{7, 3, 2, 6, 8, 1, 9, 5, 4, 10}
fmt.Println("排序前：")
fmt.Println(arr)
sort(arr, 0, len(arr)-1)
fmt.Println("排序后")
fmt.Println(arr)
}
（2）Double快速排序
package main
import "fmt"
func Swap(a []int, i int, j int) {
temp := a[i]
a[i] = a[j]
a[j] = temp
}
func Partion(a []int, l int, r int) int {
i := l - 1
pivot := a[r]
for j := 1; j < r; j++ {
if a[j] <= pivot {
i++
Swap(a, a[i], a[j])
}
}
Swap(a, a[i+1], a[r])
return i+1
}
func QuickSort(a []int, l int, r int) {
if l < r {
mid := Partion(a, l, r)
QuickSort(a, l, mid-1)
QuickSort(a, mid+1, r)
}
}
func main() {
var n int
fmt.Scanln(&n)
arr := make([]int, n)
for i := 0; i < n; i++ {
fmt.Scanln(arr[i])
}
QuickSort(arr, 0, n-1)
for i := 0; i < n; i++ {
fmt.Println(arr[i])
}
}
5、希尔排序
package main
import "fmt"
func swap(a []int, i int, j int) {
temp := a[i]
a[i] = a[j]
a[j] = temp
}
// 适合短的数组
// func sort(a []int) {
// for h := 4; h > 0; h/=2 {
// // for h := len(a)/2; h>0; h/=2
// for i := h; i < len(a); i++ {
// for j := i; j > h-1; j -= h {
// if a[j] < a[j-h]{
// swap(a, j, j-h)
// }
// }
// }
// }
// }
// 适合长数组
// Knuth序列
// h=1;
// h=3*h+1
func sort(a []int) {
h1 := 1
for h1 <= len(a)/3{
h1 = 3*h1 + 1
}
for h := h1; h > 0; h=(h-1)/3 {
for i := h; i < len(a); i++ {
for j := i; j > h-1; j -= h {
if a[j] < a[j-h] {
swap(a, j, j-h)
}
}
}
}
}
func main() {
arr := []int{9, 6, 11, 3, 5, 12, 8, 7, 10, 15, 14, 4, 1, 13, 2}
fmt.Println("排序前：")
fmt.Println(arr)
sort(arr)
fmt.Println("排序后：")
fmt.Println(arr)
}
6、基数排序
package main
import (
"fmt"
"math"
)
// 找到最大值
func getMaxNum(a []int) int {
max := 0
for i := 0; i < len(a); i++ {
if a[i] > max {
max = a[i]
}
}
return max
}
// 得到最大位数
func getMaxBit(a []int, max int) int {
count := 1
temp := max / 10
for temp != 0 {
count++
temp = temp / 10
}
return count
}
func radixSort(a []int) []int {
maxNum := getMaxNum(a)
maxBit := getMaxBit(a, maxNum)
// fmt.Println("maxNum:", maxNum)
// fmt.Println("maxBit:", maxBit)
result := make([]int, len(a))
count := make([]int, 10)
for i := 0; i < maxBit; i++ {
division := int(math.Pow10(i))
//fmt.Println("除数为:", division)
for j := 0; j < len(a); j++ {
num := a[j] / division % 10 // 统计每个桶中的记录数
fmt.Printf("%d ", num)
count[num]++
}
fmt.Println("n计数数组count为:n", count)
for m := 1; m < len(count); m++ {
count[m] += count[m-1]
}
fmt.Println("累加的计数数组count为:n", count)
for k := len(a) - 1; k >= 0; k-- { //将所有桶中记录依次收集到result中
num := a[k] / division % 10
result[count[num]-1] = a[k]
count[num]--
}
// for i := 0; i < len(result); i++ {
// a[i] = result[i]
// }
copy(a, result)
for i := 0; i < len(count); i++ {
count[i] = 0
}
}
return a
}
func main() {
arr := []int{123, 111, 124, 222, 555, 1238, 656, 4747, 469, 190}
fmt.Println("排序前 ：")
fmt.Println(arr)
result := radixSort(arr)
fmt.Println("排序后 ：")
fmt.Println(result)
}
7、计数排序
package main
import "fmt"
func sort(a []int) []int{
// 如果数组长度小于等于1直接返回该数组
if len(a) <= 1 {
return a
}
// 找到最大值
max := 0
for i := 0; i < len(a); i++ {
if a[i] > max {
max = a[i]
}
}
// 初始化一个定长数组
count := make([]int, max+1)
for i := 0; i < len(a); i++ {
count[a[i]]++
}
fmt.Println("计数数组count为:", count)
result := make([]int, len(a))
// 不稳定的排序
// k := 0
// for j := 0; j < len(count); j++ {
// for count[j] > 0{
// result[k] = j
// k++
// count[j]--
// }
// }
for i := 1; i < len(count); i++ {
count[i] += count[i-1]
}
fmt.Println("累加的计数数组count为:", count)
for i := len(a)-1; i >= 0; i-- {
count[a[i]]--
result[count[a[i]]] = a[i]
}
return result
}
func main() {
arr := []int{1, 2, 3, 3, 2, 4, 5, 3, 2, 1, 6, 7, 6}
fmt.Println("排序前 ：")
fmt.Println(arr)
result := sort(arr)
fmt.Println("排序后 ：")
fmt.Println(result)
}
8、bfprt排序
package main
import "fmt"
func swap(a []int, i int, j int) {
temp := a[i]
a[i] = a[j]
a[j] = temp
}
// 插入排序
func insertSort(a []int, low int, high int) {
//var i, j, temp int
for i := low + 1; i <= high; i++ {
temp := a[i]
j := i -1
for j >= low && a[j] > temp {
a[j+1] = a[j]
j--
}
a[j+1] = temp
}
}
// 递归寻找中位数的中位数
func FindMid(a []int, low int, high int) int {
// 只有一个元素
if low == high {
return a[low]
}
var i, k int
for i = low; i + 4 <= high; i += 5 {
insertSort(a, i, i+4)
k = i - low
// 将中位数交换到前面
swap(a, low + k/5, i + 2)
// a[low + k/5], a[i + 2] = a[i + 2], a[low + k/5]
}
n := high - i + 1
// 最后一组不足5个元素
if n > 0 {
insertSort(a, i, high)
k = i - low
swap(a, low + k/5, i + n/2)
}
k = k/5
// 只有一位中位数
if k == 0 {
return a[low]
}
return FindMid(a, low, low + k)
}
// 寻找中位数的位置
func Partion(a []int, low int, high int, index int) int {
if low <= high {
// 将中位数与第一个元素交换
swap(a, index, low)
temp := a[low]
var i, j int
i = low
j = high
// 将小于中位数的元素交换到中位数的左边，大于中位数的元素交换到中位数的右边
for i != j {
for j > i && a[j] >= temp {
j--
}
a[i] = a[j]
}
a[i] = temp
return i
}
return -1
}
func Bfprt(a []int, low int, high int, k int) int {
// 中位数
median := FindMid(a, low, high)
// 中位数下标
index := Partion(a, low, high, median)
// 划分，得到中位数的 新的下标
newIndex := Partion(a, low, high, index)
//中位数在当前序列[low, high]中的位置
rank := newIndex - low + 1
if rank == k {
// 中位数是第K小元素
// 左边的K个元素（包括中位数）为Top-K
// 返回中位数下标
return newIndex
}else if rank > k {
return Bfprt(a, low, newIndex - 1, k)
}
return Bfprt(a, newIndex + 1, high, k - rank)
}
func main() {
arr := [12]int{12, 1, 8, 10, 6, 2, 5, 9, 11, 3, 4, 7}
fmt.Println("原始数据：")
fmt.Println(arr)
var k, index int
a := make([]int, len(arr))
for i := 1; i <= len(arr); i++ {
k = i
for j := 0; j < len(arr); j++ {
a[j] = arr[j]
}
index = Bfprt(a, 0, len(arr)-1, k)
fmt.Println("处理后的数据：")
for i := 0; i < len(arr); i++ {
fmt.Println(a[i])
}
fmt.Printf("第 %d 小元素n", a[index])
fmt.Printf("Top-%d的数据：", k)
// 对Top-k元素进行排序，方便 查看
insertSort(a, index - k + 1, index)
for i := index - k + 1; i <= index; i++ {
fmt.Println(a[i])
}
fmt.Println()
}
}
package main
import "fmt"
// func swap(a []int, i int, j int) {
// if a[i] > a[j] {
// temp := a[i]
// a[i] = a[j]
// a[j] = temp
// }
// }
// 针对有序数组
func sort(a []int) {
i := 0
mid := len(a)/2
j := mid + 1
k := 0
temp := make([]int, len(a))
for i<=mid && j
4、快速排序
（1）普通快速排序
package main
import (
"fmt"
)
func swap(a []int, i int, j int) {
if a[i] > a[j] {
// var temp int
temp := a[i]
a[i] = a[j]
a[j] = temp
}
}
func partition(a []int, leftBound int, rightBound int) int {
pivot := rightBound
left := leftBound
right := rightBound - 1
for left <= right {
for left <= right && a[pivot] >= a[left] {
left++
}
for left <= right && a[pivot] < a[right] {
right--
}
if left < right {
swap(a, left, right)
}
}
swap(a, left, pivot)
return left
}
func sort(a []int, leftBound int, rightBound int) {
if leftBound >= rightBound {
return
}
mid := partition(a, leftBound, rightBound)
sort(a, leftBound, mid-1)
sort(a, mid+1, rightBound)
}
func main() {
arr := []int{7, 3, 2, 6, 8, 1, 9, 5, 4, 10}
fmt.Println("排序前：")
fmt.Println(arr)
sort(arr, 0, len(arr)-1)
fmt.Println("排序后")
fmt.Println(arr)
}
（2）Double快速排序
package main
import "fmt"
func Swap(a []int, i int, j int) {
temp := a[i]
a[i] = a[j]
a[j] = temp
}
func Partion(a []int, l int, r int) int {
i := l - 1
pivot := a[r]
for j := 1; j < r; j++ {
if a[j] <= pivot {
i++
Swap(a, a[i], a[j])
}
}
Swap(a, a[i+1], a[r])
return i+1
}
func QuickSort(a []int, l int, r int) {
if l < r {
mid := Partion(a, l, r)
QuickSort(a, l, mid-1)
QuickSort(a, mid+1, r)
}
}
func main() {
var n int
fmt.Scanln(&n)
arr := make([]int, n)
for i := 0; i < n; i++ {
fmt.Scanln(arr[i])
}
QuickSort(arr, 0, n-1)
for i := 0; i < n; i++ {
fmt.Println(arr[i])
}
}
5、希尔排序
package main
import "fmt"
func swap(a []int, i int, j int) {
temp := a[i]
a[i] = a[j]
a[j] = temp
}
// 适合短的数组
// func sort(a []int) {
// for h := 4; h > 0; h/=2 {
// // for h := len(a)/2; h>0; h/=2
// for i := h; i < len(a); i++ {
// for j := i; j > h-1; j -= h {
// if a[j] < a[j-h]{
// swap(a, j, j-h)
// }
// }
// }
// }
// }
// 适合长数组
// Knuth序列
// h=1;
// h=3*h+1
func sort(a []int) {
h1 := 1
for h1 <= len(a)/3{
h1 = 3*h1 + 1
}
for h := h1; h > 0; h=(h-1)/3 {
for i := h; i < len(a); i++ {
for j := i; j > h-1; j -= h {
if a[j] < a[j-h] {
swap(a, j, j-h)
}
}
}
}
}
func main() {
arr := []int{9, 6, 11, 3, 5, 12, 8, 7, 10, 15, 14, 4, 1, 13, 2}
fmt.Println("排序前：")
fmt.Println(arr)
sort(arr)
fmt.Println("排序后：")
fmt.Println(arr)
}
6、基数排序
package main
import (
"fmt"
"math"
)
// 找到最大值
func getMaxNum(a []int) int {
max := 0
for i := 0; i < len(a); i++ {
if a[i] > max {
max = a[i]
}
}
return max
}
// 得到最大位数
func getMaxBit(a []int, max int) int {
count := 1
temp := max / 10
for temp != 0 {
count++
temp = temp / 10
}
return count
}
func radixSort(a []int) []int {
maxNum := getMaxNum(a)
maxBit := getMaxBit(a, maxNum)
// fmt.Println("maxNum:", maxNum)
// fmt.Println("maxBit:", maxBit)
result := make([]int, len(a))
count := make([]int, 10)
for i := 0; i < maxBit; i++ {
division := int(math.Pow10(i))
//fmt.Println("除数为:", division)
for j := 0; j < len(a); j++ {
num := a[j] / division % 10 // 统计每个桶中的记录数
fmt.Printf("%d ", num)
count[num]++
}
fmt.Println("n计数数组count为:n", count)
for m := 1; m < len(count); m++ {
count[m] += count[m-1]
}
fmt.Println("累加的计数数组count为:n", count)
for k := len(a) - 1; k >= 0; k-- { //将所有桶中记录依次收集到result中
num := a[k] / division % 10
result[count[num]-1] = a[k]
count[num]--
}
// for i := 0; i < len(result); i++ {
// a[i] = result[i]
// }
copy(a, result)
for i := 0; i < len(count); i++ {
count[i] = 0
}
}
return a
}
func main() {
arr := []int{123, 111, 124, 222, 555, 1238, 656, 4747, 469, 190}
fmt.Println("排序前 ：")
fmt.Println(arr)
result := radixSort(arr)
fmt.Println("排序后 ：")
fmt.Println(result)
}
7、计数排序
package main
import "fmt"
func sort(a []int) []int{
// 如果数组长度小于等于1直接返回该数组
if len(a) <= 1 {
return a
}
// 找到最大值
max := 0
for i := 0; i < len(a); i++ {
if a[i] > max {
max = a[i]
}
}
// 初始化一个定长数组
count := make([]int, max+1)
for i := 0; i < len(a); i++ {
count[a[i]]++
}
fmt.Println("计数数组count为:", count)
result := make([]int, len(a))
// 不稳定的排序
// k := 0
// for j := 0; j < len(count); j++ {
// for count[j] > 0{
// result[k] = j
// k++
// count[j]--
// }
// }
for i := 1; i < len(count); i++ {
count[i] += count[i-1]
}
fmt.Println("累加的计数数组count为:", count)
for i := len(a)-1; i >= 0; i-- {
count[a[i]]--
result[count[a[i]]] = a[i]
}
return result
}
func main() {
arr := []int{1, 2, 3, 3, 2, 4, 5, 3, 2, 1, 6, 7, 6}
fmt.Println("排序前 ：")
fmt.Println(arr)
result := sort(arr)
fmt.Println("排序后 ：")
fmt.Println(result)
}
8、bfprt排序
package main
import "fmt"
func swap(a []int, i int, j int) {
temp := a[i]
a[i] = a[j]
a[j] = temp
}
// 插入排序
func insertSort(a []int, low int, high int) {
//var i, j, temp int
for i := low + 1; i <= high; i++ {
temp := a[i]
j := i -1
for j >= low && a[j] > temp {
a[j+1] = a[j]
j--
}
a[j+1] = temp
}
}
// 递归寻找中位数的中位数
func FindMid(a []int, low int, high int) int {
// 只有一个元素
if low == high {
return a[low]
}
var i, k int
for i = low; i + 4 <= high; i += 5 {
insertSort(a, i, i+4)
k = i - low
// 将中位数交换到前面
swap(a, low + k/5, i + 2)
// a[low + k/5], a[i + 2] = a[i + 2], a[low + k/5]
}
n := high - i + 1
// 最后一组不足5个元素
if n > 0 {
insertSort(a, i, high)
k = i - low
swap(a, low + k/5, i + n/2)
}
k = k/5
// 只有一位中位数
if k == 0 {
return a[low]
}
return FindMid(a, low, low + k)
}
// 寻找中位数的位置
func Partion(a []int, low int, high int, index int) int {
if low <= high {
// 将中位数与第一个元素交换
swap(a, index, low)
temp := a[low]
var i, j int
i = low
j = high
// 将小于中位数的元素交换到中位数的左边，大于中位数的元素交换到中位数的右边
for i != j {
for j > i && a[j] >= temp {
j--
}
a[i] = a[j]
}
a[i] = temp
return i
}
return -1
}
func Bfprt(a []int, low int, high int, k int) int {
// 中位数
median := FindMid(a, low, high)
// 中位数下标
index := Partion(a, low, high, median)
// 划分，得到中位数的 新的下标
newIndex := Partion(a, low, high, index)
//中位数在当前序列[low, high]中的位置
rank := newIndex - low + 1
if rank == k {
// 中位数是第K小元素
// 左边的K个元素（包括中位数）为Top-K
// 返回中位数下标
return newIndex
}else if rank > k {
return Bfprt(a, low, newIndex - 1, k)
}
return Bfprt(a, newIndex + 1, high, k - rank)
}
func main() {
arr := [12]int{12, 1, 8, 10, 6, 2, 5, 9, 11, 3, 4, 7}
fmt.Println("原始数据：")
fmt.Println(arr)
var k, index int
a := make([]int, len(arr))
for i := 1; i <= len(arr); i++ {
k = i
for j := 0; j < len(arr); j++ {
a[j] = arr[j]
}
index = Bfprt(a, 0, len(arr)-1, k)
fmt.Println("处理后的数据：")
for i := 0; i < len(arr); i++ {
fmt.Println(a[i])
}
fmt.Printf("第 %d 小元素n", a[index])
fmt.Printf("Top-%d的数据：", k)
// 对Top-k元素进行排序，方便 查看
insertSort(a, index - k + 1, index)
for i := index - k + 1; i <= index; i++ {
fmt.Println(a[i])
}
fmt.Println()
}
}
