//插入
func Insert(arr []int) {
for i := 1; i < len(arr); i++ {
tmp := arr[i]
end := i - 1
//找插入位置&搬移
for ; end >= 0; end-- {
if tmp < arr[end] {
arr[end+1] = arr[end]
} else {
break
}
}
arr[end+1] = tmp
}
}
//插入-二分法
func Insert_Binary(arr []int) {
for i := 1; i < len(arr); i++ {
tmp := arr[i]
left := 0
right := i - 1
end := right
//二分法找插入位置
for left <= right {
mid := (left + right) / 2
if arr[mid] > tmp {
right = mid - 1
} else {
left = mid + 1
}
}
//搬移
for idx := end; idx >= left; idx-- {
arr[idx+1] = arr[idx]
}
arr[left] = tmp
}
}
//希尔
func ShellSort(arr []int) {
gap := len(arr)
for gap > 1 {
gap = gap / 3 + 1
for idx := gap; idx < len(arr); idx++ {
//把要插入的元素先保存一份
tmp := arr[idx];
end := idx - gap;
//比较、找插入位置&搬移
for end >= 0 && arr[end] > tmp {
arr[end + gap] = arr[end];
end = end - gap;
}
//插入元素
arr[end + gap] = tmp;
}
}
}
//选择
func Select(arr []int){
for idx := 0; idx < len(arr); idx++ {
min := idx
for i := idx + 1; i<len(arr); i++ {
if arr[i] < arr[min]{
min = i
}
}
arr[idx],arr[min] = arr[min],arr[idx]
}
}
//堆排 最后一个有孩子的结点的idx = (size-2)/2
func heapAdjust(arr []int, root int, size int){
parent := root
child := root * 2 + 1
for child < size{
if child + 1 < size && arr[child+1] > arr[child]{
child = child +1
}
if arr[child] > arr[parent]{
arr[child], arr[parent] = arr[parent], arr[child]
parent = child
child = parent * 2 + 1
} else {
break
}
}
}
func HeapSort(arr []int){
//建堆(大)--->升序
size := len(arr)
for i := (size-2)/2; i >=0 ; i-- {
heapAdjust(arr,i,size)
}
//排序
pos := size -1
for pos > 0 {
arr[0], arr[pos] = arr[pos], arr[0]
size--
heapAdjust(arr, 0, size)
pos--
}
}
//冒泡
func Bubble(arr []int){
size := len(arr)
for i := 0; i < size-1; i++ {
for j := 0; j < size-i-1; j++{
if arr[j] > arr[j+1]{
arr[j], arr[j+1] = arr[j+1],arr[j]
}
}
}
}
//快排
func Partion(arr []int, left int, right int)int{
cur := left
prev := cur - 1
key := arr[right]
for cur <= right{
if arr[cur] < key {
prev++
if prev != cur{
arr[prev], arr[cur] = arr[cur], arr[prev]
}
}
cur++
}
prev++
if arr[prev] > arr[right]{
arr[prev], arr[right] = arr[right], arr[prev]
}
return prev
}
func QuickSort(arr []int, left int, right int){
if (left < right) {
div := Partion(arr, left, right)
QuickSort(arr, left, div - 1)
QuickSort(arr, div + 1, right)
}
}
func QuickSort_NoRecursion(arr []int, size int){
定义栈：s
右边界：size - 1入栈
左边界：0入栈
for s != empty() {
left := s.top()
s.pop()
right := s.top()
s.pop()
if left < right {
div := Partion(arr, left, right)
s.push(right)
s.push(div + 1)
s.push(div - 1)
s.push(left)
}
}
}
//鸽巢问题----数组arr[100],9900<arr[idx]<10000,对数组进行排序
func CountSort(arr []int, size int) {
minVal := arr[0]
maxVal := arr[0]
//统计数组中的最大和最小元素
for i := 0; i < size; i++ {
if arr[i] < minVal {
minVal = arr[i]
}
if arr[i] > maxVal {
maxVal = arr[i]
}
}
fmt.Println(minVal)
fmt.Println(maxVal)
//make切片存放每个元素出现的次数，切片长度：part = maxVal - minVal + 1
part := maxVal - minVal + 1
var tmp = make([]int, part)
//统计每个元素出现的个数
for i := 0; i < size; i++ {
tmp[arr[i]-minVal]++
}
fmt.Println(tmp)
//重新排序
idx := 0
for i := 0; i < part; i++ {
for j := 0; j < tmp[i]; j++ {
arr[idx] = i + minVal
idx++
}
}
}
//归并
func Merge(arr []int, left int, mid int, right int) {
begin1 := left
end1 := mid
begin2 := mid+1
end2 := right
tmp := make([]int,len(arr))
idx := left
for begin1 <= end1 && begin2 <= end2 {
if arr[begin1] > arr[begin2] {
tmp[idx] = arr[begin2]
begin2++
} else {
tmp[idx] = arr[begin1]
begin1++
}
idx++
}
for begin1 <= end1 {
tmp[idx] = arr[begin1]
begin1++
idx++
}
for begin2 <= end2 {
tmp[idx] = arr[begin2]
begin2++
idx++
}
//将排过序的拷贝至arr，以便下次merge时做比较
for i := left; i < idx; i++ {
arr[i] = tmp[i]
}
}
func _Merge(arr []int, left int, right int) {
if left < right {
mid := (left+right) / 2
_Merge(arr, left, mid)
_Merge(arr, mid+1, right)
Merge(arr, left, mid, right)//归并
}
}
func MergeSort(arr []int) {
size := len(arr)
left := 0
right := size - 1
_Merge(arr, left, right)
}
