python 八大排序算法

1、选择排序

选择排序是一种简单直观的排序算法，其工作原理是在未排序序列中找到最小（或最大）的元素，存放到排序序列的起始位置，然后继续寻找剩余未排序序列中的最小（或最大）元素，放到已排序序列的末尾，直至所有元素排序完毕。

在Python中，选择排序的实现代码如下：

arr = [4,2,6,5,7,8]
for i in range(0,len(arr)):
    for j in range(i+1,len(arr)):
        if arr[i] >= arr[j]:
            arr[i],arr[j]=arr[j],arr[i]        
print(arr)
1
2
3
4
5
6

2、冒泡排序

冒泡排序是一种基本的交换排序算法，其工作原理是通过相邻元素之间的比较和交换，将最大（或最小）的元素逐渐移动到数组末尾。

在Python中，冒泡排序的实现代码如下：

arr = [4,2,6,5,7,8]
for i in range(0,len(arr)-1):
    for j in range(0,len(arr)-1-i):
        if arr[j] >= arr[j+1]:
            arr[j],arr[j+1]=arr[j+1],arr[j]
print(arr)
1
2
3
4
5
6

3、插入排序

插入排序是一种简单直观的排序算法，其工作原理是把第一个元素看做已排序的圆度，然后将未排序的元素插入到已排序的部分中的合适位置，直到所有元素排好序。

在Python中，插入排序的实现代码如下：

arr = [4,2,6,5,7,8]
for i in range(1,len(arr)):
    for j in range(i,0,-1):
        if arr[j] <= arr[j-1]:
            arr[j],arr[j-1]=arr[j-1],arr[j]        
print(arr)
1
2
3
4
5
6

4、希尔排序

希尔排序（Shell Sort）是插入排序的一种高效改进版本，也称为缩小增量排序。希尔排序是非稳定排序算法，其基本思想是将待排序的序列划分成若干个子序列，每个子序列内部完成插入排序，随后逐步缩小子序列的间隔，直到间隔为1，整个序列就变得有序。

在Python中，希尔排序的实现代码如下：

def shell_sort(arr):
    n = len(arr)
    gap = n // 2  # 初始化间隔
    while gap > 0:
        for i in range(gap, n):
            temp = arr[i]
            j = i
            while j >= gap and arr[j - gap] > temp:
                arr[j] = arr[j - gap]
                j -= gap
            arr[j] = temp
        gap //= 2  # 缩小间隔
    return arr

1
2
3
4
5
6
7
8
9
10
11
12
13
14

5、快速排序

1. 从数列中挑出一个元素，称为 “基准”（pivot）;
2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
3. 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

在Python中，快速排序的实现代码如下：

# 实现快速排序方法的函数
def quick_sort_num(nums,start,end):
    if start < end:
    	# 定义基准值为第一个数
        i, j, pivot = start, end, nums[start]
        while i < j:
        	# 将基准数右边的数中比基准数小的放到左边
            while i < j and nums[j] >= pivot:
                j = j-1
            if i < j:
                nums[i] = nums[j]
                i = i+1
            # 将基准数左边的数中比基准数大的数放到右边
            while i < j and nums[i] < pivot:
                i = i+1
            if i < j:
                nums[j] = nums[i]
                j = j-1
        nums[i] = pivot
        # 分别将基准数左边的数列和右边的数列进行递归
        quick_sort_num(nums, start, i-1)
        quick_sort_num(nums, i+1, end)
    return nums

# 快速排序主体函数
def quick_sort(nums):
    start = 0
    end = len(nums)-1
    nums = quick_sort_num(nums, start, end)
    return nums
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

6、归并排序

归并排序其实是将原数列分为很多个小数列将其排序，在小数列排序完之后，再将各个小数列进行排序，最后得到一个全部有序的数列。

在Python中，归并排序的实现代码如下：

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = arr[:mid]
    right = arr[mid:]
    merge(left, right)
1
2
3
4
5
6
7

7、基数排序

基数排序的基本思想是先将数字按照个位数上数字的大小进行排序，排序之后再将已经排过序的数字再按照十位数上数字的大小进行排序，依次类推。

在Python中，基数排序的实现代码如下：

def counting_sort(arr, exp):
    n = len(arr)
    output = [0] * n
    count = [0] * 10
 
    for i in range(n):
        index = arr[i] // exp
        count[index % 10] += 1
 
    for i in range(1, 10):
        count[i] += count[i - 1]
 
    i = n - 1
    while i >= 0:
        index = arr[i] // exp
        output[count[index % 10] - 1] = arr[i]
        count[index % 10] -= 1
        i -= 1
 
    for i in range(n):
        arr[i] = output[i]
 
def radix_sort(arr):
    max_element = max(arr)
    exp = 1
    while max_element // exp > 0:
        counting_sort(arr, exp)
        exp *= 10
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

8、堆排序

堆排序是一种特殊的比较排序算法，其基本思想是维护一个最大值（或最小值）的堆，每次将堆顶元素与堆底元素交换，然后重新调整堆结构，直到堆为空。

在Python中，堆排序的实现代码如下：

def heapify(arr, n, i):
    largest = i  # 假设当前元素为最大值
    left = 2 * i + 1
    right = 2 * i + 2
    if left < n and arr[left] > arr[largest]:
        largest = left
    if right < n and arr[right] > arr[largest]:
        largest = right
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)
1
2
3
4
5
6
7
8
9
10
11