+关注继续查看

# 常见排序算法-Python实现

python

1.二分法

python    32行
1. #coding=utf-8
2. def binary_search(input_array, value):
3. """Your code goes here."""
4. length = len(input_array)
5. left = 0
6. right = length-1
7. if length == 1
8. return 0 if value == input_value[0] else -1
9. else
10. mid = (left+right)/2
11. while(right-left>1):
12. if input_array[mid] == value:
13. return mid
14. elif input_array[mid] > value:
15. right = mid
16. mid = (left+right)/2
17. else
18. left = mid
19. mid = (left+right)/2
20. if input_array[left] == value:
21. return left
22. elif input_array[right] == value:
23. return right
24. else
25. return -1
26.
27. test_list = [1,3,9,11,15,19,29
28. test_val1 = 25
29. test_val2 = 15
30. print (binary_search(test_list, test_val1))
31. print (binary_search(test_list, test_val2))

2.冒泡法

python    60行
1. #coding=utf-8
2.
3. # way=1递增排序 way=0递减排序
4. def bubble_sort(array,way=1):
5. length = len(array)
6.
7. if not length:
8. print("Error!The length of array must be greater than 0.\n"
9. return 'Wrong array'
10.
11. if way == 1
12. while length > 0
13. for i in range(length-1):
14. if array[i] > array[i+1]:
15. array[i],array[i+1] = array[i+1],array[i]
16. length -= 1
17. return array
18.
19. elif way == 0
20. while length > 0
21. for i in range(length-1):
22. if array[i] < array[i+1]:
23. array[i],array[i+1] = array[i+1],array[i]
24. length -= 1
25. return array
26.
27. # 加入排序判断标志，可提高运行效率
28. # way=1递增排序 way=0递减排序
29. def better_bubble_sort(array,way=1):
30. is_sorted = True # 判断记录上次遍历是否进行过交换，若没有则表示不用再遍历了
31. length = len(array)
32.
33. if not length:
34. print("Error!The length of array must be greater than 0.\n"
35. return 'Wrong array'
36.
37. if way == 1
38. while length > 0 and is_sorted:
39. for i in range(length-1):
40. is_sorted = False
41. if array[i] > array[i+1]:
42. array[i],array[i+1] = array[i+1],array[i]
43. is_sorted = True
44. length -= 1
45. return array
46.
47. elif way == 0
48. while length > 0 and is_sorted:
49. for i in range(length-1):
50. is_sorted = False
51. if array[i] < array[i+1]:
52. array[i],array[i+1] = array[i+1],array[i]
53. is_sorted = True
54. length -= 1
55. return array
56.
57.
58. test = [21, 4, 1, 3, 9, 20, 25, 6, 21, 14]
59. print(better_bubble_sort(test,1))

3.插入排序

python    19行
1. #coding=utf-8
2.
3. def insert_sort(array):
4. length = len(array)
5. flag = array[0
6. for x in range(1,length):
7. # 之前的
8. if array[x] < array[x-1]:
9. flag = array[x]
10. y = x
11. while y != 0 and array[y-1] > flag :
12. array[y] = array[y-1
13. y -= 1
14. array[y] = flag
15. return array
16.
17. test = [21, 4, 1, 3, 9, 20, 25, 20, 3
18. print(insert_sort(test))

4.归并排序

python    31行
1. #coding=utf-8
2.
3. def merge_sort(array):
4. if len(array) <= 1
5. return array
6.
7. split_index = len(array)/2
8. left = merge_sort(array[:split_index])
9. right = merge_sort(array[split_index:])
10. return merge(left,right)
11.
12. def merge(left,right):
13. i = 0
14. j = 0
15. result = []
16. while i < len(left) and j < len(right):
17. if left[i] <= right[j]:
18. result.append(left[i])
19. i += 1
20. else
21. result.append(right[j])
22. j += 1
23.
24. result += (left[i:])
25. result += (right[j:])
26. return result
27.
28. a = [1,2
29. test = [21, 4, 1, 3, 9, 20, 25]
30. print(merge_sort(test))

5.选择排序

python    16行
1. #coding=utf-8
2.
3. def select_sort(array):
4. length = len(array)
5. # mini = array[0]
6. for i in range(length):
7. mini = array[i]
8. for j in range(i,length):
9. if array[j] < mini:
10. mini = array[j]
11. array[i],array[j] = array[j],array[i]
12. return array
13.
14. test = [21, 4, 1, 3, 9, 20, 25, 20, 3]
15. print(select_sort(test))

6.快速排序

python    26行
1. #coding=utf-8
2.
3. # 递归
4. def quick_sort(lists, left, right):
5. # 快速排序
6. if left >= right:
7. return lists
8. key = lists[left]
9. low = left
10. high = right
11. while left < right:
12. while left < right and lists[right] >= key:
13. right -= 1
14. lists[left] = lists[right]
15. while left < right and lists[left] <= key:
16. left += 1
17. lists[right] = lists[left]
18. lists[right] = key
19. quick_sort(lists, low, left - 1
20. quick_sort(lists, left + 1, high)
21. return lists
22.
23.
24. test = [21, 4, 1, 3, 9, 20, 25, 6, 21, 14
25. print (quick_sort(test,0,len(test)-1))

written by MARSGGBO
2017-2-14

|
11月前
|
JSON 区块链 数据格式
Python实现一个简单的区块链

392 0
|
11月前
|

python 实现pacs功能 推送下拉影像
python 实现dcmtk关联pacs功能 推送下拉影像
199 0
|
11月前
|

Leedcode 每日一练 搜索二维矩阵Ⅰ Python实现
Leedcode 每日一练 搜索二维矩阵Ⅰ Python实现
97 2
|
11月前
|

Leecode加法题目3个 每日练习 Python实现
Leecode加法题目3个 每日练习 Python实现
74 0
|
11月前
|
iOS开发 Python
Python实现微信消息连续发送
Python实现微信消息连续发送
317 0
|
11月前
|
Python
Python print() 打印两个 list ，实现中间换行
Python print() 打印两个 list ，实现中间换行
490 0
|
11月前
|
Python
python实现微信小游戏“飞机大战”
python实现微信小游戏“飞机大战”
221 0
|
11月前
|
Python
Python分分钟实现图书管理系统(含代码)
Python分分钟实现图书管理系统(含代码)
216 0
|
11月前
|
JSON 算法 数据安全/隐私保护
Python：使用PyJWT实现JSON Web Tokens加密解密
Python：使用PyJWT实现JSON Web Tokens加密解密
212 0
|
12月前
|
Python
Python实现因子分析（附案例实战）
Python实现因子分析（附案例实战）
690 0