Python教程

十大排序算法的实现-python&golang

本文主要是介绍十大排序算法的实现-python&golang,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

1.冒泡

思路:每一轮排序,每次循环从头开始比较,但尾部根据i变化,length-i-1或者length-i,相当于每次当前尾部位置固定,每次循环选出当前轮最大的放后面,大的往数组尾部移动,小的往前挪
时空分析: 时间/空间 O(n^2)
稳定性:稳定
内排排序: 内排序

python

# 1.冒泡排序-稳定-内排序-时间复杂度O(n^2), 空间复杂度O(n^2)
def bubbleSort(nums: [int]) -> [int]:
    
    for i in range(len(nums)):
        for j in range(1, len(nums)-i):
            if nums[j-1] > nums[j]:
                nums[j-1], nums[j] = nums[j], nums[j-1]
    return nums

golang

// 1.bubble
func bubbleSort(nums []int) []int {
	
	for i := range nums {
		for j:=1;j<len(nums)-i;j++ {
			if nums[j-1] > nums[j] {
				nums[j-1], nums[j] = nums[j], nums[j-1]
			}
		}
	}
	return nums
}

2.选择

思路:每一轮排序,每次循环从头开始比较,不断把小的往前面推,大的被选择交换到后面,每一轮选出当轮最小的,相当于i固定位置,但交换后的值肯定是当轮最小的
时空分析: 时间/空间 O(n^2)
稳定性:数组实现不稳定,链表稳定
内排排序: 内排序

python

# 2.选择排序-不稳定-内排序-时空O(n^2)
def selectSort(nums: [int]) -> [int]:
    length = len(nums)
    for i in range(length):
        for j in range(i, length):
            if nums[i] > nums[j]:
                nums[i], nums[j] = nums[j], nums[i]
    return nums

golang

// 2.select
func selectSort(nums []int) []int {
	length := len(nums)
	for i := range nums {
		for j:=i;j<length;j++ {
			if nums[i] > nums[j] {
				nums[i], nums[j] = nums[j], nums[i]
			}
		}
	}
	return nums
}

3.插入

思路:每一轮排序,会把当前遍历的元素之前的那些元素排序,使得每一轮循环结束,当前元素及其前面元素都排好序,后面再循环,相当于把某元素插入到合适位置
e.g. nums = [1,2,3,2,6,4,7], 当前遍历的元素为下标3的元素2,后面的6/4/7不动,该元素2不断与其前面排好序的元素比较,直到找到下标2合适的插入位置,
即下标1/2的元素2/3之间,所以此轮循环比较后,nums=[1,2,2,3,6,4,7],后面遍历重复此过程。
时空分析: 时间/空间 O(n^2)
稳定性:数组稳定
内排排序: 内排序

python

# 3.插入排序-稳定-内排序-时空O(n^2)
def insertSort(nums: [int]) -> [int]:
    length = len(nums)
    for i in range(1, length):
        while i > 0 and nums[i-1] > nums[i]:
            nums[i-1], nums[i] = nums[i], nums[i-1]
            i -= 1
    return nums

golang

// 3.insert
func insertSort(nums []int) []int {
	length := len(nums)
	for i:=0;i<length;i++ {
		for j:=i;j>0;j-- {
			if nums[j-1] > nums[j] {
				nums[j-1], nums[j] = nums[j], nums[j-1]
			}
		}
	}
	return nums
}

4.希尔-插入排序升级版

思路:定义增量序列gap,通常取[1,2,4,...2^(k-1)], 循环增量序列,从大的增量开始递减,每个增量序列使用时,遍历从gap到length的元素,每次比较交换i-gapi位置的元素, 比较后i = i-gap,直到gap=0为止
时空分析: 时间/空间 O(n^2), 与增量序列有关,[1,2,4,8...]最坏O(n^2), [1,3,5,7,9...]最坏O(n^1.5), [1,5,19,41,109,...] -> O(n^1.3),详情查阅《数据结构与算法分析》
稳定性:不稳定
内排排序: 内排序

python

# 4.希尔排序-不稳定-内排序-时空O(n^2)
def shellSort(nums: [int]) -> [int]:
    length = len(nums)
    gap = length >> 1
    while gap:
        for i in range(gap, length):
            while i-gap >= 0 and nums[i-gap] > nums[i]:
                nums[i-gap], nums[i] = nums[i], nums[i-gap]
                i -= gap
        gap >>= 1
    return nums

golang

// 4.shell
func shellSort(nums []int) []int {
	length := len(nums)
	gap := length >> 1
	for gap > 0 {
		for i:=gap;i<length;i++ {
			j := i
			for j-gap >= 0 && nums[j-gap] > nums[j] {
				nums[j-gap], nums[j] = nums[j], nums[j-gap]
				j -= gap
			}
		}
		gap >>= 1
	}
	return nums
}
这篇关于十大排序算法的实现-python&golang的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!