常见排序算法-Python实现

常见排序算法-Python实现

python

排序

算法

1.二分法

python    32行

#coding=utf-8 
def binary_search(input_array, value): 
 """Your code goes here.""" 
    length = len(input_array) 
    left = 0 
    right = length-1 
 if length == 1: 
 return 0 if value == input_value[0] else -1 
 else: 
        mid = (left+right)/2 
 while(right-left>1): 
 if input_array[mid] == value: 
 return mid 
 elif input_array[mid] > value: 
                right = mid 
                mid = (left+right)/2 
 else: 
                left = mid 
                mid = (left+right)/2 
 if input_array[left] == value: 
 return left 
 elif input_array[right] == value: 
 return right 
 else: 
 return -1 
 
test_list = [1,3,9,11,15,19,29] 
test_val1 = 25 
test_val2 = 15 
print (binary_search(test_list, test_val1)) 
print (binary_search(test_list, test_val2)) 

2.冒泡法

python    60行

#coding=utf-8 
 
# way=1递增排序 way=0递减排序 
def bubble_sort(array,way=1): 
	length = len(array) 
 
 if not length: 
		print("Error!The length of array must be greater than 0.\n") 
 return 'Wrong array' 
 
 if way == 1: 
 while length > 0: 
 for i in range(length-1): 
 if array[i] > array[i+1]: 
					array[i],array[i+1] = array[i+1],array[i] 
			length -= 1 
 return array 
 
 elif way == 0: 
 while length > 0: 
 for i in range(length-1): 
 if array[i] < array[i+1]: 
					array[i],array[i+1] = array[i+1],array[i] 
			length -= 1 
 return array 
 
# 加入排序判断标志,可提高运行效率 
# way=1递增排序 way=0递减排序 
def better_bubble_sort(array,way=1): 
	is_sorted = True # 判断记录上次遍历是否进行过交换,若没有则表示不用再遍历了 
	length = len(array) 
 
 if not length: 
		print("Error!The length of array must be greater than 0.\n") 
 return 'Wrong array' 
 
 if way == 1: 
 while length > 0 and is_sorted: 
 for i in range(length-1): 
				is_sorted = False 
 if array[i] > array[i+1]: 
					array[i],array[i+1] = array[i+1],array[i] 
					is_sorted = True 
			length -= 1 
 return array 
 
 elif way == 0: 
 while length > 0 and is_sorted: 
 for i in range(length-1): 
				is_sorted = False 
 if array[i] < array[i+1]: 
					array[i],array[i+1] = array[i+1],array[i] 
					is_sorted = True 
			length -= 1 
 return array 
 
 
test =  [21, 4, 1, 3, 9, 20, 25, 6, 21, 14]  
print(better_bubble_sort(test,1)) 

3.插入排序

python    19行

#coding=utf-8 
 
def insert_sort(array): 
	length = len(array) 
	flag = array[0] 
 for x in range(1,length): 
 # 之前的 
 if array[x] < array[x-1]: 
			flag = array[x] 
			y = x 
 while y != 0 and array[y-1] > flag : 
				array[y] = array[y-1] 
				y -= 1 
			array[y] = flag 
 return array 
 
test = [21, 4, 1, 3, 9, 20, 25, 20, 3] 
print(insert_sort(test)) 

4.归并排序

python    31行

#coding=utf-8 
 
def merge_sort(array): 
 if len(array) <= 1: 
 return array 
 
	split_index = len(array)/2 
	left = merge_sort(array[:split_index]) 
	right = merge_sort(array[split_index:]) 
 return merge(left,right) 
 
def merge(left,right): 
	i = 0 
	j = 0 
	result = [] 
 while i < len(left) and j < len(right): 
 if left[i] <= right[j]: 
			result.append(left[i]) 
			i += 1 
 else: 
			result.append(right[j]) 
			j += 1 
 
	result += (left[i:]) 
	result += (right[j:]) 
 return result 
 
a = [1,2] 
test = [21, 4, 1, 3, 9, 20, 25]  
print(merge_sort(test)) 

5.选择排序

python    16行

#coding=utf-8 
 
def select_sort(array): 
	length = len(array) 
 # mini = array[0] 
 for i in range(length): 
		mini = array[i] 
 for j in range(i,length): 
 if array[j] < mini: 
				mini = array[j] 
				array[i],array[j] = array[j],array[i] 
 return array 
 
test = [21, 4, 1, 3, 9, 20, 25, 20, 3]  
print(select_sort(test)) 

6.快速排序

python    26行

#coding=utf-8 
 
# 递归 
def quick_sort(lists, left, right): 
 # 快速排序 
 if left >= right: 
 return lists 
    key = lists[left] 
    low = left 
    high = right 
 while left < right: 
 while left < right and lists[right] >= key: 
            right -= 1 
        lists[left] = lists[right] 
 while left < right and lists[left] <= key: 
            left += 1 
        lists[right] = lists[left] 
    lists[right] = key 
    quick_sort(lists, low, left - 1) 
    quick_sort(lists, left + 1, high) 
 return lists 
 
 
test = [21, 4, 1, 3, 9, 20, 25, 6, 21, 14] 
print (quick_sort(test,0,len(test)-1)) 

written by MARSGGBO 2017-2-14

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Petrichor的专栏

tensorflow编程: Higher Order Functions

从 elems列表 中 依次 扫描读取 元素 放入 公式进行 迭代计算。相当于python的 map 函数。

10040
来自专栏mathor

回文自动机、AC自动机和后缀自动机介绍(1)

 我们还从一个非常经典的题目出发,最长公共子串问题。给定两个字符串S和T,求S和T的最长公共子串的长度。比如abcdefg和abacabca的最长公共子串是ab...

28430
来自专栏Python小屋

Python标准库itertools中函数精要

1、count() >>> import itertools >>> x = itertools.count(3) >>> x count(3) >>> for...

36880
来自专栏安恒网络空间安全讲武堂

四方密码

四方密码是一种对称式加密法,由法国人Felix Delastelle发明。这种方法将字母两个一组,然后采用多字母替换密码。四方密码用4个5×5的矩阵来加密。每个...

23540
来自专栏小俊博客

微软 KMS 客户端密钥

26350
来自专栏小樱的经验随笔

Gym 100952J&&2015 HIAST Collegiate Programming Contest J. Polygons Intersection【计算几何求解两个凸多边形的相交面积板子题

J. Polygons Intersection time limit per test:2 seconds memory limit per test:64 ...

28870
来自专栏WD学习记录

牛客网 跳石板

小易来到了一条石板路前,每块石板上从1挨着编号为:1、2、3....... 这条石板路要根据特殊的规则才能前进:对于小易当前所在的编号为K的 石板,小易单次只...

12920
来自专栏书山有路勤为径

无重复字符的最长字串

LeetCode 3. Longest Substring Without Repeating Characters 已知一个字符串,求用该字符串的无重复字符...

10330
来自专栏owent

POJ PKU 2549 Sumsets 解题报告

题目链接http://acm.pku.edu.cn/JudgeOnline/problem?id=2549

9610
来自专栏开发与安全

算法:队列与广度优先搜索(迷宫问题)

队列也是一组元素的集合,也提供两种基本操作:Enqueue(入队)将元素添加到队尾,Dequeue(出队)从队头取出元素并返回。就像排队买票一样,先来先服务,先...

37670

扫码关注云+社区

领取腾讯云代金券