常见算法

2020-03-25

快排 1.选取基准值tag：选取第一个元素为基准值（每次递归调用的基准值不等） 2.从 0 向后查找到比 tag 大的数，否则 i++ 3.从 n 向前查找到比 tag 小的数，否则 j– 4.交换两个数 5.全部交换后此时 i==j,递归调用，继续比较i位置两侧位置

//第一种方式，递归传入分割后的数组
func quicksort(s []int){
    if len(s)<=0 {
        return
    }
    tag:=s[0]
    i:=0
    j:=len(s)-1
    for i<j  {
        for s[j]>tag&&i<j {
            j--
        }
        for s[i]<tag&&i<j {
            i++
        }
        s[i],s[j]=s[j],s[i]//交换
    }
    quicksort(s[:i])
    quicksort(s[i+1:])
}

//第二种方式，递归传入原数组
func quicksort(s []int,start int,end int){
    if start >=end{
        return
    }
    tag:=s[start]
    i:=start
    j:=end
    for i<j  {
        for s[j]>tag&&i<j {
            j--
        }
        for s[i]<tag&&i<j {
            i++
        }
        s[i],s[j]=s[j],s[i]//交换
    }
    quicksort(s,start,i-1)
    quicksort(s,i+1,end)
}

// QuickSort
package main

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

func swap(a int, b int) (int, int) {
	return b, a
}

func partition(aris []int, begin int, end int) int {
	pvalue := aris[begin]
	i := begin
	j := begin + 1
	for j < end {
		if aris[j] < pvalue {
			i++
			aris[i], aris[j] = swap(aris[i], aris[j])
		}
		j++
	}
	aris[i], aris[begin] = swap(aris[i], aris[begin])
	return i
}

func quick_sort(aris []int, begin int, end int) {
	if begin+1 < end {
		mid := partition(aris, begin, end)
		quick_sort(aris, begin, mid)
		quick_sort(aris, mid+1, end)
	}
}

func rand_array(aris []int, lent int) {
	for i := 0; i < lent; i++ {
		r := rand.New(rand.NewSource(time.Now().UnixNano()))
		aris[i] = r.Intn(1000)
	}
}

func main() {
	intas := []int{0, 0, 0, 0, 7, 20, 4, 77, 1, 22}
	rand_array(intas, 10)
	fmt.Println(intas)
	quick_sort(intas, 0, 10)
	fmt.Println(intas)
}

选择排序

package main

import "fmt"

func main() {
    numbers := []int{6, 2, 7, 5, 8, 9}
    SelectSort(numbers)

    fmt.Println(numbers)
}

func SelectSort(values []int) {
    length := len(values)
    if length <= 1 {
        return
    }

    for i := 0; i < length; i++ {
        min := i // 初始的最小值位置从0开始，依次向右

        // 从i右侧的所有元素中找出当前最小值所在的下标
        for j := length - 1; j > i; j-- {
            if values[j] < values[min] {
                min = j
            }
        }
        //fmt.Printf("i:%d min:%d\n", i, min)

        // 把每次找出来的最小值与之前的最小值做交换
        values[i], values[min] = values[min], values[i]

        //fmt.Println(values)
    }
}