quick_sort

  • 2022-12-14
  • 浏览 (552)

quick_sort.go 源码

package sort

//快速排序

func QuickSort(data []int) {
	quickSortHelper(data, 0, len(data)-1)
}

func quickSortHelper(data []int, lo, hi int) {
	if lo < hi {
		mid := partition(data, lo, hi)
		quickSortHelper(data, lo, mid-1)
		quickSortHelper(data, mid+1, hi)
	}
}

func partition(data []int, lo, hi int) int {
	pivot, i, j := data[hi], lo, lo
	for j < hi {
		if data[j] < pivot {
			data[j], data[i] = data[i], data[j]
			i++
		}
		j++
	}
	data[i], data[hi] = data[hi], data[i]
	return i
}

// 快速排序-迭代实现
func QuickSortIteration(data []int) {
	stack := []int{0, len(data) - 1}

	for len(stack) > 1 {
		lo, hi := stack[len(stack)-2], stack[len(stack)-1]
		stack = stack[:len(stack)-2]
		if lo < hi {
			mid := partition(data, lo, hi)
			stack = append(stack, lo, mid-1)
			stack = append(stack, mid+1, hi)
		}
	}
}

你可能感兴趣的文章

bubbleSort

bubbleSort_test

bucket_sort

0  赞