常用排序算法比较与分析 - 图文

52. 53. 54. 55. 56. 57. 58. 59. 60.

# 2. 调整堆，使其继续满足大顶堆的性质，注意实时修改堆中序列的长度 while i > 0:

temp = data_list[i-1] data_list[i-1] = data_list[0] data_list[0] = temp #堆中序列长度减1 i = i-1 #调整大顶堆

adjust_max_heap(data_list, i, 0)

2.3交换排序

核心思想：顾名思义，就是一组待排序的数据元素中，按照位置的先后顺序相互比较各自的关键码，如果是逆序，则交换这两个数据元素，直到该序列数据元素有序为止。

2.3.1 冒泡排序

核心思想：对于待排序的一组数据元素，把每个数据元素看作有重量的气泡，按照轻气泡不能在重气泡之下的原则，将未排好顺序的全部元素自上而下的对相邻两个元素依次进行比较和调整，让较重的元素往下沉，较轻的往上冒。

根据基本思想，只有在两个元素的顺序与排序要求相反时才将调换它们的位置，否则保持不变，所以冒泡排序时稳定的。时间复杂度为平方阶O(n2)，空间复杂度为O(l)。

Python源代码：

1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12.

#-------------------------冒泡排序-------------------------------- def bubble_sort(data_list): length = len(data_list)

#序列长度为length，需要执行length-1轮交换 for x in range(1,length):

#对于每一轮交换，都将序列当中的左右元素进行比较

#每轮交换当中，由于序列最后的元素一定是最大的，因此每轮循环到序列未排序的位置即可 for i in range(0,length-x): if data_list[i] > data_list[i+1]: temp = data_list[i] data_list[i] = data_list[i+1] data_list[i+1] = temp

2.3.2 快速排序

快速排序是对冒泡排序本质上的改进。

核心思想：是一个就地排序，分而治之，大规模递归的算法。即：通过一趟扫描后确保基准点的这个数据元素的左边元素都比它小、右边元素都比它大，接着又以递归方法处理左右两边的元素，直到基准点的左右只有一个元素为止。

快速排序时一个不稳定的算法，其最坏值的时间复杂度为平方阶O(n2)，空间复杂度为O(log2n)。

Python源代码：

1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29.

#-------------------------快速排序--------------------------------

#data_list：待排序的序列；start排序的开始index,end序列末尾的index #对于长度为length的序列：start = 0;end = length-1 def quick_sort(data_list,start,end): if start < end:

i , j , pivot = start, end, data_list[start] while i < j:

#从右开始向左寻找第一个小于pivot的值 while (i < j) and (data_list[j] >= pivot): j = j-1

#将小于pivot的值移到左边 if (i < j):

data_list[i] = data_list[j] i = i+1

#从左开始向右寻找第一个大于pivot的值 while (i < j) and (data_list[i] < pivot): i = i+1

#将大于pivot的值移到右边 if (i < j):

data_list[j] = data_list[i] j = j-1

#循环结束后，说明 i=j，此时左边的值全都小于pivot,右边的值全都大于pivot #pivot的位置移动正确，那么此时只需对左右两侧的序列调用此函数进一步排序即可 #递归调用函数：依次对左侧序列：从0 ~ i-1//右侧序列：从i+1 ~ end data_list[i] = pivot #左侧序列继续排序

quick_sort(data_list,start,i-1) #右侧序列继续排序

quick_sort(data_list,i+1,end)

2.4归并排序

核心思想：把数据序列递归地分成短序列，即把1分成2、2分成4、依次分解，当分解到只有1个一组的时候排序这些分组，然后依次合并回原来的序列，不断合并直到原序列全部排好顺序。

合并过程中可以确保两个相等的当前元素中，把处在前面的元素保存在结果序列的前面，因此归并排序是稳定的，其时间复杂度为O(nlog2n)，空间复杂度为O(n)。

Python源代码：

1. 2. 3.

#-------------------------归并排序-------------------------------- #这是合并的函数

# 将序列data_list[first...mid]与序列data_list[mid+1...last]进行合并

4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. 32. 33. 34. 35. 36. 37. 38. 39. 40. 41. 42. 43. 44. 45.

def mergearray(data_list,first,mid,last,temp): #对i,j,k分别进行赋值 i,j,k = first,mid+1,0

#当左右两边都有数时进行比较，取较小的数 while (i <= mid) and (j <= last): if data_list[i] <= data_list[j]: temp[k] = data_list[i] i = i+1 k = k+1 else:

temp[k] = data_list[j] j = j+1 k = k+1

#如果左边序列还有数 while (i <= mid): temp[k] = data_list[i] i = i+1 k = k+1

#如果右边序列还有数 while (j <= last): temp[k] = data_list[j] j = j+1 k = k+1

#将temp当中该段有序元素赋值给data_list待排序列使之部分有序 for x in range(0,k):

data_list[first+x] = temp[x] # 这是分组的函数

def merge_sort(data_list,first,last,temp): if first < last:

mid = (int)((first + last) / 2) #使左边序列有序

merge_sort(data_list,first,mid,temp) #使右边序列有序

merge_sort(data_list,mid+1,last,temp) #将两个有序序列合并

mergearray(data_list,first,mid,last,temp) # 归并排序的函数

def merge_sort_array(data_list): #声明一个长度为len(data_list)的空列表 temp = len(data_list)*[None] #调用归并排序

merge_sort(data_list,0,len(data_list)-1,temp)

2.5 基数排序

核心思想：首先是低位排序，然后收集;其次是高位排序，然后再收集;依次类推，直到最高位。

Python源代码：

1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. 32. 33. 34. 35. 36. 37. 38. 39. 40. 41.

#-------------------------基数排序-------------------------------- #确定排序的次数

#排序的顺序跟序列中最大数的位数相关 def radix_sort_nums(data_list): maxNum = data_list[0] #寻找序列中的最大数 for x in data_list: if maxNum < x: maxNum = x

#确定序列中的最大元素的位数 times = 0

while (maxNum > 0):

maxNum = (int)(maxNum/10) times = times+1 return times

#找到num从低到高第pos位的数据 def get_num_pos(num,pos):

return ((int)(num/(10**(pos-1)))) #基数排序

def radix_sort(data_list):

count = 10*[None] #存放各个桶的数据统计个数 bucket = len(data_list)*[None] #暂时存放排序结果 #从低位到高位依次执行循环

for pos in range(1,radix_sort_nums(data_list)+1): #置空各个桶的数据统计 for x in range(0,10): count[x] = 0

#统计当前该位(个位，十位，百位....)的元素数目 for x in range(0,len(data_list)): #统计各个桶将要装进去的元素个数 j = get_num_pos(int(data_list[x]),pos) count[j] = count[j]+1

#count[i]表示第i个桶的右边界索引 for x in range(1,10):

count[x] = count[x] + count[x-1] #将数据依次装入桶中

for x in range(len(data_list)-1,-1,-1): #求出元素第K位的数字

j = get_num_pos(data_list[x],pos)

#放入对应的桶中，count[j]-1是第j个桶的右边界索引 bucket[count[j]-1] = data_list[x]