golang 实现排序

 : jank    :   : 2179    : 2018-03-05 19:46  数据结构和算法

package main

import (
	"fmt"
)

//冒泡排序
func bubble(arr []int) []int {
	n := len(arr)
	for i := 0; i < n; i++ {
		for j := i + 1; j < n; j++ {
			if arr[i] > arr[j] {
				arr[i], arr[j] = arr[j], arr[i]
			}
			fmt.Println("arr:", arr)
		}
	}
	return arr
}

//选择排序
func selection(arr []int) []int {
	n := len(arr)
	for i := 0; i < n; i++ {
		min := i //设置min=0,同时也是数组第一个键
		for j := i + 1; j < n; j++ {
			if arr[j] < arr[min] { //判断当前j的数只要有比当前arr[min]还小的就交换min值
				min = j
			}
		}
		if min != i {
			arr[i], arr[min] = arr[min], arr[i]
		}
	}

	return arr
}

//插入排序
func insertion(arr []int) []int {
	n := len(arr)
	for i := 1; i < n; i++ {
		for j := i; j > 0; j-- {
			if arr[j] < arr[j-1] { //如果 左边的数有比它大,就交换
				arr[j], arr[j-1] = arr[j-1], arr[j]
			}
		}
	}

	return arr
}

//希尔排序
func shell(arr []int) []int {
	n := len(arr)
	h := 1
	for h < n/3 {
		h = 3*h + 1
	}
	for h > 0 {
		for i := h; i < n; i++ {
			for j := i; j >= h; j -= h { //j>0 做一个边界守护,不让下标小于0
				if arr[j] < arr[j-h] {
					arr[j], arr[j-h] = arr[j-h], arr[j]
				}
			}
			fmt.Println(arr)
		}
		h = h / 3
	}

	return arr
}

//快速排序
func quick(arr []int) []int {
	n := len(arr)
	low, row := 0, n-1
	quickSort(arr, low, row)
	return arr

}

func quickSort(arr []int, start, end int) {
	if start < end {
		i, j := start, end
		key := arr[(start+end)/2]
		for i <= j {
			for arr[i] < key {
				i++
			}
			for arr[j] > key {
				j--
			}
			if i <= j {
				arr[i], arr[j] = arr[j], arr[i]
				i++
				j--
			}
		}

		if start < j {
			quickSort(arr, start, j)
		}
		if end > i {
			quickSort(arr, i, end)
		}
	}
}



func main() {
	arr := []int{10, 7, 29, 8, 5, 6, 100, 1, 3}
	//fmt.Println("bubble: ", bubble(arr))
	//fmt.Println(selection(arr))
	//fmt.Println(insertion(arr))
	//fmt.Println(shell(arr))
	fmt.Println(quick(arr))
}


   

备案编号:赣ICP备15011386号

联系方式:qq:1150662577    邮箱:1150662577@qq.com