数据结构~七大经典内排序之Python实现
插入排序 冒泡排序 选择排序 【平均时间复杂度O(n*n)】
快速排序 堆排序 归并排序 【平均时间复杂度O(n*log(n))】
计数排序 【平均时间复杂度O(n)】
插入排序冒泡排序
def insertSort(nums):
lens_nums = len(nums)
if lens_nums <= 1:
return nums
for i in range(1,lens_nums):
for j in range(i,0,-1):
if nums[j] < nums[j-1]:
tmp = nums[j]
nums[j] = nums[j-1]
nums[j-1] = tmp
return nums
'选择排序
def selectionSort(nums):
lens = len(nums)
if lens <= 1:
return nums
for i in range(lens-1):
min_ind = i
for j in range(i+1,lens):
if nums[j] < nums[min_ind]:
min_ind = j
if min_ind != i:
tmp = nums[i]
nums[i] = nums[min_ind]
nums[min_ind] = tmp
return nums
nums = [1,2,3,4,5,6,7]
print(selectionSort(nums))
'快速排序
nums1 = [4,5,7,8,1,2,6]
def quickSort(nums,low,high):
p = low
while low <= high:
while high>0 and nums[high] >= nums[p]:
high -= 1
while low<len(nums) and nums[low] <= nums[p]:
low += 1
if low < high:
t = nums[low]
nums[low] = nums[high]
nums[high] = t
if high != p:
tmp = nums[p]
nums[p] = nums[high]
nums[high] = tmp
return high
def QuickSort(nums,low,high):
if low < high:
mid = quickSort(nums,low,high)
QuickSort(nums,low,mid-1)
QuickSort(nums,mid+1,high)
QuickSort(nums1,0,6)
print(nums1)
'堆排序
'''
Heap是一种数据结构具有以下的特点：
1）完全二叉树；
2）heap中存储的值是偏序；
Min-heap: 父节点的值小于或等于子节点的值；
Max-heap: 父节点的值大于或等于子节点的值；
已知某个节点索引为i,
其父亲节点索引为：(i-1)/2
其左孩子节点为：2*i+1
其右孩子节点为:2*i+2
构建大根堆需要从 (len(nums)-1-1)/2开始做比较
'''
def swap(nums,i,j):
'''交换数据'''
tmp = nums[i]
nums[i] = nums[j]
nums[j] = tmp
def heapy(nums,n,index):
'''
n:数组中元素的个数
index:从某个节点进行构建大/小根堆
'''
if index < n:
left = index * 2 + 1
right = index * 2 + 2
max_ind = index
if left < n and nums[left] > nums[max_ind]:
max_ind = left
if right < n and nums[right] > nums[max_ind]:
max_ind = right
if max_ind != index:
swap(nums,max_ind,index)
heapy(nums,n,max_ind)
def buildHeap(nums,n):
index = (n-2) // 2
for j in range(index,-1,-1):
heapy(nums,n,j)
def heapSort(nums,n):
buildHeap(nums,n)
for i in range(n-1,-1,-1):
swap(nums,i,0)
heapy(nums,i,0)
nums = [5,4,0,7,8,3]
heapSort(nums,len(nums))
print(nums)
'归并排序
def merge(nums,left,right,mid):
tmp = []
i = left
j = mid+1
while i <= mid and j <= right:
if nums[i] < nums[j]:
tmp.append(nums[i])
i += 1
else:
tmp.append(nums[j])
j += 1
while i <= mid:
tmp.append(nums[i])
i += 1
while j <= right:
tmp.append(nums[j])
j+=1
for i in range(len(tmp)):
nums[left] = tmp[i]
left += 1
def MergeSort(nums,left,right):
if left < right:
mid = (left + right) // 2
MergeSort(nums,left,mid)
MergeSort(nums,mid+1,right)
merge(nums,left,right,mid)
nums = [1,2,4,7,8,4,5,6,2]
MergeSort(nums,0,8)
print(nums)
'计数排序
def countSort(nums):
SortedA = []
len_nums = len(nums)
max_val = nums[0]
for i in range(len_nums):
if nums[i] > max_val:
max_val = nums[i]
Aux = [0 for i in range(max_val+1)]
for i in range(len_nums):
Aux[nums[i]] += 1
for i in range(max_val+1):
tmp = Aux[i]
for j in range(tmp,0,-1):
SortedA.append(i)
return SortedA
nums = [0,7,5,8,9,7,4]
n = countSort(nums)
print(n)
'相关知识
Python基础练习题100道电子版及源码文件
Python之函数
Python Leetcode(905.按奇偶排序数组)
Python宠物美容项目预约服务管理系统设计与实现
今天我开始学习:PETSHOP3.0宠物商店（经典案例）
Python学习手册
Java项目实战II基于Java+Spring Boot+MySQL的宠物咖啡馆平台的设计与实现(源码+数据库+文档)
基于Java的宠物猫个性化服务APP设计与实现源码.zip资源
OPENWRT
使用python实现图像对比度增强
网址: 数据结构~七大经典内排序之Python实现 https://m.mcbbbk.com/newsview548276.html
| 上一篇: 《宠一夏》宠物品牌视觉形象设计 |
下一篇: 猫咪的这四样东西让你触碰吗？尤其 |
