数据结构与算法（Python版） 源代码 （周元哲 版）第10章 排序

目录

第10章排序....................................................................2

10.2插入排序...............................................................2

10.2.1直接插入排序......................................................2

10.2.2折半插入排序.....................................................2

10.2.3希尔排序..........................................................3

10.3交换排序...............................................................3

10.3.1冒泡排序..........................................................3

10.3.2快速排序.........................................................4

10.4选择排序...............................................................4

10.4.1简单选择排序.....................................................4

10.4.2堆排序............................................................5

10.5归并排序...............................................................6

10.8实例....................................................................7

10.8.1插入一值保持有序不变.............................................7

10.8.2最小的K个数.....................................................8

第10章排序

10.2插入排序

插入排序将无序子序列中的一个或几个记录插入到有序序列中，从而减少无序子序列，

增加记录的有序子序列的长度。插入排序又可细分为直接插入排序、折半插入排序和希尔排

序。

10.2.1直接插入排序

【直接插入排序代码】

definsert_sort(alist):

foriinrange(l,len(alist)):#外循环n・l

forjinrange(i,0,-l)：#内循环

ifalist[j]<alistfj-l]:

alist[j],alist[j-l]=alist[j-l],alist[j]#元素交换

Ii=[59,l2,77,64,72,69,46,89,31,9]

print('before:\li)

insert_sort(li)

print(*after:'Ji)

【程序运行结果】

before:[59,12,77,64,72,69,46,89,31,9]

after:[9,12,31,46,59,64,69,72,77,89]

10.2.2折半插入排序

【折半插入排序代码】

defbinary_sort(a):

foriinrange(0,len(a)):

index=a[i]

low=0

hight=i-1

whilelow<=hight:

mid=(low+hight)//2

ifindex>a[mid]:

low=mid+1

else:

hight=mid-1

forjinrange(i,low,-1):

a[j]=a[j-1]

a[low]=index

li=[59,l2,77,64,72,69,46,89,31,9]

print('before:\li)

binary_sort(li)

print('after:\li)

程序运行结果如下：

before:[59,12,77,64,72,69,46,89,31,9]

after:[9,12,31,46,59,64,69,72,77,89]

10.2.3希尔排序

【希尔排序代码】

defshell_sort(alist):

n=len(alist)

gap=n//2

whilegap>0:

foriinrange(gap,n):

j=i

whilej>=gapandalist|j-gap]>alist[jj:

alist[j-gap],alist[j]=alist[j],alistU-gap]

j-=gap

gap=gap//2

li=[l1,9,84,32,92,26,58,91,35,27,46,28,75,29,37,12]

print(*before:*,li)

shell_sort(li)

print('after:\li)

【程序运行结果】

before:[11,9,84,32,92,26,58,91,35,27,46,28,75,29,37,12]

after:[9,11,12,26,27,28,29,32,35,37,46,58,75,84,91,92J

10.3交换排序

10.3.1冒泡排序

【冒泡排序代码】

defbubble_sort(alist):

forjinrange(len(alist)-1,0,-1):#外循环

foriinrange(j):#内循环

ifalist[i]>alist[i+l]:

alist[i],alist[i+l]=alist[i+l],alist[i]

li=[54,26,93,l7,77,31,44,55,20]

printCbefore:\li)

bubble_sort(li)

print('after:*,li)

【程序运行结果】

before:[54,26,93,17,77,31,44,55,20]

after:[17,20,26,31,44,54,55,77,93]

10.3.2快速排序

【快速排序代码】

defquick_sort(alist,start,end):

ifstart>=end:

return

mid=alist[startj

low=start

high=end

whilelow<high:

whilelow<highandalist[high]>=mid:

high-=1

alist[low]=alist[high]

whilelow<highandalist[low]<mid:

low+=1

alist[high]=alist[low]

alist[low]=mid

quick_sort(alist,start,low-l)

quick_sort(alist,low+l,end)

li=[48,36,61,99,81,14,30]

printCbefore/Ji)

quick_sort(li,0,len(li)-1)

printCafter:',li)

【程序运行结果】

before:148,36,61,99,81,14,30]

after:[14,30,36,48,61,81,99]

10.4选择排序

10.4.1简单选择排序

【简单选择排序代码】

defselection_sort(alist):

n=len(alist)

foriinrange(0,n):

min=i#将当前下标定义为最小值下标

forjinrange(i+l,n):

ifalist[j]<alistfmin]:#如果有小于当前最小值的关键字

min=j#将此关键字的下标赋值给min_index

alist[i],alist[min]=alist[min],alist[i]

li=[5,2,l,8,3,4,6,7]

print('before:',li)

selection_sort(li)

printCafter:',!!)

【运行结果】

before:[5,2,1,8,3,4,6,7]

after:[1,2,3,4,5,6,7,8]

10.4.2堆排序

【堆排序完整代码如下所示】

fromcollectionsimportdeque

defswap_param(L,i,j):#把堆顶元素和堆末尾的元素交换

L[i],LU]=LU],L[i]

returnL

defheap_adjust(L,start,end):#调整为大根堆

temp=L[start]

i=start

j=2*i

whilej<=end:#代表在调整完整棵树树之前一直进行循环

if(j<end)and(L[j]<L[j+1]):#保证j取到较大子树的坐标

j+=I

iftemp<L|j]:#如果子树的根节点小于子树的值，就把根节点和较大的子树的值进行交换

L[i]=Uj]

i=j

j=2*i

else:

break

L[i]=temp

defheap_sort(L):

LJength=len(L)-1#引入一个辅助空间

first_sort_count=L_length//2

foriinrange(first_sort_count):#把序列调整为一个大根堆

heap_adjust(L,first_sort_count-i,L_length)

foriinrange(L_length-1):

L=swap_param(L,1,L_length-i)

#交换第一个节点和最后一个节点的值(引入的一个辅助空间，序列长度减1)

heap_adjust(L,1,LJength-i-1)

return[L[i]foriinrange(1,len(L))]

defmain():

L=deque([50,16,30,10,60,90,2,80,70])

L.appendleft(O)

print(heap_sort(L))

if_name_=='_main_

main()

程序运行结果为：

[2,10,16,30,50,60,70,80,90]

方法二：使用heapq模块实现，heapq模块见附录C

importheapq

defheapsort(iterable):

h=[]

forvalueiniterable:

heapq.heappush(h,value)

return[heapq.heappop(h)foriinrange(len(h))]

if_name_=='_main—

li=[l,3,5,7,9,2,4,6,8,0]

print(nbefore:"Ji)

h=heapsort(li)

print("after:",h)

【程序运行结果】：

before:[1,3,5,7,9,2,4,6,8,0]

after:[0,1,2,3,4,5,6,7,8,9]

10,5归并排序

【归并排序法代码】

defmerge(left,right):

i,j=0,0

result=[]

whilei<len(Ieft)andj<len(right):

ifleft[i]<right[j]:

result.append(left[i])

i+=l

else:

result.append(right[j])

j+=l

result.extend(left[i:])

result.extend(right[j:])

returnresult

defmerge_sort(alist):

iflen(alist)<=l:

returnalist

mid=len(alist)//2

left=merge_sort(alist[:mid])

right=merge_sort(alist[mid:])

returnmerge(left,right)

defmain():

li=[9,4,6,2,l,7]

print("befroe:n,li)

print(nafter:n,merge_sort(li))

if_name_=='_main_

main()

【程序运行结果】

befroe:[9,4,6,2,1,7]

after:[1,2,4,6,7,9]

10.8实例

10.8.1插入一值保持有序不变

【例10-1】实现有序序列中插入一个值，保持序列有序不变。

【解析】：假设有序序列为(1,2,7,8,49),插入6,输出(1,2,6,7,8,49)升序。

步骤1：确定插入的位置。组(1,2,7,8,49)中找到6所要插入的位置，其位置为2

和7之间的位置，6要插入的位置是元素7所在的位置。

步骤2：依次移位，腾出空位。直接将6插入到7所在的位置，7将被覆盖，因此需要

给6腾出位置。从序列末尾开始，元素依次往其后的位置移动，49往后移动，8移到49原

先的位置上，7移到8原先的位置上。

步骤3：插入6。将数据6插入原先7所在位置。

根据例10-1的提示，针对给定序列a[0…n-1],直接插入排序算法如下所示：

步骤1：初始时，a[0]自成1个有序区，无序区为a[l..n-l]；

步骤2：第2个元素与列表中左侧的第1个元素比较，如果则交换位置,

结果是左侧的两个元素排好序。

步骤3：以此类推，将a[i]并入前面排好序的子序列a[0…i-l]中形成a[0…i]的有序区间;

步骤4：进行n-1轮比较和交换后，列表中的所有元素均按递增顺序排序

10.8.2最小的K个数

【例10。】输入n个整数,找出其中最小的K