#!/usr/bin/python
# coding:utf-8
#直接插入排序
def insert_sort(list):
  for i in range(len(list)):
    Key = list [i]      #待插入元素
      j = i - 1
      while(Key < list[j] and j >= 0):
        list[j+1] = list[j]  #后移元素
        list[j] = Key
        j=j-1
  return list
#冒泡排序  
def bubble_sort(list):
  for i in range(1, len(list)):
    for j in range(len(list)-i):
      if list[j] > list [j+1]:
        list[j+1],list[j] =list[j],list[j+1]
  return list
#快速排序
def position_key(list, low, high):
  i = low
  j = high
  key = list[low]
  while(i < j):
    while(i < j and list[j] >= key):  #從右向左，尋找第一個(gè)小于基準(zhǔn)元素的數(shù)據(jù)索引。 注意：i<y 的判斷，內(nèi)循環(huán)更新j
      j -= 1
    if i < j :
      list[i] = list[j]
    while(i<j and list[i] <= key):   #從左向右，尋找地一個(gè)大于基準(zhǔn)元素的數(shù)據(jù)索引。i<y同上
      i += 1
    if i < j:
      list[j] = list[i]
  list[j] = key     # 基準(zhǔn)元素位置 
  return j
def quick_sort(list, low, high):
  if low < high:
    position = position_key(list, low, high) #將數(shù)據(jù)分成前后兩個(gè)子序列（前邊序列值均小于后邊序列）
    quick_sort(list, low, position-1)    #將前面的序列快速排序
    quick_sort(list, position+1, high)    #將后面的序列快速排序
  return list
#選擇排序
def select_sort(list):
  for i in range(len(list)):
    for j in range(i, len(list)):
      if list[i] > list[j]:
        list[i], list[j] = list[j], list[i]
  return list
list = [23, 232, 11, 89,121, 64, 34, 12, 23423, 2312, 167, 768, 932, 346, 32789, 335, 2, 1145, 34, 56, 99, 111]
print '原始序列  ：', list
print '直接插入排序：', insert_sort(list)
print '冒泡排序  ：', bubble_sort(list)
print '快速排序  ：', quick_sort(list, 0, len(list)-1)
print '選擇排序  ：', select_sort(list)