经典排序算法python实现

目录

• 直接插入排序
• 二分插入排序
• 希尔排序
• 冒泡排序
• 快速排序
• 简单选择排序
• 堆排序
• 归并排序
• 基数排序

1. 插入排序

• 直接插入排序

#!/usr/bin/env python
# -*- coding:UTF-8 -*-
# AUTHOR: YancyKahn
# FILE: D:\Work\408_863\DataStruct\Sorting\Insertion sort\base\main.py
# DATE: 2019/10/06 Sun
# TIME: 14:51:27

# DESCRIPTION: Generate infomation when a new file is created

#summary: Directly insertion sorting
#description: ascending
#argument:
#return:
#note:

class InsertionSort:
    def __init__(self, lst):
        self.lst = lst
    
    def Directly_insert_sorting(self):
        A = self.lst
        for i in range(1, len(A)):
            scout = A[i]
            j = i - 1

            while j > -1 and A[j] > A[i]:
                A[j + 1] = A[j]
                j = j - 1
            A[j + 1] = scout
        self.lst = A
        
    def show(self):
        return self.lst

if __name__ == "__name__":
    ist = InsertionSort([5, 4, 3, 2, 1])
    ist.Directly_insert_sorting()
    print(ist.show())

• 二分插入排序

#!/usr/bin/env python
# -*- coding:UTF-8 -*-
# AUTHOR: YancyKahn
# FILE: D:\Work\408_863\DataStruct\Sorting\Insertion sort\base1\main.py
# DATE: 2019/10/06 Sun
# TIME: 15:09:12

# DESCRIPTION: Generate infomation when a new file is created


#summary: binary insertion sorting
#description:
#argument:
#return:
#note:

class InsertSort:
    def __init__(self, lst):
        self.lst = lst

    def BinaryInsertSort(self):
        A = self.lst

        for i in range(1, len(A)):
            scout = A[i]
            
            low = 0
            high = i - 1

            #binary search
            while (low <= high):
                mid = (int)((low + high)/2)
                if (A[mid] > scout):
                     high = mid - 1
                else:
                     low = mid + 1

            j = i - 1
            while j > high:
                A[j + 1] = A[j]
                j = j - 1
            A[j + 1] = scout

            self.lst = A
    def show(self):
        return self.lst


if __name__ == "__main__":
    bst = InsertSort([5, 4, 3, 2, 1])
    print(bst.show())
    bst.BinaryInsertSort()
    print(bst.show())

• 希尔排序

#!/usr/bin/env python
# -*- coding:UTF-8 -*-
# AUTHOR: YancyKahn
# FILE: D:\Work\408_863\DataStruct\Sorting\Insertion sort\base2\main.py
# DATE: 2019/10/06 Sun
# TIME: 15:23:12

# DESCRIPTION: Generate infomation when a new file is created


#summary: shell sort
#description:
#argument:
#return:
#note:

class ShellSort:
    def __init__(self, lst):
        self.lst = lst
    
    def shell_sort(self):
        length = len(self.lst)
        gap = (int)(length/2)   #gap

        arr = self.lst
        while gap > 0:
            for i in range(gap, length):
                scout = arr[i]
                j = i
                
                while j >= gap and arr[j - gap] > scout:
                    arr[j] = arr[j - gap]
                    j -= gap

                arr[j] = scout

            gap = (int)(gap/2)
        self.lst = arr

    def show(self):
        return self.lst


if __name__ == "__main__":
    arr = [1, 2, 3, 4, 5]
    arr.reverse()
    sst = ShellSort(arr)
    print(sst.show())
    sst.shell_sort()
    print(sst.show())

2. 交换排序

• 冒泡排序

#!/usr/bin/env python
# -*- coding:UTF-8 -*-
# AUTHOR: YancyKahn
# FILE: D:\Work\408_863\DataStruct\Sorting\Swap sort\Bubble sort\base\main.py
# DATE: 2019/10/06 Sun
# TIME: 15:56:39

# DESCRIPTION: Generate infomation when a new file is created

#summary: bubble sort
#description:
#argument:
#return:
#note:


class BubbleSort:
    def __init__(self, lst):
        self.lst = lst
    
    def swap(self, i, j):
        tmp = self.lst[i]
        self.lst[i] = self.lst[j]
        self.lst[j] = tmp
    
    def sort(self):
        for i in range(len(self.lst)):
            for j in range(i, len(self.lst)):
                if self.lst[i] > self.lst[j]:
                    self.swap(i, j)
    
    def show(self):
        return self.lst

if __name__ == "__main__":
    bst = BubbleSort([5, 4, 3, 2, 1])
    print(bst.show())
    bst.sort()
    print(bst.show())

• 快速排序

#!/usr/bin/env python
# -*- coding:UTF-8 -*-
# AUTHOR: YancyKahn
# FILE: D:\Work\408_863\DataStruct\Sorting\Swap sort\Quick sort\base\main.py
# DATE: 2019/10/06 Sun
# TIME: 16:03:35

# DESCRIPTION: Generate infomation when a new file is created

#summary: quick sorting
#description:
#argument:
#return:
#note:

class QuickSort:
    def __init__(self, lst):
        self.lst = lst
    
    def partition(self, low, high):
        pivot = self.lst[low]

        while low < high:
            while low < high and self.lst[high] >= pivot:
                high = high - 1
            self.lst[low] = self.lst[high]
            while low < high and self.lst[low] <= pivot:
                low = low + 1
            self.lst[high] = self.lst[low]

        self.lst[low] = pivot
        return low

    def quick_sort_helper(self, low, high):
        if low < high:
            pivotpos = self.partition(low, high)
            self.quick_sort_helper(low, pivotpos - 1)
            self.quick_sort_helper(pivotpos + 1, high)

    def quick_sort(self):
        self.quick_sort_helper(0, len(self.lst) - 1)
    def show(self):
        return self.lst

if __name__ == "__main__":
    qst = QuickSort([5, 4, 3, 2, 1])
    print(qst.show())
    qst.quick_sort()
    print(qst.show())

3. 选择排序

• 简单选择排序

#!/usr/bin/env python
# -*- coding:UTF-8 -*-
# AUTHOR: YancyKahn
# FILE: D:\Work\408_863\DataStruct\Sorting\Select sort\Easy Select sort\base\main.py
# DATE: 2019/10/06 Sun
# TIME: 16:21:11

# DESCRIPTION: Generate infomation when a new file is created

#summary: easy select sorting
#description:
#argument:
#return:
#note:


class SelectSort:
    def __init__(self, lst):
        self.lst = lst
    
    def sort(self):
        for i in range(len(self.lst)):
            min = i
            for j in range(i + 1, len(self.lst)):
                if self.lst[i] > self.lst[j]:
                    min = j
            if min != i:
                self.lst[i], self.lst[min] = self.lst[min], self.lst[i] 
    
    def show(self):
        return self.lst

if __name__ == "__main__":
    sst = SelectSort([5, 4, 3, 2, 1])
    print(sst.show())
    sst.sort()
    print(sst.show())

• 堆排序

#!/usr/bin/env python
# -*- coding:UTF-8 -*-
# AUTHOR: YancyKahn
# FILE: D:\Work\408_863\DataStruct\Sorting\Select sort\Heap sort\base\main.py
# DATE: 2019/10/06 Sun
# TIME: 16:27:37

# DESCRIPTION: Generate infomation when a new file is created


#summary: heap sorting
#description:
#argument:
#return:
#note:

class HeapSort:
    def __init__(self, lst):
        self.lst = lst

    # adjust bigest element to root. in-ordering
    def traverse0(self, strat, end):
        root = strat
        
        while (root * 2 + 1) <= end:
            lchild = root * 2
            rchild = root * 2 + 1
            swap = root

            if self.lst[lchild] > self.lst[swap]:
                swap = lchild

            if self.lst[rchild] > self.lst[swap]:
                swap = rchild
            
            if swap != root:
                self.lst[swap], self.lst[root] = self.lst[root], self.lst[swap]
                root = swap
            else:
                return
    # adjust smallest element to root. in-ordering
    def traverse1(self, strat, end):
        root = strat
        
        while (root * 2 + 1) <= end:
            lchild = root * 2
            rchild = root * 2 + 1
            swap = root

            if self.lst[lchild] < self.lst[swap]:
                swap = lchild

            if self.lst[rchild] < self.lst[swap]:
                swap = rchild
            
            if swap != root:
                self.lst[swap], self.lst[root] = self.lst[root], self.lst[swap]
                root = swap
            else:
                return
    # mod = 0 --> big heap(default), mod = 1 small heap.
    def heapify(self, mod = 0):
        length = len(self.lst)
        start = (int)(length/2)
        while start > -1:
            print(self.show())
            if mod == 0:
                self.traverse0(start, length - 1)
            else:
                self.traverse1(start, length - 1)
            start -= 1

    # mod = 0 --> ascending, mod = 1 --> descending
    def sort(self, mod = 0):
        print("heapify: ")
        print("----------")
        self.heapify(mod)
        print(self.show())
        print("----------")
        if mod == 0:
            end = len(self.lst) - 1
            while end > 0:
                print(self.show())
                self.lst[end], self.lst[0] = self.lst[0], self.lst[end]
                end -= 1
                self.traverse0(0, end)
        else:
            end = len(self.lst) - 1
            while end > 0:
                print(self.show())
                self.lst[end], self.lst[0] = self.lst[0], self.lst[end]
                end -= 1
                self.traverse1(0, end)
 
    def show(self):
        return self.lst

if __name__ == "__main__":
    hst0 = HeapSort([5, 109, 87, 4, 50, 908, 65, 22, 1, 36])
    print("smallest heap:") 
    hst0.sort()
    print(hst0.show())

    hst1 = HeapSort([5, 109, 87, 4, 50, 908, 65, 22, 1, 36])
    print("bigest heap:")
    hst1.sort(mod = 1)
    print(hst1.show())

4. 其他排序

• 归并排序

#!/usr/bin/env python
# -*- coding:UTF-8 -*-
# AUTHOR: YancyKahn
# FILE: D:\Work\408_863\DataStruct\Sorting\Merge sort\base\main.py
# DATE: 2019/10/06 Sun
# TIME: 17:25:51

# DESCRIPTION: Generate infomation when a new file is created

#summary: merge sort
#description:
#argument:
#return:
#note:

class MergeSort:
    def __init__(self, lst):
        self.lst = lst
    
    def merge(self, left, right):
        leftcout, rightcout = 0, 0
        output = list()

        while leftcout < len(left) or rightcout < len(right):
            if leftcout < len(left) and rightcout < len(right):
                if left[leftcout] < right[rightcout]:
                    output.append(left[leftcout])
                    leftcout += 1
                else:
                    output.append(right[rightcout])
                    rightcout += 1
            
            if leftcout == len(left) and rightcout < len(right):
                output.append(right[rightcout])
                rightcout += 1
            elif rightcout == len(right) and leftcout < len(left):
                output.append(left[leftcout])
                leftcout += 1
        return output

    def merge_sort(self, a):
        midcount = len(a) // 2

        if len(a) > 1:
            left = self.merge_sort(a[midcount:])
            right = self.merge_sort(a[:midcount])
            return self.merge(left, right)
        return a

    def sort(self):
        a = self.merge_sort(self.lst)
        self.lst = a
    def show(self):
        return self.lst

if __name__ == "__main__":
    mst = MergeSort([3, 1, 4, 5, 6, 7, 8])
    print(mst.show())
    mst.sort()
    print(mst.show())

• 基数排序

#!/usr/bin/env python
# -*- coding:UTF-8 -*-
# AUTHOR: YancyKahn
# FILE: D:\Work\408_863\DataStruct\Sorting\Radix sort\base\main.py
# DATE: 2019/10/06 Sun
# TIME: 18:21:47

# DESCRIPTION: Generate infomation when a new file is created


#summary: Radix sort
#description:
#argument:
#return:
#note:

from collections import defaultdict
class RadixSort:
    def __init__(self, lst):
        self.lst = lst

    #radix sort
    def radix_sort(self, eps):
        bucket = defaultdict() #bucket
        output = list()
        for i in range(10):
            bucket.setdefault(i,[])
            
        for i in range(len(self.lst)):
            index = self.lst[i]//eps
            bucket[index%10].append(self.lst[i])

        # bucket sort
        for i in range(10):
            if len(bucket) != 0:
                for element in bucket[i]:
                    output.append(element)
        self.lst = output
        
    #sort
    def sort(self):
        
        max_value = max(self.lst)
        
        eps = 1
        while max_value//eps > 0:
            self.radix_sort(eps)
            eps *= 10

    def show(self):
        return self.lst


if __name__ == "__main__":
    rst = RadixSort([311, 492, 113, 425, 631, 828, 710])
    print(rst.show())
    rst.sort()
    print(rst.show())