golang之快排实现（最傻的和原地排序）

golang之快排实现（最傻的和原地排序）

package sort

/**
* 最傻的QuikSort和基于原地的QuikSort
*
* Author:sxy
 */
func QuickSort(arr []int) {
	quickSort(arr, 0, len(arr)-1)
}

//  基于分治思想，即需要递归，递归退出条件，当start>=end，就退出。
//  递推公式，即每次取一个临界点，小于这个临界点，放左边，大于这个临界点的放数组右边。
//  partition函数每次都会得到一个临界点，基于这个临界点再递归。
func quickSort(arr []int, start, end int) {
	if start >= end {
		return
	}
	pivort := partition(arr, start, end)
	quickSort(arr, start, pivort-1)
	quickSort(arr, pivort+1, end)
}

// 如果不考虑任何空间复杂度，申请两个tmp数组tmp1和tmp2，取最后一个节点，遍历数组如果小于这个节点值放入tmp1, 如果大于这个节点值放到tmp2.
// 之后将tmp1 和最后节点值、tmp2的值都赋给tmp数组。

func partition(arr []int, start, end int) int {
	leftTmp := []int{}
	rightTmp := []int{}

	pivot := arr[end]
	for i := start; i < end; i++ {
		if arr[i] < pivot {
			leftTmp = append(leftTmp, arr[i])
		} else if arr[i] > pivot {
			rightTmp = append(rightTmp, arr[i])
		}
	}

	for i := range leftTmp {
		arr[start] = leftTmp[i]
		start++
	}
	arr[start] = pivot
	tmp := start
	start++

	for i := range rightTmp {
		arr[start] = rightTmp[i]
		start++
	}

	return tmp
}

// 如果想要使用的原地排序算法
// 将arr数组分为已排区间和未排区间，每一次从未排区间中选一个元素，如果比arr[end]小的值插入到未排的区间里面，
// 因为数组的插入需要搬移数据， 所以我们采用交换的方式，将已排区间的最后一个元素和当前小于arr[end]的节点做交换
// 最后我们将arr[end]的值和已排的最后一个元素进行交换。  如此排序成功。

func partition1(arr []int, start, end int) int {

	i := start
	pivot := arr[end]
	for j := start; j < end; j++ {
		if arr[j] < pivot {
			if !(i == j) {
				//  将a[i]和a[j]交换
				arr[i], arr[j] = arr[j], arr[i]
			}
			i++
		}
	}
	arr[i], arr[end] = arr[end], arr[i]
	return i
}