#!/usr/bin/python
# -*- coding: UTF-8 -*-

import random
import time

#快速排序
def quickSort(l,low,high):
	i=low
	j=high
	if i>=j:
		return l
	key=l[i]
	while i<j:
		while i<j and l[j]>=key:
			j=j-1
		l[i]=l[j]
		while i<j and l[i]<=key:
			i=i+1
		l[j]=l[i]
	l[i]=key
	quickSort(l,low,i-1)
	quickSort(l,j+1,high)
	return l

#插入排序
def insert(l):
	for i in range(1,len(arr)):
		tmp=l[i]
		j=i
		while j>0 and l[j-1]>l[i]:
			l[j]=l[j-1]
			j-=1
		l[j]=tmp
			 
#冒泡排序
def bubbling(l):
	a=len(l)
	i=0
	while i<a:
		j=0
		while j<(a-i-1):
			if l[j+1]<l[j]:
				l[j],l[j+1]=l[j+1],l[j]
			j+=1
		i+=1
#选择排序
def select(l):
	b=len(l)
	i=0
	while i<b:
		j=i+1
		while j<b:
			if l[j]<l[i]:
				l[i],l[j]=l[j],l[i]
			j+=1
		i+=1	
#基数排序
import math
def radix(l):
	radix=10
	K = int(math.ceil(math.log(max(l), radix))) # 用K位数可表示任意整数
    	bucket = [[] for i in range(radix)] # 不能用 [[]]*radix
    	for i in range(1, K+1): # K次循环
        	for val in l:
            		bucket[val%(radix**i)/(radix**(i-1))].append(val) # 析取整数第K位数字 （从低到高）
        	del l[:]
        	for each in bucket:
            		l.extend(each) # 桶合并
        	bucket = [[] for i in range(radix)]
#归并排序
def Merge(left,right):
        result=[]
        q,r=0, 0
        while q<len(left) and r<len(right):
                if left[q] <= right[r]:
                        result.append(left[q])
                        q += 1
                else:
                        result.append(right[r])
                        r += 1
        result+= left[q:]
        result += right[r:]
        return result
def mergeSort(l):
	if len(l) <= 1:
		return l
	num = len(l)/2 
	left = mergeSort(l[:num])
	right = mergeSort(l[num:])
	return Merge(left, right)

#希尔排序
def shell_sort(lists):
	count = len(lists)
	step = 2
   	group = count / step
    	while group > 0:
        	for i in range(0, group):
            		j = i + group
            		while j < count:
                		k = j - group
                		key = lists[j]
                		while k >= 0:
                    			if lists[k] > key:
                        			lists[k + group] = lists[k]
                        			lists[k] = key
                    			k -= group
                		j += group
        	group /= step
    	return lists

#堆排序
def adjust_heap(lists, i, size):
	lchild = 2 * i + 1
    	rchild = 2 * i + 2
    	max = i
    	if i < size / 2:
        	if lchild < size and lists[lchild] > lists[max]:
           		max = lchild
        	if rchild < size and lists[rchild] > lists[max]:
            		max = rchild
        	if max != i:
            		lists[max], lists[i] = lists[i], lists[max]
            		adjust_heap(lists, max, size)
 
def build_heap(lists, size):
    	for i in range(0, (size/2))[::-1]:
        	adjust_heap(lists, i, size)
 
def heap_sort(lists):
    	size = len(lists)
    	build_heap(lists, size)
    	for i in range(0, size)[::-1]:
        	lists[0], lists[i] = lists[i], lists[0]
        	adjust_heap(lists, 0, i)

f=open("data4","w")
i=0
arr=[]
while (i<1000):
	arr+=[random.choice(range(100000))]
	i=i+1
i=0
ticks=time.time()
#quickSort(arr,0,100-1)
#insert(arr)
bubbling(arr)
#select(arr)
#radix(arr)
#arr=mergeSort(arr)
#arr=shell_sort(arr)
#heap_sort(arr)
while (i<1000):
	f.write(str(arr[i]))
	f.write(" ")
	i=i+1
ticks1=time.time()
cc=(ticks1-ticks)
print "运行时间time：%.3fs" % cc
f.close()
