Home Backend Development Python Tutorial Top ten sorting algorithms that programmers must master (Part 2)

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

Aug 15, 2023 pm 02:53 PM
Sorting Algorithm



#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 sort

03 Selection sort - selection class sorting 04 Heap sort - selection class sorting

##05 Insertion Sort - Insertion Class Sorting

06 Hill Sorting - Insertion Class Sorting

07 Merge sort - merge sort sort

##08 Counting sorting - distribution sorting

09 Radix sorting - distribution sorting

10 Bucket sorting - distribution Class sorting



##06
Hill sort
HillSort (Shell Sort): is a type of insertion sort, also known as "Diminishing Increment Sort" ), is a more efficient and improved version of the direct insertion sort algorithm.

Algorithm principle:
    Take an integer gap less than n
  • (gap is called the step size) and divide the elements to be sorted into several Group subsequence, all records whose distance is a multiple of gap are placed in the same group

  • Perform direct insertion sorting on the elements in each group, this time After the sorting is completed, the elements of each group are ordered
  • Reduce the gap value and repeat the above grouping and sorting
  • Repeat the above operation. When gap=1, the sorting ends
The code is as follows:
'''希尔排序'''
def Shell_Sort(arr):
    # 设定步长,注意类型
    step = int(len(arr) / 2)
    while step > 0:
        for i in range(step, len(arr)):
            # 类似插入排序, 当前值与指定步长之前的值比较, 符合条件则交换位置
            while i >= step and arr[i - step] > arr[i]:
                arr[i], arr[i - step] = arr[i - step], arr[i]
                i -= step
        step = int(step / 2)
    return arr

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


#07
Merge sort
##Merge Sort : is an effective and stable sorting algorithm based on merge operations. , this algorithm is a very typical application of the divide and conquer method (Divide and Conquer), which merges ordered subsequences to obtain a completely ordered sequence.

Algorithm principle:
  • Apply for space so that its size is the sum of the two sorted sequences. This space is used to store the merged The sequence

  • sets two indexes. The initial
  • index

    positions are the starting positions of the two sorted sequences

  • Compare the elements pointed to by the two
  • indexes

    , select the relatively small element and put it into the merge space, and move the index to Next position

  • Repeat the previous step until a certain
  • index

    exceeds the end of the sequence

  • Copy all remaining elements of the other sequence directly to the end of the merged sequence
代码如下:
'''归并排序'''def Merge(left, right):
    arr = []
    i = j = 0
    while j < len(left) and  i < len(right):
        if left[j] < right[i]:
            arr.append(left[j])
            j += 1
        else:
            arr.append(right[i])
            i += 1
    if j == len(left):
        # right遍历完
        for k in right[i:]:
            arr.append(k)
    else:
        # left遍历完
        for k in left[j:]:
            arr.append(k)
    return arr

def Merge_Sort(arr):
    # 递归结束条件
    if len(arr) <= 1:
        return arr
    # 二分
    middle = len(arr) // 2
    left = Merge_Sort(arr[:middle])
    right = Merge_Sort(arr[middle:])
    # 合并
    return Merge(left, right)

arr = [27, 70, 34, 65, 9, 22, 47, 68, 21, 18]
result = Merge_Sort(arr)
print(&#39;result list: &#39;, result)
# result list: [9, 18, 21, 22, 27, 34, 47, 65, 68, 70]

08
计数排序
计数排序(Count sort):是一个非基于比较的排序算法,它的优势在于在对一定范围内的整数排序时,它的复杂度为Ο(n+k)(其中k是整数的范围),快于任何比较排序算法。

算法原理:
  • 找出待排序的数组中最大和最小的元素

  • 统计数组中每个值为i的元素出现的次数,存入数组C的第i项

  • 对所有的计数累加(从C中的第一个元素开始,每一项和前一项相加)

  • 反向填充目标数组:将每个元素i放在新数组的第C(i)项,每放一个元素就将C(i)减去1


代码如下:
&#39;&#39;&#39;计数排序&#39;&#39;&#39;
def Count_Sort(arr):
    max_num = max(arr)
    min_num = min(arr)
    count_num = max_num - min_num + 1
    count_arr = [0 for i in range(count_num)]
    res = [0 for i in range(len(arr))]
    # 统计数字出现的次数
    for i in arr:
        count_arr[i - min_num] += 1
    # 统计前面有几个比自己小的数
    for j in range(1, count_num):
        count_arr[j] = count_arr[j] + count_arr[j - 1]
    # 遍历重组
    for k in range(len(arr)):
        res[count_arr[arr[k] - min_num] - 1] = arr[k]
        count_arr[arr[k] - min_num] -= 1
    return res

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

09
基数排序
基数排序(radix sort)是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。由于整数也可以表达字符串(比如名字或日期)和特定格式的浮点数,所以基数排序也不是只能使用于整数。

算法原理(以LSD为例):
  • 根据个位数的数值,遍历列表将它们分配至编号0到9的桶子中

  • 将这些桶子中的数值重新串接起来

  • 根据十位数的数值,遍历列表将它们分配至编号0到9的桶子中

  • 再将这些桶子中的数值重新串接起来


代码如下:
&#39;&#39;&#39;基数排序&#39;&#39;&#39;
def Radix_Sort(arr):
    max_num = max(arr)
    place = 0
    while 10 ** place <= max_num:
        # 创建桶
        buckets = [[] for _ in range(10)]
        # 分桶
        for item in arr:
            pos = item // 10 ** place % 10
            buckets[pos].append(item)
        j = 0
        for k in range(10):
            for num in buckets[k]:
                arr[j] = num
                j += 1
        place += 1
    return arr

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

10
桶排序
桶排序 (Bucket sort)或所谓的箱排序:划分多个范围相同的桶区间,每个桶自排序,最后合并,桶排序可以看作是计数排序的扩展。

算法原理:
  • 计算有限桶的数量

  • 逐个桶内部排序

  • 遍历每个桶,进行合并


代码如下:
&#39;&#39;&#39;桶排序&#39;&#39;&#39;
def Bucket_Sort(arr):
    num = max(arr)
    # 列表置零
    pre_lst = [0] * num
    result = []
    for data in arr:
        pre_lst[data - 1] += 1
    i = 0
    while i < len(pre_lst): # 遍历生成的列表,从小到大
        j = 0
        while j < pre_lst[i]:
            result.append(i + 1)
            j += 1
        i += 1
    return result

arr = [26, 53, 83, 86, 5, 46, 5, 72, 21, 4, 75]
result = Bucket_Sort(arr)
print(&#39;result list: &#39;, result)
# result list: [4, 5, 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 2). For more information, please follow other related articles on the PHP Chinese website!

Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn

Hot AI Tools

Undress AI Tool

Undress AI Tool

Undress images for free

Undresser.AI Undress

Undresser.AI Undress

AI-powered app for creating realistic nude photos

AI Clothes Remover

AI Clothes Remover

Online AI tool for removing clothes from photos.

Clothoff.io

Clothoff.io

AI clothes remover

Video Face Swap

Video Face Swap

Swap faces in any video effortlessly with our completely free AI face swap tool!

Hot Article

Hot Tools

Notepad++7.3.1

Notepad++7.3.1

Easy-to-use and free code editor

SublimeText3 Chinese version

SublimeText3 Chinese version

Chinese version, very easy to use

Zend Studio 13.0.1

Zend Studio 13.0.1

Powerful PHP integrated development environment

Dreamweaver CS6

Dreamweaver CS6

Visual web development tools

SublimeText3 Mac version

SublimeText3 Mac version

God-level code editing software (SublimeText3)

Complex experimental design issues in Kuaishou's two-sided market Complex experimental design issues in Kuaishou's two-sided market Apr 15, 2023 pm 07:40 PM

1. Background of the problem 1. Introduction to the two-sided market experiment The two-sided market, that is, a platform, includes two participants, producers and consumers, and both parties promote each other. For example, Kuaishou has a video producer and a video consumer, and the two identities may overlap to a certain extent. Bilateral experiment is an experimental method that combines groups on the producer and consumer sides. Bilateral experiments have the following advantages: (1) The impact of the new strategy on two aspects can be detected simultaneously, such as changes in product DAU and the number of people uploading works. Bilateral platforms often have cross-side network effects. The more readers there are, the more active the authors will be, and the more active the authors will be, the more readers will follow. (2) Effect overflow and transfer can be detected. (3) Help us better understand the mechanism of action. The AB experiment itself cannot tell us the relationship between cause and effect, only

How to filter and sort data in Vue technology development How to filter and sort data in Vue technology development Oct 09, 2023 pm 01:25 PM

How to filter and sort data in Vue technology development In Vue technology development, data filtering and sorting are very common and important functions. Through data filtering and sorting, we can quickly query and display the information we need, improving user experience. This article will introduce how to filter and sort data in Vue, and provide specific code examples to help readers better understand and use these functions. 1. Data filtering Data filtering refers to filtering out data that meets the requirements based on specific conditions. In Vue, we can pass comp

How to use radix sort algorithm in C++ How to use radix sort algorithm in C++ Sep 19, 2023 pm 12:15 PM

How to use the radix sort algorithm in C++ The radix sort algorithm is a non-comparative sorting algorithm that completes sorting by dividing the elements to be sorted into a limited set of digits. In C++, we can use the radix sort algorithm to sort a set of integers. Below we will discuss in detail how to implement the radix sort algorithm, with specific code examples. Algorithm idea The idea of ​​the radix sorting algorithm is to divide the elements to be sorted into a limited set of digital bits, and then sort the elements on each bit in turn. Sorting on each bit is completed

Google uses AI to break the ten-year ranking algorithm seal. It is executed trillions of times every day, but netizens say it is the most unrealistic research? Google uses AI to break the ten-year ranking algorithm seal. It is executed trillions of times every day, but netizens say it is the most unrealistic research? Jun 22, 2023 pm 09:18 PM

Organizing | Nuka-Cola, Chu Xingjuan Friends who have taken basic computer science courses must have personally designed a sorting algorithm - that is, using code to rearrange the items in an unordered list in ascending or descending order. It's an interesting challenge, and there are many possible ways to do it. A lot of time has been invested in figuring out how to accomplish sorting tasks more efficiently. As a basic operation, sorting algorithms are built into the standard libraries of most programming languages. There are many different sorting techniques and algorithms used in code bases around the world to organize large amounts of data online, but at least as far as the C++ libraries used with the LLVM compiler are concerned, the sorting code has not changed in more than a decade. Recently, the Google DeepMindAI team has now developed a

How to implement the selection sort algorithm in C# How to implement the selection sort algorithm in C# Sep 20, 2023 pm 01:33 PM

How to implement the selection sort algorithm in C# Selection sort (SelectionSort) is a simple and intuitive sorting algorithm. Its basic idea is to select the smallest (or largest) element from the elements to be sorted each time and put it at the end of the sorted sequence. Repeat this process until all elements are sorted. Let's learn more about how to implement the selection sort algorithm in C#, along with specific code examples. Creating a selection sort method First, we need to create a method for implementing selection sort. This method accepts a

Swoole Advanced: How to use multi-threading to implement high-speed sorting algorithm Swoole Advanced: How to use multi-threading to implement high-speed sorting algorithm Jun 14, 2023 pm 09:16 PM

Swoole is a high-performance network communication framework based on PHP language. It supports the implementation of multiple asynchronous IO modes and multiple advanced network protocols. On the basis of Swoole, we can use its multi-threading function to implement efficient algorithm operations, such as high-speed sorting algorithms. The high-speed sorting algorithm (QuickSort) is a common sorting algorithm. By locating a benchmark element, the elements are divided into two subsequences. Those smaller than the benchmark element are placed on the left, and those greater than or equal to the benchmark element are placed on the right. Then the left and right subsequences are placed. subsequence recursion

Discussion on application scenarios of different PHP array sorting algorithms Discussion on application scenarios of different PHP array sorting algorithms Apr 28, 2024 am 09:39 AM

For different scenarios, it is crucial to choose the appropriate PHP array sorting algorithm. Bubble sort is suitable for small-scale arrays without stability requirements; quick sort has the lowest time complexity in most cases; merge sort has high stability and is suitable for scenarios that require stable results; selection sort is suitable for situations without stability requirements. Situation; Heap sort efficiently finds the maximum or minimum value. Through comparison of actual cases, quick sort is superior to other algorithms in terms of time efficiency, but merge sort should be chosen when stability needs to be considered.

What are the sorting algorithms for arrays? What are the sorting algorithms for arrays? Jun 02, 2024 pm 10:33 PM

Array sorting algorithms are used to arrange elements in a specific order. Common types of algorithms include: Bubble sort: swap positions by comparing adjacent elements. Selection sort: Find the smallest element and swap it to the current position. Insertion sort: Insert elements one by one to the correct position. Quick sort: divide and conquer method, select the pivot element to divide the array. Merge Sort: Divide and Conquer, Recursive Sorting and Merging Subarrays.

See all articles