当前位置 主页 > 网站技术 > 代码类 > 最大化 缩小

    python常用排序算法的实现代码

    栏目:代码类 时间:2019-11-08 21:04

    这篇文章主要介绍了python常用排序算法的实现代码,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下

    排序是计算机语言需要实现的基本算法之一,有序的数据结构会带来效率上的极大提升。

    1.插入排序

    插入排序默认当前被插入的序列是有序的,新元素插入到应该插入的位置,使得新序列仍然有序。

    def insertion_sort(old_list):
      n=len(old_list)
      k=0
      for i in range(1,n):
        temp=old_list[i]
        j=i
        while j>0 and temp<old_list[j-1]:
          old_list[j]=old_list[j-1]
          j=j-1
        old_list[j]=temp
      return old_list

    2.冒泡排序

    冒泡排序的原理是对序列进行遍历,遍历过程中如果发现相邻两个元素,左边的元素大于右边,则进行交换,一次遍历之后最大的元素被移动到对尾,然后进行第二次遍历,直到队列有序。

    def bubble_sort(old_list):
      n=len(old_list)
      for i in range(n-1):
        for j in range(n-1-i):
          if old_list[j]>old_list[j+1]:
            old_list[j],old_list[j+1]=old_list[j+1],old_list[j]
      return old_list

    3.快速排序

    快速排序的实现方法是设置两个游标,一个从前往后,一个从后往前,如果左侧游标所指数据大于右侧,两数据进行交换,直到两个游标指向同一数据,则第一趟遍历结束。结束时游标所在数据,左侧都比其小,右侧都比其大。

    接下来对游标前后的两个序列进行递归操作。

    def quick_sort(list,low,high):
      i=low
      j=high  
      if i >= j:
        return list
      key=list[i]
      while i < j:
        while i < j and list[j]>=key:
          j = j - 1
        list[i]=list[j]
        while i < j and list[i]<=key:
          i = i + 1
        list[j]=list[i]
      list[i]=key
      quick_sort(list,low,i-1)
      quick_sort(list,j+1,high)
      return list

    4.选择排序

    选择排序的原理是是先找到起始数组中最小的元素,将它交换到i=0;然后寻找剩下元素中最小的元素,将它交换到i=1的位置…… 直到找到第二大的元素,将它交换到n-2的位置。这时,整个数组的排序完成。

    def select_sort(list):
      length=len(list)
      for i in range(length):
        min_index=i
        for j in range(i,length):
          if list[j]<list[min_index]:
            min_index=j
        list[i],list[min_index]=list[min_index],list[i]
      return list

    5.归并排序

    归并排序是对数组进行拆分再拆分,直到不能再拆分,然后分别对最小粒度的子数组进行合并,然后再合并稍微大一点的数组,直到最终合成一个最大的数组。分两个函数完成,一个负责拆分,一个负责排序合并。

    def merge_sort(list):
      if len(list)<=1:
        return list
      mid=int(len(list)/2)
      left=merge_sort(list[:mid])
      right=merge_sort(list[mid:])
      return merge(left,right)
    def merge(list1,list2):
      list=[]
      i,j=0,0
      while i<len(list1) and j<len(list2):
        if list1[i]<list2[j]:
          list.append(list1[i])
          i=i+1
        elif list1[i]>=list2[j]:
          list.append(list2[j])
          j=j+1
      list.extend(list1[i:])
      list.extend(list2[j:])
      return list

    6.希尔排序

    def shell_sort(nums):
      step = len(nums)/2
      while step > 0:
        for i in range(step, len(nums)):
          while i >= step and nums[i-step] > nums[i]:
            nums[i], nums[i-step] = nums[i-step], nums[i]
            i -= step
        step = step/2
      return nums
    
    下一篇:没有了