leecode中的排序，冒泡+选择+插入+希尔排序，基础到真题56,75,215,347,451---(一)

vlambda
2022-05-18

leecode中的排序，冒泡+选择+插入+希尔排序，基础到真题56,75,215,347,451---(一)

今天是5月17日，目标是吃透十大排序算法，此篇为所作笔记。介绍顺序为：1）十大排序算法原理及python实现，2）leecode真题解析。

十大算法大的性质表如下：

算法术语：

稳定排序：即如果a在b的前面，且a==b,排完后a仍在b之前
非稳定排序：与稳定排序相反，排完后a可能不在b之前
原地排序：排序过程中不申请多余的内存空间，只利用原有的空间对待排数据进行比较和交换排序
非原地排序：需要额外的数组来辅助排序
时间复杂度：算法所需消耗的时间(简单的说就是量级，详见数据结构一书)
空间复杂度：所需内存大小

按表中的排序方法顺序予以解释如下：

冒泡排序：

实质：每一次循环都在查找对应空间的最大值，并置于列尾

操作：把第一个元素与第二个相比较，如果第一个比第二个大，则交换位置，继续比较第二个与第三个元素，如果第二个比第三个大，则交换他们的位置，一趟下来，排在最右的元素就会是最大的数。除去最右的元素，对剩余的元素做同样的工作，如此重复，直至排序完成。优化：若有一轮无需变换位置，则表明数组已经有序，排序提前结束

原理动图：

leecode中的排序，冒泡+选择+插入+希尔排序，基础到真题56,75,215,347,451---(一)

代码实现：

def bubbleSort(nums:list)->list: if not nums or len(nums)<2: return nums
 for i in range(len(nums)): # 数组是否已经有序的标志，若有序，提前结束 swapped = False        #最后i个数值已经拍好序，不用再重排 for j in range(len(nums)-i-1): if nums[j]> nums[j+1]: nums[j],nums[j+1] = nums[j+1],nums[j] swapped = True
 if not swapped: break#优化后的代码def bubbleSort1(nums:list)->list: if not nums or len(nums)<2: return nums
 swapped = True while(swapped):        swapped = False         #没有任何相邻对需要调换位置，证明已经有序循环直接结束 for i in range(len(nums)-1): if nums[i+1] < nums[i]: nums[i+1],nums[i] = nums[i],nums[i+1] swapped = True
nums = [64, 34, 25, 12,12, 22, 11, 90]bubbleSort1(nums)print(nums)

选择排序：

原理：首先，找到数组中最小的那个数，将之与第一个数调换位置，然后对从第2个开始的剩下元素中寻找最小数，并与第2个数调换位置，如此往复，直至整个数组排序结束，称之为冒泡排序。

原理动画为：

leecode中的排序，冒泡+选择+插入+希尔排序，基础到真题56,75,215,347,451---(一)

代码实现：

def selectSort(nums:list)->list: if not nums or len(nums)<2: return nums  for i in range(len(nums)): min= nums[i] swapped = False for j in range(i+1,len(nums)): if nums[j]<min: min,k = nums[j],j swapped = True        #determine if we need to swap the position and value if swapped : nums[i],nums[k] = nums[k],nums[i]

插入排序：

排序原理：对待排序列，从第2个元素开始，与之前的元素相比较，当插入元素小于比较对象元素时，继续往前比较，直至不小于比较对象时，此时将此元素插入该次比较对象之后。重复这个过程，直至将最后一个元素作为插入对象完成插入操作。(从此描述可以看出，当对第N个元素作为插入元素时，前N-1个元素实质上已经排好序，此时可以采用二分查找算法快速找到插入位置，从而实现优化,实现代码给出了两种解)

原理动画：

插入排序代码：

def insertSort(nums:list)->list: if not nums or len(nums)<2: return nums
 for i in range(1,len(nums)): swap = False for j in range(i-1,-1,-1):            #here the code block can be rewritten in a bi-search way if nums[j] > nums[i]: j = j-1 swap =True else: break        #if there is the need to swap the list if swap : temp = nums[i] nums[j+2:i+1] = nums[j+1:i]            nums[j+1] = temp

希尔排序：

排序原理：固定间隔的几个元素之间排序，然后再缩小这个间隔，这样到最后数列就成为基本有序数列，优化版本的选择排序

原理图：

代码如下：

def shellSort(nums:list)->list: if not nums or len(nums)<2: return nums
 n = len(nums) #there exist some other step definition dist = n//2 while dist > 0: #start from the distance point for i in range(dist, len(nums)): j = i #compare the unit with the unit before.if less than before ,exchange while(j-dist >=0 and nums[j] < nums[j-dist]): nums[j],nums[j-dist] = nums[j-dist],nums[j] j -= dist dist = dist // 2
 return nums