Python四种基础排序算法实现与对比

插入排序：逐步构建有序序列

插入排序的核心思想是将未排序的元素逐个插入到已排序序列的正确位置。在Python实现中，算法从第二个元素开始遍历，将当前元素（Key）与前面的元素逐一比较。若前一个元素大于Key，则将其后移，直到找到合适位置或遍历结束。此过程确保了每次循环后，索引i之前的元素均保持有序。

#直接插入排序
def insert_sort(list):
  for i in range(len(list)):
    Key = list [i]      #待插入元素
      j = i - 1
      while(Key < list[j] and j >= 0):
        list[j+1] = list[j]  #后移元素
        list[j] = Key
        j=j-1
  return list

冒泡排序：相邻元素两两交换

冒泡排序通过重复遍历列表，比较相邻元素并交换顺序错误的元素，使较大的元素逐渐“冒泡”至序列末尾。实现时，外层循环控制遍历轮数，内层循环负责相邻元素的比较与交换。经过len(list)-1轮遍历后，整个序列即完成升序排列。

#冒泡排序  
def bubble_sort(list):
  for i in range(1, len(list)):
    for j in range(len(list)-i):
      if list[j] > list [j+1]:
        list[j+1],list[j] =list[j],list[j+1]
  return list

快速排序：分治策略与基准元素

快速排序采用分治法，通过选择一个基准元素（key）将序列分为两部分：小于基准的元素位于左侧，大于基准的位于右侧。核心函数position_key负责确定基准元素的最终位置，并通过递归调用quick_sort对左右子序列分别排序。该方法在平均情况下具有较好的时间复杂度。

#快速排序
def position_key(list, low, high):
  i = low
  j = high
  key = list[low]
  while(i < j):
    while(i < j and list[j] >= key):  #从右向左，寻找第一个小于基准元素的数据索引。 注意：i<y 的判断，内循环更新j
      j -= 1
    if i < j :
      list[i] = list[j]
    while(i<j and list[i] <= key):   #从左向右，寻找地一个大于基准元素的数据索引。i<y同上
      i += 1
    if i < j:
      list[j] = list[i]
  list[j] = key     # 基准元素位置 
  return j
def quick_sort(list, low, high):
  if low < high:
    position = position_key(list, low, high) #将数据分成前后两个子序列（前边序列值均小于后边序列）
    quick_sort(list, low, position-1)    #将前面的序列快速排序
    quick_sort(list, position+1, high)    #将后面的序列快速排序
  return list

选择排序：寻找最小值交换

选择排序每次从未排序部分中选出最小（或最大）的元素，将其放到已排序部分的末尾。实现时，外层循环确定当前要放置的位置i，内层循环从i开始遍历剩余元素，寻找最小值的索引j。若发现更小的元素，则与位置i的元素交换。此过程重复至序列结束。

#选择排序
def select_sort(list):
  for i in range(len(list)):
    for j in range(i, len(list)):
      if list[i] > list[j]:
        list[i], list[j] = list[j], list[i]
  return list

算法验证与工具推荐

为验证上述算法的正确性，使用包含22个整数的序列进行测试。测试代码依次调用四种排序函数，并打印原始序列及各算法的排序结果。实验表明，四种算法均能正确将序列按升序排列，且最终输出结果一致。

list = [23, 232, 11, 89,121, 64, 34, 12, 23423, 2312, 167, 768, 932, 346, 32789, 335, 2, 1145, 34, 56, 99, 111]
print '原始序列  ：', list
print '直接插入排序：', insert_sort(list)
print '冒泡排序  ：', bubble_sort(list)
print '快速排序  ：', quick_sort(list, 0, len(list)-1)
print '选择排序  ：', select_sort(list)

对于希望直观理解排序过程的用户，推荐使用在线动画演示工具（如tools.jb51.net），通过动态可视化辅助学习算法的执行细节。

以上就是Python实现的插入排序，冒泡排序，快速排序，选择排序算法示例的详细内容，更多关于Python排序算法的资料请关注本站其它相关文章！