云萌主云应用官方论坛

标题: 用Python实现各种排序算法 [打印本页]
作者: 骑单车的小女孩    时间: 2016-12-30 00:37
标题: 用Python实现各种排序算法
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
复制代码
来自：http://www.jianshu.com/p/3380ea152c44





欢迎光临 云萌主云应用官方论坛 (https://yunmengzhu.com/) Powered by Discuz! X3.4