程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
您现在的位置: 程式師世界 >> 編程語言 >  >> 更多編程語言 >> Python

Python algorithm practice week5 sorting algorithm

編輯:Python

0x01 Selection sort

Sorting is one of the most common computer operations , Sorting is to sort a group of disordered data according to certain rules ( Increase or decrease ), The sort object can be numeric , It can also be character type ( according to ASCII The sequence of the codes )

  • Selection sort ( Ascending ) Find the minimum number in several unordered data each time , In the first place of unordered data
    • from N Find the minimum value and subscript in the list of elements , Swap with the first element
    • Starting with the second element N-1 Find the minimum value and its subscript in the elements , Swap with the second element
    • And so on ,N-1 After the round, there is the ordered data
  • Select the implementation of sorting algorithm
# Selection sort
list = [49, 38, 65, 97, 76, 13, 27, 49]
for i in range(len(list) - 1):
m = i
for j in range(i + 1, len(list)):
if list[j] < list[m]:
m = j
list[i], list[m] = list[m], list[i]
print(list)
  • Algorithm analysis Select Sorting common demand comparison N-1 round , The total number of rounds compared is (N-1)+(N-2)+...+2+1=N(N-1)/2 Time

The number of times a sort is selected to perform a swap is N-1 Time

0x02 Bubble sort

  • Algorithmic thought
    • The first round of comparison : Let's start with the first element , Sort all in the list in order N Two consecutive elements of the two elements are compared in pairs , If the two do not satisfy the ascending relation, they are exchanged . After the first round of comparison , The maximum number will sink to the end of the list .
    • The second round of comparison : Let's start with the first element , To the top of the list N-1 Compare the two elements , Bring the second largest number to the bottom
    • And so on ,N-1 After wheel , Sorting complete
  • Implementation of bubble sorting algorithm
list = [77, 42, 35, 10, 22, 101, 5]
for i in range(len(list) - 1):
for j in range(len(list) - 1 - i):
if list[j] > list[j + 1]:
list[j], list[j + 1] = list[j + 1], list[j]
print(list)
  • The improvement of bubble sort algorithm If in a round of comparison , An exchange has never been performed , It means that the order has been arranged
# improvement
list = [77, 42, 35, 10, 22, 101, 5]
for i in range(len(list) - 1):
flag = True
for j in range(len(list) - 1 - i):
if list[j] > list[j + 1]:
list[j], list[j + 1] = list[j + 1], list[j]
flag = False
if flag:
break
print(list)
  • Analysis of bubbling algorithm
    • The main time consumption of the algorithm is the number of comparisons
    • Bubbling algorithms need to be compared N-1 round , The total number of comparisons is (N-1)+(N-2)+...+2+1=N(N-1)/2 Time
    • The number of exchanges performed by bubble sort is uncertain
    • Bubble sort is a sort algorithm with low efficiency

0x03 function 、 recursive

  • The benefits of functions
    • Separate different tasks in the program
    • Implement structured programming
    • Reduce program complexity
    • Achieve code reuse
    • Improve the quality of your code
    • Collaborative development
    • Realize special functions ( recursive )
    • .......
  • Python Classification of functions in
    • Built in functions input()、print()、int()、float()、len()、max() etc.
    • Standard library functions math In bag sqrt()、sin()、cos();random In bag random() etc.
    • Third party library functions
    • Custom library functions
  • function
# Definition of custom function
def Function name ([ Parameter list ]):
The body of the function
# Function call
Function name ([ Argument list ])
# Example : Define a function for averaging
def average(a, b):
return (a + b / 2)
temp = average(1, 3)
print(temp)
  • problem : Write a function to judge whether a number is a prime number , And call its output 200 Prime number within
import math
def isPrime(a):
m = int(math.sqrt(a))
for i in range(2, m + 1):
if a % i == 0:
return False
return True
for i in range(2, 200):
if isPrime(i):
print(i)
  • problem : The bubble sorting algorithm is written in functional form
def bubbleSort(a):
for i in range(len(a) - 1):
for j in range(len(a) - 1 - i):
if a[j] > a[i]:
a[j], a[i] = a[i], a[j]
list = [77, 42, 35, 10, 22, 101, 5]
bubbleSort(list)
print(list)
  • Recursive function Self calling function , Call yourself directly or indirectly inside the function body
# Non recursive methods
def factorial(n):
s = 1
for i in range(1, n + 1):
s = s * i
return s
# Recursive method
def factorial(n):
if n == 1:
return 1
else:
s = n * factorial(n - 1)
return s
print(factorial(3))

0x04 Merge sort

  • Algorithmic thought
    • Will include N The list of elements is split into two containing N/2 Sublist of elements
    • Recursively call merge sort on two sublists ( Finally, the whole list can be divided into N Sublist )
    • Merge two sorted sub lists
  • Implementation of merge sort algorithm
def merge(left, right): # Merge two lists
merged = []
i, j = 0, 0 # i and j Respectively as left and right The subscript
left_len, right_len = len(left), len(right) # Get the length of the left and right lists respectively
while i < left_len and j < right_len: # Loop merge the left and right sub list elements
if left[i] <= right[j]:
merged.append(left[i]) # Merge left sublist elements
i += 1
else:
merged.append(right[j]) # Merge the right child list elements
j += 1
merged.extend(left[i:]) # Merge the remaining elements of the left sublist
merged.extend(right[j:]) # Merge the remaining elements of the right sub list
print(left, right, merged) # Trace debugging
return merged # Return to the merged list
def mergeSort(a): # Merge sort
if len(a) <= 1: # Empty or only one element , Go directly back to the list
return a
mid = len(a) // 2 # Middle of list
left = mergeSort(a[:mid]) # Merge and sort the left sub list
right = mergeSort(a[mid:]) # Merge and sort the right sub list
return merge(left, right) # Merge the ordered left and right sub lists
a = [98, 23, 11, 10, 33, 42]
temp = mergeSort(a)
print(temp)

python The sorting algorithm provided by the language system , The bottom layer is realized by merging and sorting algorithm

a = sorted([24, 8, 10, 35])
print(a)
# [8, 10, 24, 35]
a.sort(reverse=True)
print(a)
# [35, 24, 10, 8]
b = sorted(a)
print(b)
# [8, 10, 24, 35]
c = sorted(a, reverse=True)
print(c)
# [35, 24, 10, 8]

  1. 上一篇文章:
  2. 下一篇文章:
Copyright © 程式師世界 All Rights Reserved