返回顶部

用Python实现各种排序算法

[复制链接]
骑单车的小女孩Lv.2 显示全部楼层 发表于 2016-12-30 00:37:57 |阅读模式 打印 上一主题 下一主题

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
1.冒泡排序
比较相邻的元素大小,将小的前移,大的后移,就像水中的气泡一样,最小的元素经过几次移动,会最终浮到水面上。
  1. def bubble(list):
  2.     for i in range(len(list)):
  3.         for j in range(0,len(list)-1-i):
  4.             if list[j] > list[j+1]:
  5.                 list[j],list[j+1]=list[j+1],list[j]
  6. if name == 'main':
  7.     list1 = [2,3,5,7,8,9,6,54,1,42]
  8.     bubble(list1)
  9.     print(list1)
复制代码
2.插入排序
将一个待排数据按其大小插入到已经排序的数据中的适当位置,直到全部插入完毕。
  1. def insertsort(list):
  2.     if list != None:
  3.         if len(list) == 1:
  4.             pass
  5.         else:
  6.             for i in range(1,len(list)):#start with second item.
  7.                 temp = list[i]
  8.                 for j in range(i):
  9.                     if list[j]>list[i]:
  10.                         for k in range(i,j,-1):#
  11.                             list[k]= list[k-1]
  12.                         list[j] = temp
  13. if name == 'main':
  14.     list1 = [3,2,7,5,8,9,6,54,1,42]
  15.     insertsort(list1)
  16.     print(list1)
复制代码
3.快速排序
(1)这里实现第一轮排序,不妨称第一个元素为锚
(2)i,j分别指向待排序序列的第一和最后一个元素
(3)j与锚比较,若大于锚则左移,直到小于锚的元素停下,与i指向元素交换,i后移
(4)接着,i与锚比较,若小于则右移,直到大于锚的元素停下,与j指向的元素交换,j前移,
(5)i,j交替移动,i==j时,锚temp到达最终位置。
  1. L = [90,89,78,67,56,45,34,23,12,0]
  2. def first_sort(numbers,i,j):
  3.     temp = numbers[i]
  4.     while i!=j:
  5.         while i<j and numbers[j]>temp:
  6.             j = j - 1
  7.         if i < j
  8.             numbers[i] = numbers[j]
  9.             i = i + 1
  10.         while i < j and numbers[i]<temp:
  11.             i = i + 1
  12.         if i <j:
  13.             numbers[j] = numbers[i]
  14.             j = j - 1
  15.         numbers[i] = temp
  16.         return i
  17. def quick_sort(numbers,i,j):
  18.     if i<j:
  19.         middle = first_sort(numbers,i,j)
  20.         quick_sort(numbers,i,middle-1)
  21.         quick_sort(numbers,middle+1,j)
  22. if name=='main':
  23.     quick_sort(L,0,len(L)-1)
  24.     print
复制代码

4.选择排序
从所有序列中先找到最小的,然后放到第一个位置。之后再看剩余元素中最小的,放到第二个位置……以此类推,就可以完成整个的排序工作。
  1. def selectionsort(list):
  2.     if list != None:
  3.         for i in range(len(list)):
  4.             min = i
  5.             for j in range(i+1,len(list)):
  6.                 if list[min] > list[j]:
  7.                     min = j
  8.             if min != i:
  9.                 list[min],list[i] = list[i],list[min]
  10. if name == 'main':
  11.     list1 = [2,3,5,7,8,9,6,54,1,42]
  12.     selectionsort(list1)
  13.     print(list1)
复制代码
5.希尔排序
先将整个待排元素序列分割成若干个子序列(由相隔某个“增量”的元素组成的)分别进行直接插入排序,然后依次缩减增量再进行排序,待整个序列中的元素基本有序(增量足够小)时,再对全体元素进行一次直接插入排序。
  1. test=[9,2,3,5,7]
  2. def ShellSort(data,flag):
  3.     '''
  4.     data: list,to be sorted
  5.     flag: 0->asc,1->desc
  6.     return a new sorted list
  7.     '''
  8.     retData=[]
  9.     #copy data to retData
  10.     for item in data:
  11.         retData.append(item)
  12.     #sort retData
  13.     count=len(retData)
  14.     step=count/2;
  15.     while step>0:
  16.         i=0
  17.         while i<count:
  18.             j=i+step
  19.             while j<count:
  20.                 t=retData.pop(j)
  21.                 k=j-step
  22.                 #asc
  23.                 if flag==0:
  24.                     while k>=0:
  25.                         if t>=retData[k]:
  26.                             retData.insert(k+1, t)
  27.                             break
  28.                         k=k-step
  29.                     if k < 0:
  30.                         retData.insert(0, t)
  31.                 #desc
  32.                 elif flag==1:
  33.                     while k>=0:
  34.                         if t<=retData[k]:
  35.                             retData.insert(k+1, t)
  36.                             break
  37.                         k=k-step
  38.                     if k<0:
  39.                         retData.insert(0, t)
  40.                 j=j+step
  41.             i=i+1
  42.         step=step/2
  43.     return retData
  44. data=ShellSort(test,0)
  45. print 'Asc:',data
  46. data=ShellSort(test,1)
  47. print 'Desc:',data
复制代码

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

云萌主 云萌主-BIGSAAS旗下,由北京合智互联信息技术有限公司在2018年创立,为广大云应用技术爱好者的平台。在云萌主论坛可以查看云应用技术文章、云产品产品最新资讯、技术问答、技术视频。在畅游云上技术的同时,学到最新的云应用产品和技术。
  • 微信公众号

  • Powered by Discuz! X3.4 | Licensed | Copyright © 2001-2022, Aliyun Cloud. | 星点互联设计
  • 京ICP备18052714号 | 营业执照 | |合智互联| QQ