# encoding: utf-8
# Author : geovindu,Geovin Du 涂聚文.
# IDE : PyCharm 2023.1 python 11
# Datetime : 2023/7/2 20:25
# User : geovindu
# Product : PyCharm
# Project : pythonStudyDemo
# File : TenSortAlgotrthms.py
# explain : 学习 十种排序 https://www.sitepoint.com/best-sorting-algorithms/ python javascript
from enum import Enum
import sortingalgorithms.CheckSort
import sortingalgorithms.duplicateChecking
from heapq import heappop, heappush
class TenSortAlgotrthms(object):
"""
"""
def bubbleSort(self,arr):
"""
1。冒泡排序方法bubble Sort 从小至大 升序
:param arr 整数数组 如 arr = [64, 34, 25, 12, 22, 11, 90]
:return:
"""
n = len(arr)
swapped = False
for i in range(n - 1):
for j in range(0, n - i - 1):
if arr[j] > arr[j + 1]:
swapped = True
arr[j], arr[j + 1] = arr[j + 1], arr[j]
if not swapped:
return
def bubbleSort(self,arr,checkSort=None):
"""
1。冒泡排序方法 从小至大 升序
:param arr 整数数组 如 arr = [64, 34, 25, 12, 22, 11, 90]
:param checkSort选择排序方式 Desc 降序 Asc 升序
:return:
"""
n = len(arr)
swapped = False
if(checkSort!=None):
if(checkSort.Asc==sortingalgorithms.CheckSort.CheckSort.Desc):
for i in range(n - 1):
for j in range(0, n - i - 1):
if arr[j] > arr[j + 1]:
swapped = True
arr[j], arr[j + 1] = arr[j + 1], arr[j]
if not swapped:
return
else:
for i in range(n - 1):
for j in range(0, n - i - 1):
if arr[j] < arr[j + 1]:
swapped = True
arr[j], arr[j + 1] = arr[j + 1], arr[j]
if not swapped:
return
else:
for i in range(n - 1):
for j in range(0, n - i - 1):
if arr[j] > arr[j + 1]:
swapped = True
arr[j], arr[j + 1] = arr[j + 1], arr[j]
if not swapped:
return
def bubbleSortIndex(self, arr, checkSort, eqLeter : int):
"""
1。冒泡排序方法 bubble Sort 从小至大 升序
:param arr 整数数组 如 arr = [64, 34, 25, 12, 22, 11, 90]
:param checkSort选择排序方式 Desc 降序 Asc 升序
:param eqLeter 找查指定的数字的下标
:return:返回下标 元组
"""
n = len(arr)
fin = sortingalgorithms.duplicateChecking.DuplicateChecking()
index = fin.findindex(arr, eqLeter)
# print("index" ,index ,eqLeter)
swapped = False
if(checkSort.Asc == sortingalgorithms.CheckSort.CheckSort.Desc):
for i in range(n - 1):
for j in range(0, n - i - 1):
if arr[j] > arr[j + 1]:
swapped = True
arr[j], arr[j + 1] = arr[j + 1], arr[j]
if not swapped:
return index
else:
for i in range(n - 1):
for j in range(0, n - i - 1):
if arr[j] < arr[j + 1]:
swapped = True
arr[j], arr[j + 1] = arr[j + 1], arr[j]
if not swapped:
return index
def insertionSort(self,items:list):
"""
2 插入排序（Insertion Sort） items = [6,20,8,19,56,23,87,41,49,53]
print(insertionSort(items))
:param items
:return:
"""
for i in range(1, len(items)):
j = i
while j > 0 and items[j-1] > items[j]:
items[j-1], items[j] = items[j], items[j-1]
j -= 1
return items
def quickSort(self,items:list):
"""
3 快速排序（Quick Sort） quick Sort items = [6,20,8,19,56,23,87,41,49,53]
print(quickSort(items))
:param items
:return:
"""
if len(items) > 1:
pivot = items[0]
left = [i for i in items[1:] if i < pivot]
right = [i for i in items[1:] if i >= pivot]
return self.quickSort(left) + [pivot] + self.quickSort(right)
else:
return items
def bucketSort(self,items:list):
"""
4 桶排序（Bucket Sort) Bucket sort items = [6,20,8,19,56,23,87,41,49,53]
print(bucketSort(items))
:param items:
:return:
"""
buckets = [[] for _ in range(len(items))]
for item in items:
bucket = int(item/len(items))
buckets[bucket].append(item)
for bucket in buckets:
bucket.sort()
return [item for bucket in buckets for item in bucket]
def shellSort(self,items:list):
"""
5 希尔排序（Shell Sort）items = [6,20,8,19,56,23,87,41,49,53]
print(shellSort(items))
:param items:
:return:
"""
sublistcount = len(items)//2
while sublistcount > 0:
for start in range(sublistcount):
self.gap_insertion_sort(items, start, sublistcount)
sublistcount = sublistcount // 2
return items
def gap_insertion_sort(self,items:list, start, gap):
"""
:param items:
:param start:
:param gap:
:return:
"""
for i in range(start+gap, len(items), gap):
currentvalue = items[i]
position = i
while position >= gap and items[position-gap] > currentvalue:
items[position] = items[position-gap]
position = position-gap
items[position] = currentvalue
def mergeSort(self,items:list):
"""
6.归并排序（Merge Sort）items = [6,20,8,19,56,23,87,41,49,53]
print(mergeSort(items))
:param items:
:return:
"""
if len(items) <= 1:
return items
mid = len(items) // 2
left = items[:mid]
right = items[mid:]
left = self.mergeSort(left)
right = self.mergeSort(right)
return self.merge(left, right)
def merge(self,left, right):
"""
:param left:
:param right:
:return:
"""
merged = []
left_index = 0
right_index = 0
while left_index < len(left) and right_index < len(right):
if left[left_index] > right[right_index]:
merged.append(right[right_index])
right_index += 1
else:
merged.append(left[left_index])
left_index += 1
merged += left[left_index:]
merged += right[right_index:]
return merged
def selectionSort(self,items:list):
"""
7 选择排序（Selection Sort）items = [6,20,8,19,56,23,87,41,49,53]
print(selectionSort(items))
:param items:
:return:
"""
for i in range(len(items)):
min_idx = i
for j in range(i + 1, len(items)):
if items[min_idx] > items[j]:
min_idx = j
items[i], items[min_idx] = items[min_idx], items[i]
return items
def radixSort(self,items:list):
"""
8 基数排序（Radix Sort）items = [6,20,8,19,56,23,87,41,49,53]
print(radixSort(items))
:param items:
:return:
"""
max_length = False
tmp, placement = -1, 1
while not max_length:
max_length = True
buckets = [list() for _ in range(10)]
for i in items:
tmp = i // placement
buckets[tmp % 10].append(i)
if max_length and tmp > 0:
max_length = False
a = 0
for b in range(10):
buck = buckets[b]
for i in buck:
items[a] = i
a += 1
placement *= 10
return items
def combSort(self,items:list):
"""
9 梳排序(Comb sort)（梳排序是一种不稳定排序算法，改良自泡沫排序和快速排序。其目的是消除阵列尾部的小数值，提高排序效率）
:param items:
:return:
"""
gap = len(items)
shrink = 1.3
sorted = False
while not sorted:
gap //= shrink
if gap <= 1:
sorted = True
else:
for i in range(len(items) - gap):
if items[i] > items[i + gap]:
items[i], items[i + gap] = items[i + gap], items[i]
return self.bubble_sort(items)
def bubble_sort(self,items:list):
"""
:param items:
:return:
"""
for i in range(len(items)):
for j in range(len(items) - 1 - i):
if items[j] > items[j + 1]:
items[j], items[j + 1] = items[j + 1], items[j]
return items
def insertionSort(self,arr, left=0, right=None):
"""
:param arr:
:param left:
:param right:
:return:
"""
if right is None:
right = len(arr) - 1
for i in range(left + 1, right + 1):
key_item = arr[i]
j = i - 1
while j >= left and arr[j] > key_item:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key_item
return arr
def merge(self,left, right):
"""
:param left:
:param right:
:return:
"""
if not left:
return right
if not right:
return left
if left[0] < right[0]:
return [left[0]] + self.imerge(left[1:], right)
return [right[0]] + self.imerge(left, right[1:])
def timSort(self,arr):
"""
10 TimSort是结合了合并排序（合并排序）和插入排序（插入排序）而得出的排序算法，它在现实中有很好的效率.Tim Peters在2002年设计了该算法并在Python中使用是Python中list.sort的默认实现）。
items = [6,20,8,19,56,23,87,41,49,53]
print(timsort(items))
:param arr:
:return:
"""
min_run = 32
n = len(arr)
for i in range(0, n, min_run):
self.insertionSort(arr, i, min((i + min_run - 1), n - 1))
size = min_run
while size < n:
for start in range(0, n, size * 2):
midpoint = start + size - 1
end = min((start + size * 2 - 1), (n - 1))
merged_array = self.imerge(
left=arr[start:midpoint + 1],
right=arr[midpoint + 1:end + 1]
)
arr[start:start + len(merged_array)] = merged_array
size *= 2
return arr
def countingSort(self,inputArray):
"""
11 计数排序(Counting sort)inputArray = [2,2,0,6,1,9,9,7]
print("Input array = ", inputArray) sortedArray = countingSort(inputArray)
print("Counting sort result = ", sortedArray)
:return:
"""
# Find the maximum element in the inputArray
maxElement = max(inputArray)
countArrayLength = maxElement + 1
# Initialize the countArray with (max+1) zeros
countArray = [0] * countArrayLength
# Step 1 -> Traverse the inputArray and increase
# the corresponding count for every element by 1
for el in inputArray:
countArray[el] += 1
# Step 2 -> For each element in the countArray,
# sum up its value with the value of the previous
# element, and then store that value
# as the value of the current element
for i in range(1, countArrayLength):
countArray[i] += countArray[i - 1]
# Step 3 -> Calculate element position
# based on the countArray values
outputArray = [0] * len(inputArray)
i = len(inputArray) - 1
while i >= 0:
currentEl = inputArray[i]
countArray[currentEl] -= 1
newPosition = countArray[currentEl]
outputArray[newPosition] = currentEl
i -= 1
return outputArray
def heapSort(self,array:list):
"""
12 堆排序（Heap Sort）array = [13, 21, 15, 5, 26, 4, 17, 18, 24, 2]
print(heap_sort(array))
:param array:
:return:
"""
heap = []
for element in array:
heappush(heap, element)
ordered = []
# While we have elements left in the heap
while heap:
ordered.append(heappop(heap))
return ordered
标签：Sort,arr,return,python,items,self,param,range,Algotrthms From： https://www.cnblogs.com/geovindu/p/17530529.html