常见算法python实现(sort)

• Bubble sort(冒泡排序)
  原理：每次从队列的第一个数开始，依次比较相邻的两个数，将小数放在前面,大数放在后面，所以每进行一次冒泡后将会把前面队列中的最大数放到前面队列的队尾。
  时间复杂度：O(n^2)
  空间复杂度：O(1)

#!/user/bin/env python2
# -*-coding:utf-8 -*-
def bubbleSort(alist):
  for i in xrange(len(alist)):
    print alist        //打印出每次冒泡后的队列情况
    for j in xrange(1,len(alist)-i):
      if alist[j-1]>alist[j]:              //相邻数进行比较，大的放后面，小的放前面
         alist[j-1],alist[j]=alist[j],alist[j-1]
  return alist              //退出bubbleSort模块
test_bubbleSort_list=[8,7,6,5,4,3,2,1]
print bubbleSort(test_bubbleSort_list)

• Selection sort(选择排序)
  原理：不断选择剩余元素中的最小者。
  1、找到数组中最小元素并将其和数组第一个元素交换位置；
  2、在剩下的元素中找到最小元素并将其与数组第二个元素交换，直至整个数组排序。

#!/user/bin/env python2
# -*- coding:utf-8 -*-
def selectionSort(alist):
  for i in xrange(len(alist)):
    print alist
    min_index=i
    for j in xrange(i+1,len(alist)):
      if alist[j]<alist[min_index]:
        min_index=j
    alist[min_index],alist[i]=alist[i],alist[min_index]
  return alist
unsorted_list=[8,7,6,5,4,3,2,1]
print selectionSort(unsorted_list)

• Insertion sort(插入排序)
  原理：通过构建有序序列，对于未排序序列，从后向前扫描(对于单向链表则只能从前往后遍历)，找到相应位置并插入。
  1、 从第一个元素开始，该元素可认为已排序；
  2、取下一个元素，对已排序数组从后往前扫描；
  3、若从排序数组中取出的元素大于新元素，则移至下一位置；
  4、重复步骤3，直至找到已排序元素小于或等于新元素的位置；
  5、插入新元素至该位置；
  6、重复2~5。

#!/user/bin/env python2
# -*-coding:utf-8 -*-
def insertionSort(alist):
  for i,item_i in enumerate(alist):
    print alist
    index=i
    while index>0 and alist[index-1]>item_i:
      alist[index]=alist[index-1]
      index-=1
    alist[index]=item_i
  return alist
unsorted_list=[8,7,6,5,4,3,2,1]
print insertionSort(unsorted_list)

• Merge Sort(归并排序)
  原理：先使每个子序列有序，再使子序列段间有序。
  //将两个有序对数组归并成一个更大的有序数组。通常做法为递归排序，并将两个不同的有序数组归并到第三个数组中；归并排序是一种典型的分治应用。

#!/user/bin/env python2
# -*-coding:utf-8 -*-
def MergeSort(lists):
    if len(lists)<=1:
        return lists
    num=int(len(lists)/2)
    left=MergeSort(lists[:num])
    right=MergeSort(lists[num:])
    return Merge(left,right)

def Merge(left,right):
    l,r=0,0
    result=[]
    while l<len(left) and r<len(right):
        if left[l]<right[r]:
            result.append(left[l])
            l+=1
        else:
            result.append(right[r])
            r+=1
    result+=left[l:]
    result+=right[r:]
    return result
print MergeSort([8,7,6,5,4,3,2,1])

• Quick Sort(快速排序)
  原理：快排是一种采用分治思想的排序算法，大致分为三个步骤。
  1、定基准——首先随机选择一个元素最为基准；
  2、划分区——所有比基准小的元素置于基准左侧，比基准大的元素置于右侧；
  3、递归调用——递归地调用此切分过程。

#!/user/bin/env python2
# -*-coding:utf-8 -*-
def qsort3(alist,l,u):
    print alist
    if l>=u:
        return
    t=alist[l]
    i=l+1
    j=u
    while True:
        while i<=u and alist[i]<t:
            i+=1
        while alist[j]>t:
            j-=1
        if i>j:
            break
        alist[i],alist[j]=alist[j],alist[i]
    alist[l],alist[j]=alist[j],alist[l]
    qsort3(alist,l,j-1)
    qsort3(alist,j+1,u)
    
unsortedArray=[6,5,3,1,8,7,2,4]
print qsort3(unsortedArray,0,len(unsortedArray)-1)