quick.go

package main

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

func quickSort(arr []int) (s []int) {
	l := len(arr)
	if l <= 1 {
		s = arr
		return
	}
	var left, right []int
	pivot := arr[0]

	for i := 1; i < l; i++ {
		if arr[i] <= pivot {
			left = append(left, arr[i])
		} else {
			right = append(right, arr[i])
		}
	}
	left = quickSort(left)
	right = quickSort(right)

	s = append(s, left...)
	s = append(s, pivot)
	s = append(s, right...)
	return
}

func quickSort2(arr []int, left, right int) {
	l := len(arr)
	if l <= 1 {
		return
	}
	if left > right {
		return
	}
	i, j := left, right
	pivot := arr[left]
	for {
		// 循环外不需要用到 j, 所以先判断 j, 让循环 break
		for arr[j] > pivot {
			j--
		}
		for arr[i] <= pivot && i < j {
			i++
		}

		if i >= j {
			break
		}

		arr[i], arr[j] = arr[j], arr[i]

	}
	arr[i], arr[left] = arr[left], arr[i]

	quickSort2(arr, left, i-1)
	quickSort2(arr, i+1, right)
	return
}

func quickSort3(arr []int, left, right int) {
	l := len(arr)
	if l <= 1 {
		return
	}
	if left >= right {
		return
	}
	i, j := left, right
	mid := (right + left) / 2
	pivot := arr[mid]

	for {
		for arr[i] < pivot {
			i++
		}
		for arr[j] > pivot {
			j--
		}
		if i >= j {
			break
		}
		arr[i], arr[j] = arr[j], arr[i]
	}
	quickSort3(arr, left, i-1)
	quickSort3(arr, i+1, right)
	return
}

func quickSort4(arr []int, left, right int) {
	l := len(arr)
	if l <= 1 {
		return
	}

	if left >= right {
		return
	}

	pivot := arr[right]
	i, j := left-1, left
	for ; j <= right; j++ {
		if arr[j] <= pivot {
			i++
			arr[i], arr[j] = arr[j], arr[i]
		}
	}
	quickSort4(arr, left, i-1)
	quickSort4(arr, i+1, right)
}

func main() {
	slice := generateSlice(10)
	fmt.Println("Unsorted", slice)
	slice = quickSort(slice)
	fmt.Println("Sorted", slice)

	fmt.Println("-----------------------------")

	slice2 := generateSlice(10)
	fmt.Println("Unsorted", slice2)
	quickSort3(slice2, 0, len(slice2)-1)
	fmt.Println("Sorted", slice2)

	fmt.Println("-----------------------------")

	slice3 := generateSlice(10)
	fmt.Println("Unsorted", slice3)
	quickSort4(slice3, 0, len(slice3)-1)
	fmt.Println("Sorted", slice3)

}

func generateSlice(size int) []int {
	slice := make([]int, size, size)
	rand.Seed(time.Now().UnixNano())
	for i := 0; i < size; i++ {
		slice[i] = rand.Intn(99999) - rand.Intn(99999)
	}
	return slice
}