python各种排序算法,python用排序算法 函数实现

  python各种排序算法,python用排序算法 函数实现

  python排序算法有哪些?下面这篇文章将向你介绍Python的十大经典排序算法。有一定的参考价值,有需要的朋友可以参考一下,希望对大家有所帮助。

  现在很多事情都可以用算法解决。在编程中,算法起着非常重要的作用。用函数封装算法,使得程序不需要重复编写就能更好地被调用。

  Python十大经典算法:

  一、插入排序

  1.算法思想

  从第二个元素开始,将其与前一个元素进行比较。如果前一个元素大于当前元素,则将前一个元素向后移动,当前元素依次向前移动,直到找到一个小于或等于它的元素并插入到它的后面。

  然后选择第三个元素,重复上述操作,插入,依次选择最后一个元素,插入完成所有排序。

  2.代码实现

  定义插入_排序(arr):

  #插入排序

  #第一层表示循环插入的次数。

  对于范围(1,len(arr)):中的I

  #设置当前需要插入的元素

  current=arr[i]

  #与当前元素进行比较的比较元素

  pre_index=i - 1

  而pre_index=0且arr[pre_index] current:

  #当比较元素大于当前元素时,将比较元素向后移动。

  arr[前索引1]=arr[前索引]

  #向前选择下一个比较元素

  pre_index -=1

  #当比较元素小于当前元素时,在它后面插入当前元素。

  arr[预索引1]=当前

  返回二、选择排序

  1.算法思想

  设第一个元素为比较元素,依次与后面的元素进行比较。比较完所有元素后,找出最小的元素,与第一个元素交换,重复上述操作。我们会找到第二小的元素和第二个位置元素,以此类推,找到剩下的最小的元素,把它改到前面,也就是完成排序。

  2.代码实现

  定义选择_排序(arr):

  #选择排序

  #第一层表示循环选择的次数。

  对于范围内的I(len(arr)-1):

  #将起始元素设置为最小元素

  min_index=i

  #第二层for表示将最小的元素与后面的元素逐一进行比较。

  对于范围(I ^ 1,len(arr)):中的j

  if arr[j] arr[min_index]:

  #如果当前元素小于最小元素,则将当前元素角标记为最小元素角标记。

  min_index=j

  #搜索一次后,将最小的元素与起始元素交换。

  arr[最小索引],arr[i]=arr[i],arr[最小索引]

  返回三、冒泡排序

  1.算法思想

  从第一个到第二个比较一下。如果第一个比第二个大,交换位置,然后比较第二个和第三个。渐渐的,第一轮过后,最大的元素已经排到了最后。

  因此,如果重复上述操作,第二个最大的将在倒数第二个位置。然后重复上述操作n-1次,完成排序,因为最后一次只有一个元素,所以不需要比较。

  2.代码实现

  def bubble_sort(数组):

  #冒泡排序

  #第一层表示循环次数。

  对于范围内的I(len(arr)-1):

  #的第二层指示具体比较哪两个元素。

  对于范围内的j(len(arr)-1-I):

  if arr[j] arr[j 1]:

  #如果前面的比后面的大,交换这两个元素的位置

  arr[j],arr[j 1]

   = arr[j + 1], arr[j]

   return arr四、快速排序

  1.算法思想

  找出基线条件,这种条件必须尽可能简单,不断将问题分解(或者说缩小规模),直到符合基线条件。

  2.代码实现

  

def quick_sort(arr):

   if len(arr) < 2:

   # 基线条件:为空或只包含一个元素的数组是“有序”的

   return arr

   else:

   # 递归条件

   pivot = arr[0]

   # 由所有小于基准值的元素组成的子数组

   less = [i for i in arr[1:] if i <= pivot]

   # 由所有大于基准值的元素组成的子数组

   greater = [i for i in array[1:] if i > pivot]

   return quicksort(less) + [pivot] + quicksort(greater)

  print(quick_sort([10, 5, 2, 3]))

五、归并排序

  1.算法思想

  归并排序是分治法的典型应用。分治法(pide-and-Conquer):将原问题划分成 n 个规模较小而结构与原问题相似的子问题;递归地解决这些问题,然后再合并其结果,就得到原问题的解,分解后的数列很像一个二叉树。

  具体实现步骤:

  

  1. 使用递归将源数列使用二分法分成多个子列

      

  2. 申请空间将两个子列排序合并然后返回

      

  3. 将所有子列一步一步合并最后完成排序

      

  4. 注:先分解再归并
2.代码实现

  

def merge_sort(arr):

   #归并排序

   if len(arr) == 1:

   return arr

   # 使用二分法将数列分两个

   mid = len(arr) // 2

   left = arr[:mid]

   right = arr[mid:]

   # 使用递归运算

   return marge(merge_sort(left), merge_sort(right))

  def marge(left, right):

   #排序合并两个数列

   result = []

   # 两个数列都有值

   while len(left) > 0 and len(right) > 0:

   # 左右两个数列第一个最小放前面

   if left[0] <= right[0]:

   result.append(left.pop(0))

   else:

   result.append(right.pop(0))

   # 只有一个数列中还有值,直接添加

   result += left

   result += right

   return result

六、希尔排序

  1.算法思想

  希尔排序的整体思想是将固定间隔的几个元素之间排序,然后再缩小这个间隔。这样到最后数列就成为了基本有序数列。

  具体步骤:

  

  1. 计算一个增量(间隔)值

      

  2. 对元素进行增量元素进行比较,比如增量值为7,那么就对0,7,14,21…个元素进行插入排序

      

  3. 然后对1,8,15…进行排序,依次递增进行排序

      

  4. 所有元素排序完后,缩小增量比如为3,然后又重复上述第2,3步

      

  5. 最后缩小增量至1时,数列已经基本有序,最后一遍普通插入即可

      

2.代码实现

  

def shell_sort(arr):

   #希尔排序

   # 取整计算增量(间隔)值

   gap = len(arr) // 2

   while gap > 0:

   # 从增量值开始遍历比较

   for i in range(gap, len(arr)):

   j = i

   current = arr[i]

   # 元素与他同列的前面的每个元素比较,如果比前面的小则互换

   while j - gap >= 0 and current < arr[j - gap]:

   arr[j] = arr[j - gap]

   j -= gap

   arr[j] = current

   # 缩小增量(间隔)值

   gap //= 2

   return arr

七、基数排序

  1.算法思想

  基数排序(radix sort)属于“分配式排序”(distribution sort),又称“桶子法”(bucket sort)或bin sort,顾名思义,它是透过键值的部份资讯,将要排序的元素分配至某些“桶”中,藉以达到排序的作用,基数排序法是属于稳定性的排序,其时间复杂度为O (nlog(r)m),其中r为所采取的基数,而m为堆数,在某些时候,基数排序法的效率高于其它的稳定性排序法。

  2.代码实现

  2.1由桶排序改造,从最低位到最高位依次桶排序,最后输出最后排好的列表。

  

def RadixSort(list,d):

   for k in range(d):#d轮排序

   # 每一轮生成10个列表

   s=[[] for i in range(10)]#因为每一位数字都是0~9,故建立10个桶

   for i in list:

   # 按第k位放入到桶中

   s[i//(10**k)%10].append(i)

   # 按当前桶的顺序重排列表

   list=[j for i in s for j in i]

   return list

2.2简单实现

  

from random import randint

  def radix_sort():

   A = [randint(1, 99999999) for _ in xrange(9999)]

   for k in xrange(8):

   S = [ [] for _ in xrange(10)]

   for j in A:

   S[j / (10 ** k) % 10].append(j)

   A = [a for b in S for a in b]

   for i in A:

   print i

八、计数排序

  1.算法思想

  对每一个输入元素x,确定小于x的元素个数。利用这一信息,就可以直接把x 放在它在输出数组上的位置上了,运行时间为O(n),但其需要的空间不一定,空间浪费大。

  2.代码实现

  

from numpy.random import randint

  def Conuting_Sort(A):

   k = max(A) # A的最大值,用于确定C的长度

   C = [0]*(k+1) # 通过下表索引,临时存放A的数据

   B = (len(A))*[0] # 存放A排序完成后的数组

   for i in range(0, len(A)):

   C[A[i]] += 1 # 记录A有哪些数字,值为A[i]的共有几个

   for i in range(1, k+1):

   C[i] += C[i-1] # A中小于i的数字个数为C[i]

   for i in range(len(A)-1, -1, -1):

   B[C[A[i]]-1] = A[i] # C[A[i]]的值即为A[i]的值在A中的次序

   C[A[i]] -= 1 # 每插入一个A[i],则C[A[i]]减一

   return B

九、堆排序

  1.算法思想

  堆分为最大堆和最小堆,是完全二叉树。堆排序就是把堆顶的最大数取出,将剩余的堆继续调整为最大堆,具体过程在第二块有介绍,以递归实现 ,

  剩余部分调整为最大堆后,再次将堆顶的最大数取出,再将剩余部分调整为最大堆,这个过程持续到剩余数只有一个时结束。

  2.代码实现

  

import time,random

  def sift_down(arr, node, end):

   root = node

   #print(root,2*root+1,end)

   while True:

   # 从root开始对最大堆调整

   child = 2 * root +1 #left child

   if child > end:

   #print('break',)

   break

   print("v:",root,arr[root],child,arr[child])

   print(arr)

   # 找出两个child中交大的一个

   if child + 1 <= end and arr[child] < arr[child + 1]: #如果左边小于右边

   child += 1 #设置右边为大

   if arr[root] < arr[child]:

   # 最大堆小于较大的child, 交换顺序

   tmp = arr[root]

   arr[root] = arr[child]

   arr[child]= tmp

   # 正在调整的节点设置为root

   #print("less1:", arr[root],arr[child],root,child)

   root = child #

   #[3, 4, 7, 8, 9, 11, 13, 15, 16, 21, 22, 29]

   #print("less2:", arr[root],arr[child],root,child)

   else:

   # 无需调整的时候, 退出

   break

   #print(arr)

   print('-------------')

  def heap_sort(arr):

   # 从最后一个有子节点的孩子还是调整最大堆

   first = len(arr) // 2 -1

   for i in range(first, -1, -1):

   sift_down(arr, i, len(arr) - 1)

   #[29, 22, 16, 9, 15, 21, 3, 13, 8, 7, 4, 11]

   print('--------end---',arr)

   # 将最大的放到堆的最后一个, 堆-1, 继续调整排序

   for end in range(len(arr) -1, 0, -1):

   arr[0], arr[end] = arr[end], arr[0]

   sift_down(arr, 0, end - 1)

   #print(arr)

十、桶排序

  1.算法思想

  为了节省空间和时间,我们需要指定要排序的数据中最小以及最大的数字的值,来方便桶排序算法的运算。

  2.代码实现

  

#桶排序

  def bucket_sort(the_list):

   #设置全为0的数组

   all_list = [0 for i in range(100)]

   last_list = []

   for v in the_list:

   all_list[v] = 1 if all_list[v]==0 else all_list[v]+1

   for i,t_v in enumerate(all_list):

   if t_v != 0:

   for j in range(t_v):

   last_list.append(i)

   return last_list

总结:

  在编程中,算法都是相通的,算法重在算法思想,相当于将一道数学上的应用题的每个条件,区间,可能出现的结果进行分解,分步骤的实现它。算法就是将具体问题的共性抽象出来,将步骤用编程语言来实现。通过这次对排序算法的整理,加深了对各算法的了解,具体的代码是无法记忆的,通过对算法思想的理解,根据伪代码来实现具体算法的编程,才是真正了解算法。

  推荐学习:Python视频教程以上就是python排序算法有哪些?的详细内容,更多请关注盛行IT软件开发工作室其它相关文章!

  

郑重声明:本文由网友发布,不代表盛行IT的观点,版权归原作者所有,仅为传播更多信息之目的,如有侵权请联系,我们将第一时间修改或删除,多谢。

留言与评论(共有 条评论)
   
验证码: