Add files via upload

linwt · web-flow · commit 44f17a1d7651 · 2019-03-30T20:17:00.000+08:00
diff --git a/十大排序算法/01.冒泡排序.py b/十大排序算法/01.冒泡排序.py
@@ -0,0 +1,13 @@
+# 外循环控制循环次数，内循环控制左右元素两两比较，若第一个大于第二个则交换位置，最终最大的元素会放在最右边
+# 除去最后一个元素，对剩余元素重复以上循环
+def bubble_sort(nums):
+    for i in range(1, len(nums)-1):
+        for j in range(len(nums)-i):
+            if nums[j] > nums[j+1]:
+                nums[j], nums[j+1] = nums[j+1], nums[j]
+    return nums
+
+
+if __name__ == '__main__':
+    nums = [2, 1, 6, 7, 9, 5, 0, 4, 3, 8]
+    print(bubble_sort(nums))
diff --git a/十大排序算法/02.选择排序.py b/十大排序算法/02.选择排序.py
@@ -0,0 +1,15 @@
+# 外循环控制循环次数，内循环查找出最小元素，并与第一个元素交换位置
+# 除去第一个元素，对剩余元素重复以上循环
+def select_sort(nums):
+    for i in range(len(nums)-1):
+        min_index = i
+        for j in range(i+1, len(nums)):
+            if nums[j] < nums[min_index]:
+                min_index = j
+        nums[min_index], nums[i] = nums[i], nums[min_index]
+    return nums
+
+
+if __name__ == '__main__':
+    nums = [2, 1, 6, 7, 9, 5, 0, 4, 3, 8]
+    print(select_sort(nums))
diff --git a/十大排序算法/03.插入排序.py b/十大排序算法/03.插入排序.py
@@ -0,0 +1,15 @@
+# 从左往右遍历每个元素，将遍历到的元素插入到该元素左边序列中，且位置在从右往左第一个小于等于该元素的元素右边
+def insert_sort(nums):
+    if len(nums) < 2:
+        return nums
+    for i in range(1, len(nums)):
+        j = i
+        while j > 0 and nums[j] < nums[j-1]:
+            nums[j], nums[j-1] = nums[j-1], nums[j]
+            j -= 1
+    return nums
+
+
+if __name__ == '__main__':
+    nums = [2, 1, 6, 7, 9, 5, 0, 4, 3, 8]
+    print(insert_sort(nums))
diff --git a/十大排序算法/04.希尔排序.py b/十大排序算法/04.希尔排序.py
@@ -0,0 +1,16 @@
+#  把元素按下标的一定增量分组，对每组使用直接插入排序算法排序
+def shell_sort(nums):
+    n = len(nums)
+    gap = n // 2
+    while gap > 0:
+        for i in range(gap, n):
+            while i >= gap and nums[i] < nums[i-gap]:
+                nums[i], nums[i-gap] = nums[i-gap], nums[i]
+                i -= gap
+        gap //= 2
+    return nums
+
+
+if __name__ == '__main__':
+    nums = [2, 1, 6, 7, 9, 5, 0, 4, 3, 8]
+    print(shell_sort(nums))
diff --git a/十大排序算法/05.归并排序.py b/十大排序算法/05.归并排序.py
@@ -0,0 +1,28 @@
+# 将数组分解最小，然后依次合并两个有序数组
+# 合并思路：比较两个数组的最左边的数，取较小者，取了后相应的指针往右移一位。继续比较，直至一个数组为空，最后复制另一个数组的剩余部分
+def merge_sort(nums):
+    if len(nums) < 2:
+        return nums
+    left = merge_sort(nums[:len(nums)//2])
+    right = merge_sort(nums[len(nums)//2:])
+    return merge(left, right)
+
+
+def merge(left, right):
+    l = r = 0
+    res = []
+    while l < len(left) and r < len(right):
+        if left[l] < right[r]:
+            res.append(left[l])
+            l += 1
+        else:
+            res.append(right[r])
+            r += 1
+    res += left[l:]
+    res += right[r:]
+    return res
+
+
+if __name__ == '__main__':
+    nums = [2, 1, 6, 7, 9, 5, 0, 4, 3, 8]
+    print(merge_sort(nums))
diff --git a/十大排序算法/06.快速排序.py b/十大排序算法/06.快速排序.py
@@ -0,0 +1,43 @@
+# 先在数组中挑出一个“基准”元素，比它小的放左边，比它大的放右边
+
+# 逐一赋值形式
+def quick_sort(nums):
+    l, r = 0, len(nums)-1
+    # 数组为空或只有一个元素
+    if l >= r:
+        return nums
+    key = nums[l]
+    while l < r:
+        while l < r and nums[r] >= key:
+            r -= 1
+        nums[l] = nums[r]
+        while l < r and nums[l] <= key:
+            l += 1
+        nums[r] = nums[l]
+    nums[l] = key
+    l_nums = quick_sort(nums[:l])
+    r_nums = quick_sort(nums[l+1:])
+    return l_nums + [key] + r_nums
+
+
+# 两者交换形式
+def quick_sort2(nums):
+    l, r = 0, len(nums)-1
+    if l >= r:
+        return nums
+    p = l
+    while l < r:
+        while l < r and nums[r] >= nums[p]:
+            r -= 1
+        while l < r and nums[l] <= nums[p]:
+            l += 1
+        nums[r], nums[l] = nums[l], nums[r]
+    nums[l], nums[p] = nums[p], nums[l]
+    l_nums = quick_sort(nums[:l])
+    r_nums = quick_sort(nums[l+1:])
+    return l_nums + [nums[l]] + r_nums
+
+
+if __name__ == '__main__':
+    nums = [2, 1, 6, 7, 9, 5, 0, 4, 3, 8]
+    print(quick_sort(nums))
diff --git a/十大排序算法/07.堆排序.py b/十大排序算法/07.堆排序.py
@@ -0,0 +1,38 @@
+def heap_sort(nums):
+    n = len(nums)
+    # 最后一个有子节点的结点的索引
+    first = n//2-1
+    # 构造最大堆。逐个有子节点的结点进行调整
+    for start in range(first, -1, -1):
+        max_heapify(nums, start, n-1)
+    # 将最大堆转化成有序数组
+    for end in range(n-1, 0, -1):
+        # 最后一个元素与第一个交换位置
+        nums[end], nums[0] = nums[0], nums[end]
+        # 交换后排除最后一个元素，重新调整成最大堆
+        max_heapify(nums, 0, end-1)
+    return nums
+
+
+# 最大堆调整。子节点较大者与父节点交换
+def max_heapify(nums, start, end):
+    root = start
+    # 父节点交换下来后判新子节点是否还可继续交换
+    while True:
+        child = 2*root+1
+        if child > end:
+            break
+        # 获取较大子节点
+        if child+1 <= end and nums[child] < nums[child+1]:
+            child += 1
+        # 较大子节点成为父节点
+        if nums[child] > nums[root]:
+            nums[child], nums[root] = nums[root], nums[child]
+            root = child
+        else:
+            break
+
+
+if __name__ == '__main__':
+    nums = [2, 1, 6, 7, 9, 5, 0, 4, 3, 8]
+    print(heap_sort(nums))
diff --git a/十大排序算法/08.计数排序.py b/十大排序算法/08.计数排序.py
@@ -0,0 +1,20 @@
+def count_sort(nums):
+    max_num, min_num = max(nums), min(nums)
+    count = [0] * (max_num - min_num + 1)
+    res = [0] * len(nums)
+    # 记录每个元素出现次数
+    for num in nums:
+        count[num-min_num] += 1
+    # 加上前一元素值，此时每个元素的含义是包括当前元素在内有多少个元素在桶里
+    for i in range(1, len(count)):
+        count[i] += count[i-1]
+    # 获取每个元素在最终数组中对应位置索引并存入
+    for num in nums:
+        res[count[num-min_num]-1] = num
+        count[num-min_num] -= 1
+    return res
+
+
+if __name__ == '__main__':
+    nums = [2, 1, 8, 9, 9, 5, 9, 4, 4, 8]
+    print(count_sort(nums))
diff --git a/十大排序算法/09.桶排序.py b/十大排序算法/09.桶排序.py
@@ -0,0 +1,16 @@
+# 获取数组最大值和最小值并构建在该范围的数组长度，数组记录元素出现的个数，最后遍历数组获取对应个数的元素
+def bucket_sort(nums):
+    max_num, min_num = max(nums), min(nums)
+    count = [0 for _ in range(min_num, max_num+1)]
+    res = []
+    for num in nums:
+        count[num-min_num] += 1
+    for index in range(len(count)):
+        if count[index] != 0:
+            res += [index+min_num] * count[index]
+    return res
+
+
+if __name__ == '__main__':
+    nums = [2, 1, 8, 9, 9, 5, 9, 4, 4, 8]
+    print(bucket_sort(nums))
diff --git a/十大排序算法/10.基数排序.py b/十大排序算法/10.基数排序.py
@@ -0,0 +1,15 @@
+def radix_sort(nums):
+    # 最大数字长度作为排序次数
+    for k in range(len(str(max(nums)))):
+        # 数字0-9建立10个桶
+        buckets = [[] for _ in range(10)]
+        # 对每个元素从低位到高位获取对应数字，放入对应的桶
+        for num in nums:
+            buckets[num//(10**k) % 10].append(num)
+        nums = [num for bucket in buckets for num in bucket]
+    return nums
+
+
+if __name__ == '__main__':
+    nums = [21, 111, 84, 91, 454, 52, 312, 421, 4, 8]
+    print(radix_sort(nums))
