[Python]排序算法

class Sort: 
    '''
    冒泡排序: 将最大的下沉到最后
    '''
    def bubbleSort(self, nums: [int] ) -> [int]:

        for i in range(len(nums)-1):
            flag = False
            for j in range(len(nums)-i-1):
                if nums[j] > nums[j+1]:
                    nums[j], nums[j+1] = nums[j+1], nums[j]
                    flag = True
            if not flag:
                break
        return nums

class Sort:
    '''
    选择排序: 选择局部最小 --> 减小范围 
    '''
    def selectionSort(self, nums:[int]) -> [int]:

        for i in range(len(nums)-1):
            for j in range(i+1, len(nums)):
                min_i = i
                if nums[j] < nums[min_i]:
                    min_i = j
            if min_i != i:
                nums[i], nums[min_i] = nums[min_i], nums[i]
        return nums

class Sort:
    '''
    插入排序: 逐个插入到正确的位置
    ''' 
    def insertionSort(self, nums:[int]) -> [int]:

        for i in range(1, len(nums)):
            temp = nums[i]
            j = i
            while j > 0 and nums[j-1] > temp:
                nums[j] = nums[j-1]
                j -= 1
            nums[j] = temp
        return nums

class Sort:
    '''
    希尔排序: 多次分组组内排序使得元素快速跳跃移动, 最后一次插入排序
    '''
    
    def shellSort(self, nums: [int]) -> [int]:
      
        gap = len(nums) // 2
        while gap:
            for i in range(gap, len(nums)):
                # gap -- len(nums) 位置的数进行插入, 不同的分组一起进行 
                temp = nums[i]
                j = i
                while j >= gap and nums[j-gap] > nums[j]:
                    nums[j], nums[j-gap] = nums[j-gap], nums[j]
                    j -= gap
                nums[j] = temp
            gap = gap // 2
        return nums

class Sort:
    '''
    合并排序: 分解合并
    '''
    def merge(sellf, left_nums: [int], right_nums: [int]) -> [int]:
        nums = []
        left_i, right_i = 0, 0
        while left_i < len(left_nums) and right_i < len(right_nums):
            if left_nums[left_i] < right_nums[right_i]:
                nums.append(left_nums[left_i])
                left_i += 1
            else:
                nums.append(right_nums[right_i])
                right_i += 1
        
        if left_i < len(left_nums): nums.append(nums[left_i:])
        else: nums.append(right_nums[right_i])
        return nums
    
    def mergeSort(self, nums:[int]) -> [int]:

        if len(nums) == 1:
            return nums
        mid = len(nums) // 2
        left_nums = self.mergeSort(nums[:mid])
        right_nums = self.mergeSort(nums[mid:])
        self.merge(left_nums, right_nums)
        return nums

class Sort:
    '''
    快速排序: 哨兵划分, 递归分解
    '''
    def randomPartition(self, nums:[int], low, high) -> int:
        i_pivot = random.randint(low, high)
        nums[low], nums[i_pivot] = nums[i_pivot], nums[low]
        pivot = nums[low]
        i, j = low, high
        while i < j:
            while i < j and nums[j] >= pivot:
                j -= 1
            while i < j and nums[i] <= pivot:
                i += 1
            nums[i], nums[j] = nums[j], nums[i]
        nums[low], nums[i] = nums[i], nums[low]
        return i

    def quickSort(self, nums:[int], low, high) -> [int]:
        if low < high:
            i_pivot = self.randomPartition(nums, low, high)
            self.quickSort(nums, low, i_pivot-1)
            self.quickSort(nums, i_pivot+1, high)
        return nums

    # 使用额外空间
class Sort:
    def quick_sort(self, arr: [int]) -> [int]:
        if len(arr) <= 1:
            return arr
        pivot = arr[0]  
        left = []
        right = []
        for x in arr[1:]:
            if x < pivot:
                left.append(x)
            else:
                right.append(x)
        return self.quick_sort(left) + [pivot] + self.quick_sort(right)

class MaxHeap:
    def __init__(self) -> None:
        self.max_heap = []
         
    def peek(self) -> int:
        if not self.max_heap:
            return None
        return self.max_heap[0]
    
    def push(self, val) -> None:
        self.max_heap.append(val)
        self.__shift_up(len(self.max_heap)-1)
        
    def __shift_up(self, i) -> None:
        while (i-1)//2 >= 0 and self.max_heap[(i-1)//2] < self.max_heap[i]:
             self.max_heap[(i-1)//2], self.max_heap[i] = self.max_heap[i], self.max_heap[(i-1)//2]
             i = (i-1)//2
    
    def pop(self) -> int:
        if not self.max_heap:
            raise('heap empty')
        size = len(self.max_heap)
        self.max_heap[0], self.max_heap[size-1] = self.max_heap[size-1], self.max_heap[0]
        val = self.max_heap.pop()
        size -= 1
        self.__shift_down(0, size)
        return val
    
    def __shift_down(self, i, size) -> None:
        while 2*i+1 < size:
            left, right = 2*i+1, 2*i+2
            if 2*i+2 >= size:
                larger = left
            else:
                if self.max_heap[left] >= self.max_heap[right]:
                    larger = left
                else:
                    larger = right
            
            if self.max_heap[i] >= self.max_heap[larger]:
                break
            else:
                self.max_heap[i], self.max_heap[larger] = self.max_heap[larger], self.max_heap[i]
                i = larger

    def get_heap(self) -> [int]:
        return self.max_heap
    
    def __buildMaxHeap(self, nums:[int]):
        size = len(nums)
        for i in range(size):
            self.max_heap.append(nums[i])
        for i in range((size-2)//2, -1, -1):
            self.__shift_down(i, size)

    def maxHeapSort(self, nums:[int]) -> [int]:
        self.__buildMaxHeap(nums)
        size = len(self.max_heap)
        for i in range(size-1, 0, -1):
            self.max_heap[0], self.max_heap[i] = self.max_heap[i], self.max_heap[0]
            self.__shift_down(0, i)
        return self.max_heap
    

# test
def main():
    heap = MaxHeap()
    # heap.push(2)
    # heap.push(3)
    # heap.push(1)
    # heap.push(5)
    # heap.push(4)
    # print(heap.get_heap())
    # heap.pop()
    # print(heap.get_heap())
    nums=[10, 25, 6, 8, 7, 1, 20, 23, 16, 19, 17, 3, 18, 14]
    print(heap.maxHeapSort(nums))

if __name__ == '__main__':
    main()

class Sort:
    '''
    计数排序: 统计后展开
    '''    
    def countingSort(self, nums:[int]) -> [int]:
        nums_min, nums_max = min(nums), max(nums)
        size = nums_max - nums_min + 1
        counts = [0 for _ in range(size)]
        
        for num in nums:
            counts[num-nums_min] += 1
        for i in range(1, size):
            counts[i] += counts[i-1]
            
        res = [0 for _ in range(len(nums))]    
        for i in range(len(nums)-1, -1, -1):
            num = nums[i]
            res[counts[num-nums_min]-1] = num
            counts[num-nums_min] -= 1
        return res

        # 逆序为了稳定排序, 正序遍历并且稳定也可以
        # counts[i] = count[i] + counts[i-1] - nums[i] + 1

class Sort:
    def count_sort(self, nums:[int]) -> [int]:
        '''
        另一种计数, 通过计算每个数有多少个数比它小
        '''
        size = len(nums) 
        res, rank = [0]*size, [0]*size
        for i in range(size):
            for j in range(i+1, size):
                if nums[i] > nums[j]:
                    rank[i] += 1
                else:
                    rank[j] += 1
        for i in range(size): res[rank[i]] = nums[i]
        return res

class Sort:
    '''
    桶排序: 分组入桶, 桶内排序, 合并
    '''
    def bucketSort(self, nums:[int], bucket_size:int) -> [int]:
        num_max, num_min = max(nums), min(nums)
        bucket_cnt = (num_max - num_min) // bucket_size + 1
        buckets = [[] for _ in range(bucket_cnt)]
        
        for num in nums:
            buckets[(num-num_min) // bucket_size].append(num)
        
        for bucket in buckets:
            self.selectionSort(bucket)
        
        return [num for bucket in buckets for num in bucket]

class Sort:
    '''
    基数排序: 根据相同位置上的数逐渐调整数组顺序
    '''
    def radixSort(self, nums:[int]) -> [int]:
    size = len(str(max(nums)))
    for i in range(size):
        buckets = [[] for _ in range(10)]
        for num in nums:
            buckets[num // 10**i % 10].append(num)
        nums = [num for bucket in buckets for num in bucket]
    return nums

from typing import Optional

# 链表节点
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

# 链表
class LinkedList:
    def __init__(self) -> None:
        self.dummy_head = None

    # 根据列表初始化链表
    def create(self, data):
        self.dummy_head = ListNode('-inf')
        cur = self.dummy_head
        for i in range(len(data)):
            node = ListNode(data[i])
            cur.next = node
            cur = cur.next
    
    # 获取线性链表长度
    def length(self):
        cnt = 0
        cur = self.dummy_head
        while cur:
            cnt += 1
            cur = cur.next
        return cnt
        
    # 查找元素
    def find(self, val):
        cur = self.dummy_head
        while cur:
            if val == cur.val:
                return cur
            cur = cur.next
        return None
    
    # 链表头部插入元素
    def insertFront(self, val):
        node = ListNode(val, self.dummy_head)
        self.dummy_head = node
    
    # 链表尾部插入元素
    def insertRear(self, val):
        node = ListNode(val)
        cur = self.dummy_head
        while cur:
            cur = cur.next
        cur.next = node
    
    # 链表中间插入元素
    def insertInside(self, idx, val):
        cur = self.dummy_head
        cnt = 0
        while cur and cnt < idx-1:
            cnt += 1
            cur = cur.next
        if not cur:
            return 'Error'
        node = ListNode(val, cur.next)
        cur.next = node
        
    # 改变元素
    def change(self, idx, val):
        cnt = 0
        cur = self.dummy_head
        while cur and cnt < idx:
            cnt += 1
            cur = cur.next
        if not cur:
            return 'Error'
        cur.val = val

    # 删除头部元素
    def removeFront(self):
        if self.dummy_head:
            self.dummy_head = self.dummy_head.next
    
    # 删除尾部元素
    def removeEnd(self):
        if not self.dummy_head or not self.dummy_head.next:
            return 'Error'
        cur = self.dummy_head
        while cur.next.next:
            cur = cur.next
        cur.next = None
    
    # 删除中间元素
    def removeInside(self, idx):
        cnt = 0
        cur = self.dummy_head
        while cur and cnt < idx-1:
            cnt += 1
            cur = cur.next
        if not cur: return 'Error'
        cur.next = cur.next.next

    # 打印链表
    def showList(self, head = None):
        if head:
            cur = head
        else:
            cur = self.dummy_head.next
        print('dummy_head', end= ' ')
        while cur:
            print('-->', cur.val, end=' ')
            cur = cur.next
        print()


        
def main(): 
    L = LinkedList()
    L.create(list(range(1, 5)))
    L.showList()
    L.removeEnd()
    L.showList()
    L.removeInside(2)
    L.showList()

if __name__ == "__main__":
    main()

from LinkedList import ListNode
from LinkedList import LinkedList
from typing import Optional

class LinkedListSort:
    @staticmethod
    def bubbleSort(head: ListNode):
        node_i = head
        tail = None
        while node_i.next:
            node_j = head
            flag = False
            while node_j and node_j.next != tail:
                if node_j.val > node_j.next.val:
                    node_j.val, node_j.next.val = node_j.next.val, node_j.val
                    flag = True
                node_j = node_j.next
            if not flag:
                return
            tail = node_j
            node_i = node_i.next
        return

    @staticmethod
    def selectSort(head: ListNode):
        node_i = head
        while node_i and node_i.next:
            min_node = node_i
            node_j = node_i.next
            while node_j:
                if node_j.val < min_node.val:
                    min_node = node_j
                node_j = node_j.next
            if min_node != node_i:
                min_node.val, node_i.val = node_i.val, min_node.val
            node_i = node_i.next
        return 
                
    @staticmethod
    def insertSort(head: ListNode) -> Optional[ListNode]:
        # 使用虚头节点, 可能插入到头部
        if not head or not head.next:
            return head
        dummy_head = ListNode(-1, head)
        sorted_list = head
        curr = head.next
        while curr:
            if curr.val >= sorted_list.val:
                sorted_list = sorted_list.next
            else:
                prev = dummy_head
                while prev.next.val <= curr.val:
                    prev = prev.next
                sorted_list.next = curr.next
                curr.next = prev.next
                prev.next = curr
            curr = sorted_list.next
        return dummy_head.next
                  
    @staticmethod
    def merge(left: ListNode, right: ListNode):
        dummy_head = ListNode(-1)
        curr = dummy_head
        while left and right:
            if left.val <= right.val:
                curr.next = left
                left = left.next
            else:
                curr.next = right
                right = right.next
            curr = curr.next
        if left:
            curr.next = left
        elif right:
            curr.next = right
        return dummy_head.next
    
    @staticmethod
    def mergeSort(head: ListNode):
        if not head or not head.next: return head
        left, right = head, head.next
        while right and right.next:
            left = left.next
            right = right.next.next
        left_head, right_head = head, left.next
        left.next = None
        
        return LinkedListSort.merge(LinkedListSort.mergeSort(left_head), LinkedListSort.mergeSort(right_head))
    
    @staticmethod
    def partition(left: ListNode, right: ListNode):
        if left == right or left.next == right: return left
        pivot = left.val
        node_i, node_j = left, left.next
        while node_j != right:
            if node_j.val < pivot:
                node_i = node_i.next
                node_i.val, node_j.val = node_j.val, node_i.val
            node_j = node_j.next
        left.val, node_i.val = node_i.val, left.val
        return node_i
    @staticmethod
    def quickSort(left: ListNode, right: Optional[ListNode]):
        if left == right or left.next == right: return left
        pi = LinkedListSort.partition(left, right)
        LinkedListSort.quickSort(left, pi)
        LinkedListSort.quickSort(pi.next, right)
        return left
    
    @staticmethod
    def countingSort(head: ListNode):
        # 只能针对整数, 因为区间长度必须有限
        list_min, list_max = float('inf'), float('-inf')
        curr = head
        while curr:
            if curr.val < list_min:
                list_min = curr.val
            elif curr.val > list_max:
                list_max = curr.val
            curr = curr.next

        size = list_max - list_min + 1
        curr = head
        counts = [ 0 for _ in range(size)]
        while curr:
            counts[curr.val-list_min] += 1
            curr = curr.next
        print(counts, size, list_min)
        # 构造链表与构造数组不同, 链表从头结点开始, 数组则可以随机访问置值
        dummy_head = ListNode(-1)
        curr = dummy_head
        for i in range(size):
            while counts[i]:
                curr.next = ListNode(i+list_min)
                counts[i] -= 1
                curr = curr.next
        return dummy_head.next
    
    @staticmethod
    def putinBucket(buckets, idx, val):
        if not buckets[idx]:
            buckets[idx] = ListNode(val) 
            return
        node = ListNode(val, buckets[idx])
        buckets[idx] = node
    
    @staticmethod
    def bucketSort(head: ListNode, bucket_size = 5):
        if not head: return head
        list_min, list_max = float('inf'), float('-inf')
        curr = head
        while curr:
            if curr.val < list_min:
                list_min = curr.val
            elif curr.val > list_max:
                list_max = curr.val
            curr = curr.next
        bucket_cnts = (list_max-list_min) // bucket_size + 1
        buckets = [None for _ in range(bucket_cnts)]
    
        # 放入桶中
        curr = head
        while curr:
            idx = (curr.val-list_min) // bucket_size
            LinkedListSort.putinBucket(buckets, idx, curr.val)
            curr = curr.next
        
        # 排序并组装成链表
        dummy_head = ListNode(-1)
        curr = dummy_head
        for bucket_head in buckets:
            bucket_curr = LinkedListSort.mergeSort(bucket_head)
            while bucket_curr:
                curr.next = bucket_curr
                bucket_curr = bucket_curr.next
                curr = curr.next
        return dummy_head.next
    
    def radixSort(head: ListNode):
        # 基数排序, 只适用于N+
        max_len = 0
        curr = head
        while curr:
            max_len = max(max_len, len(str(curr.val)))
            curr = curr.next
        
        for i in range(max_len):
            curr = head
            buckets = [[] for i in range(10)]
            while curr:
                buckets[curr.val // (10**i) % 10].append(curr.val)
                curr = curr.next
            
            dummy_head = ListNode(-1)
            curr = dummy_head
            for bucket in buckets:
                for num in bucket:
                    curr.next = ListNode(num)
                    curr = curr.next
            head = dummy_head.next
        return head
        
    
L = LinkedList()
L.create([5, 3, 4, 2, 1, 7, 6, 8, 9])
# LinkedListSort.bubbleSort(L.dummy_head.next)
# LinkedListSort.selectSort(L.dummy_head.next)
# LinkedListSort.insertSort(L.dummy_head.next)
# LinkedListSort.mergeSort(L.dummy_head.next)
# LinkedListSort.quickSort(L.dummy_head.next, None)
# L.showList()
# res = LinkedListSort.countingSort(L.dummy_head.next)
# L.showList(res)

# res = LinkedListSort.bucketSort(L.dummy_head.next)
# L.showList(res)    

res = LinkedListSort.radixSort(L.dummy_head.next)
L.showList(res)