用Python实现各种排序算法

1.冒泡排序

比较相邻的元素大小，将小的前移，大的后移，就像水中的气泡一样，最小的元素经过几次移动，会最终浮到水面上。

def bubble(list):      for i in range(len(list)):          for j in range(0,len(list)-1-i):              if list[j] > list[j+1]:                  list[j],list[j+1]=list[j+1],list[j]  if name == 'main':      list1 = [2,3,5,7,8,9,6,54,1,42]      bubble(list1)      print(list1)

2.插入排序

将一个待排数据按其大小插入到已经排序的数据中的适当位置，直到全部插入完毕。

def insertsort(list):      if list != None:          if len(list) == 1:              pass          else:              for i in range(1,len(list)):#start with second item.                  temp = list[i]                  for j in range(i):                      if list[j]>list[i]:                          for k in range(i,j,-1):#                              list[k]= list[k-1]                          list[j] = temp  if name == 'main':      list1 = [3,2,7,5,8,9,6,54,1,42]      insertsort(list1)      print(list1)

3.快速排序

(1)这里实现第一轮排序，不妨称第一个元素为锚
(2)i，j分别指向待排序序列的第一和最后一个元素
(3)j与锚比较，若大于锚则左移，直到小于锚的元素停下，与i指向元素交换，i后移
(4)接着，i与锚比较，若小于则右移，直到大于锚的元素停下，与j指向的元素交换，j前移，
(5)i,j交替移动，i==j时，锚temp到达最终位置。

L = [90,89,78,67,56,45,34,23,12,0]  def first_sort(numbers,i,j):      temp = numbers[i]      while i!=j:          while i<j and numbers[j]>temp:              j = j - 1          if i < j              numbers[i] = numbers[j]              i = i + 1          while i < j and numbers[i]<temp:              i = i + 1          if i <j:              numbers[j] = numbers[i]              j = j - 1          numbers[i] = temp          return i  def quick_sort(numbers,i,j):      if i<j:          middle = first_sort(numbers,i,j)          quick_sort(numbers,i,middle-1)          quick_sort(numbers,middle+1,j)  if name=='main':      quick_sort(L,0,len(L)-1)      print

4.选择排序

从所有序列中先找到最小的，然后放到第一个位置。之后再看剩余元素中最小的，放到第二个位置……以此类推，就可以完成整个的排序工作。

def selectionsort(list):      if list != None:          for i in range(len(list)):              min = i              for j in range(i+1,len(list)):                  if list[min] > list[j]:                      min = j              if min != i:                  list[min],list[i] = list[i],list[min]  if name == 'main':      list1 = [2,3,5,7,8,9,6,54,1,42]      selectionsort(list1)      print(list1)

5.希尔排序

先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。

test=[9,2,3,5,7]  def ShellSort(data,flag):      '''      data: list,to be sorted      flag: 0->asc,1->desc      return a new sorted list      '''      retData=[]      #copy data to retData      for item in data:          retData.append(item)      #sort retData      count=len(retData)      step=count/2;      while step>0:          i=0          while i<count:              j=i+step              while j<count:                  t=retData.pop(j)                  k=j-step                  #asc                  if flag==0:                      while k>=0:                          if t>=retData[k]:                              retData.insert(k+1, t)                              break                          k=k-step                      if k < 0:                          retData.insert(0, t)                  #desc                  elif flag==1:                      while k>=0:                          if t<=retData[k]:                              retData.insert(k+1, t)                              break                          k=k-step                      if k<0:                          retData.insert(0, t)                  j=j+step              i=i+1          step=step/2      return retData  data=ShellSort(test,0)  print 'Asc:',data  data=ShellSort(test,1)  print 'Desc:',data