python: Sorting Algorithms

# encoding: utf-8
# 版权所有 2023 涂聚文有限公司
# 许可信息查看：Python Sorting Algorithms
# 描述： * https://www.programiz.com/dsa/counting-sort
#  * https://www.geeksforgeeks.org/sorting-algorithms/
# Author    : geovindu,Geovin Du 涂聚文.
# IDE       : PyCharm 2023.1 python 311
# Datetime  : 2023/9/21 21:55
# User      : geovindu
# Product   : PyCharm
# Project   : EssentialAlgorithms
# File      : SortingAlgorithms.py
# explain   : 学习import tkinter as tk
from tkinter import ttk
import itertools
import math
import sys
import os
from typing import Listclass SortingAlgorithms(object):"""排序算法"""def BubbleSort(array:list):"""1。Bubble Sort冒泡排序法:param array int数组:return:"""# loop to access each array elementfor i in range(len(array)):# loop to compare array elementsfor j in range(0, len(array) - i - 1):# compare two adjacent elements# change > to < to sort in descending orderif array[j] > array[j + 1]:# swapping elements if elements# are not in the intended ordertemp = array[j]array[j] = array[j + 1]array[j + 1] = tempdef BubbleSort2(array:list):"""1。Bubble Sort冒泡排序法:param array int数组:return:"""# loop through each element of arrayfor i in range(len(array)):# keep track of swappingswapped = False# loop to compare array elementsfor j in range(0, len(array) - i - 1):# compare two adjacent elements# change > to < to sort in descending orderif array[j] > array[j + 1]:# swapping occurs if elements# are not in the intended ordertemp = array[j]array[j] = array[j + 1]array[j + 1] = tempswapped = True# no swapping means the array is already sorted# so no need for further comparisonif not swapped:breakdef SelectionSort(array:list):"""2 python Program for Selection Sort 选择排序:param array int数组:return:"""for i in range(len(array)):# Find the minimum element in remaining# unsorted arraymin_idx = ifor j in range(i+1, len(array)):if array[min_idx] > array[j]:min_idx = j# Swap the found minimum element with# the first elementarray[i], array[min_idx] = array[min_idx], array[i]def InsertionSort(array:list):"""3 Insertion Sort插入排序:param array int数组:return:"""# Traverse through 1 to len(arr)for i in range(1, len(array)):key = array[i]# Move elements of arr[0..i-1], that are# greater than key, to one position ahead# of their current positionj = i - 1while j >= 0 and key < array[j]:array[j + 1] = array[j]j -= 1array[j + 1] = keydef Partition(array, low, high):""":param array int数组:param low::param high::return:"""# Choose the rightmost element as pivotpivot = array[high]# Pointer for greater elementi = low - 1# Traverse through all elements# compare each element with pivotfor j in range(low, high):if array[j] <= pivot:# If element smaller than pivot is found# swap it with the greater element pointed by ii = i + 1# Swapping element at i with element at j(array[i], array[j]) = (array[j], array[i])# Swap the pivot element with# the greater element specified by i(array[i + 1], array[high]) = (array[high], array[i + 1])# Return the position from where partition is donereturn i + 1def QuickSort(array, low, high):"""4 Quick Sort 快速排序:param array int数组:param low::param high::return:"""if low < high:# Find pivot element such that# element smaller than pivot are on the left# element greater than pivot are on the rightpi = SortingAlgorithms.Partition(array, low, high)# Recursive call on the left of pivotSortingAlgorithms.QuickSort(array, low, pi - 1)# Recursive call on the right of pivotSortingAlgorithms.QuickSort(array, pi + 1, high)def MergeSort(array:list):"""5 Merge Sort 合并/归并排序:param array int数组:return:"""if len(array) > 1:# Finding the mid of the arraymid = len(array) // 2# Dividing the array elementsL = array[:mid]# Into 2 halvesR = array[mid:]# Sorting the first halfSortingAlgorithms.MergeSort(L)# Sorting the second halfSortingAlgorithms.MergeSort(R)i = j = k = 0# Copy data to temp arrays L[] and R[]while i < len(L) and j < len(R):if L[i] <= R[j]:array[k] = L[i]i += 1else:array[k] = R[j]j += 1k += 1# Checking if any element was leftwhile i < len(L):array[k] = L[i]i += 1k += 1while j < len(R):array[k] = R[j]j += 1k += 1def CountingSort(array:list,hight:int):"""6 Counting Sort 计数排序:param array int数组:param hight 最大的整数 如100，数组中必须小数此数的整数:return:"""size = len(array)output = [0] * size# Initialize count arraydcount = [0] * hight# Store the count of each elements in count arrayprint(size)for i in range(0, size):dcount[array[i]] += 1# Store the cummulative count 最大的数for i in range(1, hight):dcount[i] += dcount[i - 1]# Find the index of each element of the original array in count array# place the elements in output arrayi = size - 1while i >= 0:output[dcount[array[i]] - 1] = array[i]dcount[array[i]] -= 1i -= 1# Copy the sorted elements into original arrayfor i in range(0, size):array[i] = output[i]def CountingSortTo(array: List[int]):"""6 Counting Sort 计数排序:param:return:"""max = min = 0for i in array:if i < min:min = iif i > max:max = icount = [0] * (max - min + 1)for j in range(max - min + 1):count[j] = 0for index in array:count[index - min] += 1index = 0for a in range(max - min + 1):for c in range(count[a]):array[index] = a + minindex += 1def countingSort(array, exp1):""":param array:param exp1::return:"""n = len(array)# The output array elements that will have sorted arroutput = [0] * (n)# initialize count array as 0count = [0] * (10)# Store count of occurrences in count[]for i in range(0, n):index = array[i] // exp1count[index % 10] += 1# Change count[i] so that count[i] now contains actual# position of this digit in output arrayfor i in range(1, 10):count[i] += count[i - 1]# Build the output arrayi = n - 1while i >= 0:index = array[i] // exp1output[count[index % 10] - 1] = array[i]count[index % 10] -= 1i -= 1# Copying the output array to arr[],# so that arr now contains sorted numbersi = 0for i in range(0, len(array)):array[i] = output[i]def RadixSort(array:list):"""7 Radix Sort 基数排序:param array:return:"""# Find the maximum number to know number of digitsmax1 = max(array)# Do counting sort for every digit. Note that instead# of passing digit number, exp is passed. exp is 10^i# where i is current digit numberexp = 1while max1 / exp >= 1:SortingAlgorithms.countingSort(array, exp)exp *= 10def insertionSort(array:list):""":return:"""for i in range(1, len(array)):up = array[i]j = i - 1while j >= 0 and array[j] > up:array[j + 1] = array[j]j -= 1array[j + 1] = upreturn arraydef BucketSort(array):"""8 Bucket Sort 桶排序:param array:return:"""arr = []slot_num = 10  # 10 means 10 slots, each# slot's size is 0.1for i in range(slot_num):arr.append([])# Put array elements in different bucketsfor j in array:index_b = int(slot_num * j)arr[index_b].append(j)# Sort individual bucketsfor i in range(slot_num):arr[i] = SortingAlgorithms.insertionSort(arr[i])# concatenate the resultk = 0for i in range(slot_num):for j in range(len(arr[i])):array[k] = arr[i][j]k += 1return array# Bucket Sort in Pythondef BucketSortTo(array:list):"""8 Bucket Sort 桶排序:param array:return:"""bucket = []# Create empty bucketsfor i in range(len(array)):bucket.append([])# Insert elements into their respective bucketsfor j in array:index_b = int(10 * j)bucket[index_b].append(j)# Sort the elements of each bucketfor i in range(len(array)):bucket[i] = sorted(bucket[i])# Get the sorted elementsk = 0for i in range(len(array)):for j in range(len(bucket[i])):array[k] = bucket[i][j]k += 1return arraydef heapify(array:list, Nsize:int, index:int):""":param array 数组:param Nsize: 数组长度:param index: 索引号:return:"""largest = index  # Initialize largest as rootl = 2 * index + 1  # left = 2*i + 1r = 2 * index + 2  # right = 2*i + 2# See if left child of root exists and is# greater than rootif l < Nsize and array[largest] < array[l]:largest = l# See if right child of root exists and is# greater than rootif r < Nsize and array[largest] < array[r]:largest = r# Change root, if neededif largest != index:array[index], array[largest] = array[largest], array[index]  # swap# Heapify the root.SortingAlgorithms.heapify(array, Nsize, largest)# The main function to sort an array of given sizedef HeapSort(array:list):"""9 Heap Sort 堆排序:param array:return:"""Nsize = len(array)# Build a maxheap.for i in range(Nsize // 2 - 1, -1, -1):SortingAlgorithms.heapify(array, Nsize, i)# One by one extract elementsfor i in range(Nsize - 1, 0, -1):array[i], array[0] = array[0], array[i]  # swapSortingAlgorithms.heapify(array, i, 0)def ShellSort(array:list):"""10 Shell Sort 希尔排序:param array 数组:return:"""# code herenszie=len(array)gap = nszie // 2while gap > 0:j = gap# Check the array in from left to right# Till the last possible index of jwhile j < nszie:i = j - gap  # This will keep help in maintain gap valuewhile i >= 0:# If value on right side is already greater than left side value# We don't do swap else we swapif array[i + gap] > array[i]:breakelse:array[i + gap], array[i] = array[i], array[i + gap]i = i - gap  # To check left side also# If the element present is greater than current elementj += 1gap = gap // 2def LinearSearch(array:list,fint:int):"""11 Linear Search线性搜索:param array 整数数组:param fint 要查找的数字:return:"""nsize=len(array)# Going through array sequenciallyfor i in range(0, nsize):if (array[i] == fint):return i  #找到了return -1 #未找到def BinarySearch(array:list, x, low, high):"""12 Binary Search  二分查找:param x::param low::param high::return:"""if high >= low:mid = low + (high - low) // 2# If found at mid, then return itif array[mid] == x:return mid# Search the left halfelif array[mid] > x:return SortingAlgorithms.BinarySearch(array, x, low, mid - 1)# Search the right halfelse:return SortingAlgorithms.BinarySearch(array, x, mid + 1, high)else:return -1def BingoSort(array, size):""":param array:param size::return:"""# Finding the smallest element From the Arraybingo = min(array)# Finding the largest element from the Arraylargest = max(array)nextBingo = largestnextPos = 0while bingo < nextBingo:# Will keep the track of the element position to# shifted to their correct positionstartPos = nextPosfor i in range(startPos, size):if array[i] == bingo:array[i], array[nextPos] = array[nextPos], array[i]nextPos += 1#  Here we are finding the next Bingo Element#  for the next passelif array[i] < nextBingo:nextBingo = array[i]bingo = nextBingonextBingo = largest

# encoding: utf-8
# 版权所有 2023 涂聚文有限公司
# 许可信息查看：
# 描述：
# Author    : geovindu,Geovin Du 涂聚文.
# IDE       : PyCharm 2023.1 python 311
# Datetime  : 2023/9/21 22:00
# User      : geovindu
# Product   : PyCharm
# Project   : EssentialAlgorithms
# File      : SortingExample.py
# explain   : 学习import ChapterOne.SortingAlgorithmsclass Example(object):""""实例"""def Bubble(self):"""1。Bubble Sort冒泡排序法:return:"""data = [-2, 45, 0, 11, -9]ChapterOne.SortingAlgorithms.SortingAlgorithms.BubbleSort(data)print('\n1 冒泡排序法 Bubble Sorted Array in Ascending Order:')for i in range(len(data)):print("%d" % data[i], end=" ")def Select(self):"""2 Selection Sort 选择排序:return:"""geovindu = [64, 25, 12, 22, 11]ChapterOne.SortingAlgorithms.SortingAlgorithms.SelectionSort(geovindu)print("\n2 选择排序Selection Sorted ")for i in range(len(geovindu)):print("%d" % geovindu[i], end=" ")def Insert(self):"""3 Insertion Sort插入排序:return:"""arr = [12, 11, 13, 5, 6]ChapterOne.SortingAlgorithms.SortingAlgorithms.InsertionSort(arr)print("\n3 插入排序 Insertion Sorted ")for i in range(len(arr)):print("% d" % arr[i], end=" ")def Quick(self):"""4 Quick Sort 快速排序:return:"""array = [10, 7, 8, 9, 1, 5]N = len(array)# Function callChapterOne.SortingAlgorithms.SortingAlgorithms.QuickSort(array, 0, N - 1)print("\n4 快速排序 Quick Sorted ")for x in array:print(x, end=" ")def Merge(self):"""5 Merge Sort  合并/归并排序:return:"""geovindu = [12, 11, 99, 13, 5, 6, 7,88,100]ChapterOne.SortingAlgorithms.SortingAlgorithms.MergeSort(geovindu)print("\n5 合并/归并排序 Merge Sorted ")for x in geovindu:print(x, end=" ")def Counting(self):"""6 Counting Sort 计数排序:return:"""geovindu = [17, 56, 71, 38, 61, 62, 48, 28, 57, 42]ChapterOne.SortingAlgorithms.SortingAlgorithms.CountingSortTo(geovindu)print("\n6 计数排序  Counting Sorted ")print(geovindu)for i in range(0,len(geovindu)):print("% d" % geovindu[i], end=" ")geovindu = [4, 55, 22, 98, 9, 43, 11]ChapterOne.SortingAlgorithms.SortingAlgorithms.CountingSort(geovindu, 100)print("\n6 计数排序  Counting Sorted ")for x in geovindu:print(x, end=" ")def Radix(self):"""7 Radix Sort 基数排序:return:"""geovindu = [170, 45, 75, 90, 802, 24, 2, 66]print("\n7 基数排序  Radix Sorted ")# Function CallChapterOne.SortingAlgorithms.SortingAlgorithms.RadixSort(geovindu)for i in range(len(geovindu)):print(geovindu[i], end=" ")def Bucket(self):"""8 Bucket Sort 桶排序:return:"""#geovindu = [170, 45, 75, 90, 802, 24, 2, 66]geovindu = [0.897, 0.565, 0.656,0.1234, 0.665, 0.3434]print("\n8 桶排序  Bucket Sorted ")# Function Calldu=ChapterOne.SortingAlgorithms.SortingAlgorithms.BucketSort(geovindu)for i in range(len(du)):print(du[i], end=" ")def Heap(self):"""9 Heap Sort 堆排序:return:"""geovindu = [170, 45, 75, 90, 802, 24, 2, 66]print("\n9 堆排序  Heap Sorted ")# Function CallChapterOne.SortingAlgorithms.SortingAlgorithms.HeapSort(geovindu)for i in range(len(geovindu)):print(geovindu[i], end=" ")def Shell(self):"""10 Shell Sort 希尔排序:return:"""geovindu = [170, 45, 75, 90, 802, 24, 2, 66]print("\n10 希尔排序  Shell Sorted ")# Function CallChapterOne.SortingAlgorithms.SortingAlgorithms.ShellSort(geovindu)for i in range(len(geovindu)):print(geovindu[i], end=" ")def Linear(self):"""11 Linear Search 线性搜索:return:"""array = [2, 4, 8,0, 1, 9]x = 8n = len(array)result = ChapterOne.SortingAlgorithms.SortingAlgorithms.LinearSearch(array,x)print("\n11 线性搜索  Linear Search ")if (result == -1):print("Element not found")else:print("Element found at index: ", result)def Binary(self):"""12 Binary Search  二分查找:return:"""array = [3, 4, 5, 6, 7, 8, 9]x = 4result = ChapterOne.SortingAlgorithms.SortingAlgorithms.BinarySearch(array, x, 0, len(array) - 1)print("\n12 二分查找  Binary Search ")if result != -1:print("Element is present at index " + str(result))else:print("Not found")def Bingo(self):"""13 Bingo Sort:return:"""arr = [5, 4, 8, 5, 4, 8, 5, 4, 4, 4]ChapterOne.SortingAlgorithms.SortingAlgorithms.BingoSort(arr, size=len(arr))print("\n13   Bingo Sorted ")for i in range(len(arr)):print(arr[i], end=" ")

调用：

    exm=BLL.SortingExample.Example()exm.Bubble()exm.Select()exm.Insert()exm.Quick()exm.Merge()exm.Counting()exm.Radix()exm.Bucket()exm.Heap()exm.Shell()exm.Linear()exm.Binary()exm.Bingo()