關(guān)于三種簡(jiǎn)單排序的操作

一、關(guān)于插入排序的一些想法與實(shí)現(xiàn)，插入排序的原理是在序列前增加一個(gè)哨兵，通過哨兵的值與前面比較，如果需要改變的話直接覆蓋掉與哨兵值的位置，最后可以將哨兵填充到新的空缺位置，按照排序的定義意思就是直接在新的列表前直接補(bǔ)一個(gè)索引為0的位置填充一個(gè)零
nums=[1,9,8,5,6,7,4,3,2]
nums=[0]+nums
length=len(nums)
for i in range(2,length):
nums[0]=nums[i]
j=i-1
if nums[j]>nums[0]:
while nums[j]>nums[0]:
nums[j+1]=nums[j]
j-=1
nums[j+1]=nums[0]
nums.pop(0)
print(nums)

這是基礎(chǔ)的代碼，但是為什么一定要在列表前面添加一個(gè)索引為零的哨兵呢，我的想法是完全可以用一個(gè)額外的值來代替這個(gè)在列表里的操作啊，這樣省著前面填充，后面又移除。
nums=[1,9,8,5,6,7,4,3,2]
length=len(nums)

for i in range(1,length):
sentry=nums[i]
j=i-1
if nums[j]>sentry:
while nums[j]>sentry:
nums[j+1]=nums[j]
j-=1
nums[j+1]=sentry
print(nums)

這樣下來也可以實(shí)現(xiàn)，但同時(shí)也有一個(gè)小問題就是哨兵在的時(shí)候一般比到哨兵就截止了，這種前面×××，如果最大值是1的話，容易直接減到負(fù)索引超界，所以在第二個(gè)循環(huán)中加了個(gè)判斷條件就是減到負(fù)索引就可以停止了，這樣可以處理最大值在第一的情況。
nums=[10,9,8,5,6,7,4,3,2]
length=len(nums)

for i in range(1,length):
sentry=nums[i]
j=i-1
if nums[j]>sentry:
while nums[j]>sentry:
nums[j+1]=nums[j]
j-=1
if j==-1:
break
nums[j+1]=sentry
print(nums)

如果繼續(xù)優(yōu)化的話，就是在進(jìn)入有序區(qū)之后可以進(jìn)行折半查找，會(huì)少許的提升效率。
二、選擇排序
選擇排序是一種比冒泡排序稍微優(yōu)化一點(diǎn)的算法，本質(zhì)上是在每一趟選出一個(gè)最值，然后直接與隊(duì)列的頭或者尾交換，最后得出排列順序的一種排序算法，與冒泡的優(yōu)化是一趟下來交換的次數(shù)小。但是與此同時(shí)不能提前結(jié)束，所以從效率上來講是差不多的。
lst=[1,9,8,5,6,7,4,3,2]
length=len (lst)
for i in range (length):
maxer=i
for j in range(i+1,length):
if lst[maxer]<lst[j]:
maxer=j

lst[i],lst[maxer]=lst[maxer],lst[i]

print(lst)

這個(gè)是簡(jiǎn)單的快速排序，在這個(gè)排序中的缺點(diǎn)是沒有提前結(jié)束，我們想能不能在一趟中同時(shí)把最大值與最小值選出來
lst=[1,9,8,5,6,7,4,3,2]
length=len (lst)
for i in range (length//2):
maxer=i
miner=-i-1
for j in range(i+1,length-i):
if lst[maxer]<lst[j]:
maxer=j
if lst[-j-1]<lst[miner]:
miner=-j-1
if lst[miner]==lst[maxer]:
break
if maxer !=i:
lst[i],lst[maxer]=lst[maxer],lst[i]
if miner==i or miner==i-length:
miner=maxer-length
if miner !=-i-1:
lst[-i-1],lst[miner]=lst[miner],lst[-i-1]
print(lst)

三、冒泡排序
nums=[1,2,3,4,5,6,7,8,9]
#nums=[1,9,8,5,6,7,4,3,2]
length=len(nums)
count=0
scount=0
for i in range(9):
count+=1
flag=False
for j in range(8-i):
if nums[j]>nums[j+1]:
tmp=nums[j]
nums[j]=nums[j+1]
nums[j+1]=tmp
scount+=1
flag=True
if not flag:
#if flag==False:
break
print(nums,count,scount)