Top ten sorting algorithms that programmers must master (Part 1)

#Book Issue Introduction

Sort AlgorithmIt can be said that every programmer must have it After mastering, it is necessary to understand their principles and implementation.The following is an introduction to the Python implementation of the ten most commonly used sorting algorithms to facilitate your learning. .

01 Bubble sort——exchange sort02 Quick sort—— Exchange sorting

03 Selection sort——Selection sorting04 Heap sort ——Select class sort

05 Insertion sort——Insertion class sort

06 Hill sorting-insertion sorting

07 Merging sort-merging sorting

08 Counting sorting-distribution sorting

09 Radix sorting-distribution sorting

10 Bucket sorting-distribution sorting

01

##risk Bubble Sort

#Bubble Sort:

A classic sorting algorithm gets its name because during the operation of the algorithm, extreme values ​​will gradually emerge like bubbles under the water.

Algorithm principle:

Compare adjacent elements. If the first one is bigger than the second one, swap them both.

• Do the same for each pair of adjacent elements, starting with the first pair and ending with the last pair. At this point, the last element should be the largest number.

• Repeat the above steps for all elements except the last one.

• Continue repeating the above steps for fewer and fewer elements each time until there are no pairs of numbers to compare.

code show as below:

'''冒泡排序'''
def Bubble_Sort(arr):
    for i in range(1, len(arr)):
        for j in range(0, len(arr)-i):
            if arr[j] > arr[j+1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

arr = [29, 63, 41, 5, 62, 66, 57, 34, 94, 22]
result = Bubble_Sort(arr)
print('result list: ', result)
# result list: [5, 22, 29, 34, 41, 57, 62, 63, 66, 94]

##02

Quick Sort

Quicksort: Split the data to be sorted into two independent parts through one sort, and then Then use this method to quickly sort the two parts of the data respectively. The entire sorting process can be performed recursively, so that the entire data becomes an ordered sequence, which is an improvement on the bubble sort algorithm.

Algorithm principle:

• First set a dividing value, and divide the array into left and right parts through this dividing value.

• Collect the data that is greater than or equal to the cut-off value to the right of the array, and the data that is less than the cut-off value are concentrated to the left of the array. At this time, each element in the left part is less than or equal to the dividing value, and each element in the right part is greater than or equal to the dividing value.

• #Then, the data on the left and right can be sorted independently. For the array data on the left, you can take a dividing value and divide this part of the data into left and right parts. Similarly, place the smaller value on the left and the larger value on the right. The array data on the right can also be processed similarly.

• # Repeat the above process until the data in the left and right parts are sorted.

code show as below:

'''快速排序'''
def Quick_Sort(arr):
    # 递归入口及出口
    if len(arr) >= 2:
        # 选取基准值，也可以选取第一个或最后一个元素
        mid = arr[len(arr) // 2]
        # 定义基准值左右两侧的列表
        left, right = [], []
        # 从原始数组中移除基准值
        arr.remove(mid)
        for num in arr:
            if num >= mid:
                right.append(num)
            else:
                left.append(num)
        return Quick_Sort(left) + [mid] + Quick_Sort(right)
    else:
        return arr

arr = [27, 70, 34, 65, 9, 22, 47, 68, 21, 18]
result = Quick_Sort(arr)
print('result list: ', result)
# result list: [9, 18, 21, 22, 27, 34, 47, 65, 68, 70]

#03

Select sort

##Selection sort : It is a simple and intuitive sorting algorithm. No matter what data is entered, the time complexity is O(n²). So when using it, the smaller the data size, the better.

Algorithm principle:

Find the smallest (large) element in the unsorted sequence and store it at the starting position of the sorted sequence.
Continue to find the smallest (largest) element from the remaining unsorted elements, and then put it at the end of the sorted sequence.
And so on until all elements are sorted.

代码如下：

'''选择排序'''
def Selection_Sort(arr):
    for i in range(len(arr) - 1):
        # 记录最小数的索引
        minIndex = i
        for j in range(i + 1, len(arr)):
            if arr[j] < arr[minIndex]:
                minIndex = j
        # i 不是最小数时，将 i 和最小数进行交换
        if i != minIndex:
            arr[i], arr[minIndex] = arr[minIndex], arr[i]
    return arr

arr = [5, 10, 76, 55, 13, 79, 49, 51, 65, 30]
result = Quick_Sort(arr)
print(&#39;result list: &#39;, result)
# result list: [5, 10, 13, 30, 49, 51, 55, 65, 76, 79]

04

插入排序

插入排序（Insertion Sort）：一般也被称为直接插入排序，是一种最简单直观的排序算法。

算法原理：

• 将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
  

• 从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。

代码如下：

'''插入排序'''
def Insertion_Sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

arr = [31, 80, 42, 47, 35, 26, 10, 5, 51, 53]
result = Insertion_Sort(arr)
print(&#39;result list: &#39;, result)
# result list: [5, 10, 26, 31, 35, 42, 47, 51, 53, 80]

05

堆排序

堆排序（Heap sort）：是指利用堆这种数据结构所设计的一种排序算法，堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。

算法原理：

• 创建一个堆 H[0……n-1]；
  

• 把堆首（最大值）和堆尾互换；

• 把堆的尺寸缩小 1，并调用 shift_down(0)，目的是把新的数组顶端数据调整到相应位置；

• 重复步骤 2，直到堆的尺寸为 1。

代码如下：

'''堆排序'''
def Heapify(arr, n, i):
    largest = i
    # 左右节点分块
    left = 2 * i + 1
    right = 2 * i + 2
    if left < n and arr[i] < arr[left]:
        largest = left
    if right < n and arr[largest] < arr[right]:
        largest = right
    if largest != i:
        # 大小值交换
        arr[i], arr[largest] = arr[largest], arr[i]
        # 递归
        Heapify(arr, n, largest)

def Heap_Sort(arr):
    nlen = len(arr)
    for i in range(nlen, -1, -1):
        # 调整节点
        Heapify(arr, nlen, i)
    for i in range(nlen - 1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]
        # 调整节点
        Heapify(arr, i, 0)
    return arr

arr = [26, 53, 83, 86, 5, 46, 72, 21, 4, 75]
result = Heap_Sort(arr)
print(&#39;result list: &#39;, result)
# result list: [4, 5, 21, 26, 46, 53, 72, 75, 83, 86]

The above is the detailed content of Top ten sorting algorithms that programmers must master (Part 1). For more information, please follow other related articles on the PHP Chinese website!