快速排序

def quick_sort(lyst):
    quick_sort_helper(lyst, 0, len(lyst) - 1)


def partition(lyst, left, right):
    """
    找到基准点并与项目中最后一个交换
    """

    def swap(lyst, i, j):
        """交换项目中 i 和 j的位置"""
        #  可以理解为 lyst[i], lyst[j] = lyst[j], lyst[i]
        temp = lyst[i]
        lyst[i] = lyst[j]
        lyst[j] = temp
		#   找到基准点并与最后一项交换
    middle = (left + right) // 2
    pivot = lyst[middle]
    lyst[middle], lyst[right] = lyst[right], lyst[middle]
    #  将边界点设置为第一个位置
    boundary = left
    #  将项移动到基准点左侧
    for index in range(left, right):
        if lyst[index] < pivot:
            swap(lyst, index, boundary)
            boundary += 1
    #  交换基准点和边界项目
    swap(lyst, right, boundary)
    return boundary


def quick_sort_helper(lyst, left, right):
    """用于隐藏子列表重点的额外参数
    :param lyst:
    :param left:
    :param right:
    :return:
    """
    if left < right:
        pivot_location = partition(lyst, left, right)
        quick_sort_helper(lyst, left, pivot_location - 1)
        quick_sort_helper(lyst, pivot_location + 1, right)


def quick_sort_main(size=20, sort=quick_sort):
    import random
    lyst = []
    for count in range(size):
        lyst.append(random.randint(1, size + 1))
    print(lyst)
    print(f"排序前lyst内存地址：{id(lyst)}\n")
    sort(lyst)
    print(lyst)
    print(f"排序后lyst内存地址：{id(lyst)}\n")


if __name__ == '__main__':
    quick_sort_main()

package main

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

func partition(lyst []int, left int, right int) int {

	swap := func(lyst []int, i int, j int) {

		temp := lyst[i]
		lyst[i] = lyst[j]
		lyst[j] = temp
	}
	middle := (left + right) / 2
	pivot := lyst[middle]
	lyst[middle], lyst[right] = lyst[right], lyst[middle]
	boundary := left
	for i := left; i < right; i ++{
		if lyst[i] < pivot {
			swap(lyst, i, boundary)
			boundary += 1
		}
	}
	swap(lyst, right, boundary)
	return boundary
}

func quickSortHelper(lyst []int, left int, right int) {
	if left < right {
		pivotLocation := partition(lyst, left, right)
		quickSortHelper(lyst, left, pivotLocation-1)
		quickSortHelper(lyst, pivotLocation+1, right)
	}
}

func quickSort(lyst []int) {
	quickSortHelper(lyst, 0, len(lyst)-1)
}

func main() {
	//生成若干个不重复的随机数
	//生成count个[start,end)结束的不重复的随机数
	generateRandomNumber := func(start int, end int, count int) []int {
		//范围检查
		if end < start || (end-start) < count {
			return nil
		}

		//存放结果的slice
		nums := make([]int, 0)
		//随机数生成器，加入时间戳保证每次生成的随机数不一样
		r := rand.New(rand.NewSource(time.Now().UnixNano()))
		for len(nums) < count {
			//生成随机数
			num := r.Intn((end - start)) + start

			//查重
			exist := false
			for _, v := range nums {
				if v == num {
					exist = true
					break
				}
			}

			if !exist {
				nums = append(nums, num)
			}
		}

		return nums
	}

	nums := generateRandomNumber(1, 100, 40)
	fmt.Println("排序前：",nums)
	quickSort(nums)
	fmt.Println("排序后：",nums)
}