JIYIK CN >

This article introduces several commonly used sorting algorithms in software engineering.

The core codes of all sorting algorithms are introduced in "Core Codes of Common Sorting Algorithms"

1. Insertion Sort

The basic idea of ​​insertion sort is to insert a record to be sorted into the previously sorted sequence according to the size of its keyword each time until all records are inserted.

For the concept and principle of insertion sort, you can refer to "The Learning Path of Sorting Algorithm - Insertion Sort (Concept)"

Insertion sort can be broken down into three cases.

Direct Insertion Sort - "The Road to Learning Sorting Algorithms - Direct Insertion Sort"

Binary Insertion Sort - "The Road to Learning Sorting Algorithms - Binary Insertion Sort"

Table Insertion Sort —— "The Road to Learning Sorting Algorithms - Table Insertion Sort"

2. Shell sort

Hill sort is named after the designer of the algorithm, Hill. It is an improvement of Hill on the basis of insertion sort and can be said to be a special insertion sort.

Here are the properties of insertion sort:

First of all, the insertion sort algorithm is very efficient when operating on already ordered data, and can achieve the efficiency of linear sorting.

Secondly, when inserting sort, only one data can be moved in each sorting, so this sorting method is relatively inefficient.

Based on this property, the designer of Hill sort invented the Hill sort algorithm, whose basic idea is:

First, the entire sequence of records to be sorted is divided into several subsequences and sorted by direct insertion. The method of dividing the subsequence is to set an increment. When each subsequence is in order, the increment is reduced by half (divided by 2, rounded up), and the subsequence is sorted again. This is done in sequence. When the records in the entire sequence are basically in order, all records are sorted by direct insertion in sequence. At this time, the increment is reduced to 1, because direct insertion sort is very efficient when the elements are basically in order (according to the first point above, close to the best case).

For specific implementation, please refer to "The Road to Learning Sorting Algorithms - Hill Sorting"

3. Merge Sort

Merge sort is an effective sorting algorithm based on the merge operation. This algorithm is a very typical application of the Divide and Conquer method. Merge the ordered subsequences to obtain a completely ordered sequence; that is, first make each subsequence ordered, and then make the subsequence segments ordered. If two ordered lists are merged into one ordered list, it is called a two-way merge.

The most common way to implement merge sort is to use a recursive function. Of course, the underlying mechanism of the recursive function is also the stack mechanism. Therefore, the method of implementing merge sort can also use a stack instead of recursion.

For specific implementation, you can refer to "The Road to Learning Sorting Algorithms - Merge Sort" and "The Road to Learning Sorting Algorithms - Merge Sort (Non-recursive Implementation)"

4. Quick Sort

Quick sort is a sorting algorithm developed by Tony Hall. On average, sorting n items requires O(n log n) comparisons. In the worst case, O(n2) comparisons are required, but this is uncommon. In fact, quick sort is often significantly faster than other O(n log n) algorithms because its inner loop can be implemented efficiently on most architectures.

Quick sort uses the divide and conquer strategy to divide a list into two sub-lists.
The implementation steps are as follows

1. Pick out an element from the sequence, called the "benchmark" (there are many ways to find this benchmark, here we use the first element as the benchmark by default)
2. Reorder the sequence, put all elements smaller than the benchmark value in front of the benchmark, and all elements larger than the benchmark value after the benchmark (the same number can be on either side). After this partition exits, the benchmark is in the middle of the sequence. This is called a partition operation.
3. Divide the array into two parts from the middle position of the benchmark obtained in the second step, and recursively sort the subsequence of elements smaller than the benchmark value and the subsequence of elements greater than the benchmark value.
4. Repeat the second step until the number of values ​​in the subsequence is 1

Similarly, the common implementation method is to use a recursive function. So it can also be implemented in a non-recursive way, that is, with the help of a stack.

For specific implementation, you can refer to "The Road to Learning Sorting Algorithms - Quick Sort" and "The Road to Learning Sorting Algorithms - Quick Sort (Non-recursive Implementation)"

5. Heap Sort

Heapsort: refers to a sorting algorithm designed using the heap data structure. A heap is a structure that approximates a complete binary tree and satisfies the properties of a heap: the key value or index of a child node is always smaller than (or larger than) its parent node.

From the last sentence of the above definition, we can also derive two concepts - the big top heap and the small top heap.

The so-called max-heap is that the key value or index of a child node is always smaller than its parent node. The sequence obtained by the max-heap is increasing.

The so-called mini-heap is that the key value or index of the child node is always greater than its parent node. The sequence obtained by the mini-heap is decreasing.

Let's take a look at the idea of ​​heap sorting.

By taking advantage of the fact that the top record of the mini-heap is the largest keyword, it becomes easy to select the largest record from the disorder each time.

The basic idea is (max-heap): 1) The initial sequence of keywords to be sorted (R1, R2….Rn) is constructed into a max-heap, which is the initial unordered area; 2) The top element R[1] of the heap is exchanged with the last element R[n], and a new unordered area (R1, R2, …Rn-1) and a new ordered area (Rn) are obtained, and R[1, 2…n- 1] <= R[n] are satisfied; 3) Since the new top R[1] of the heap after the exchange may violate the properties of the heap, it is necessary to adjust the current unordered area (R1, R2, …Rn-1) to a new heap, and then exchange R[1] with the last element of the unordered area again to obtain a new unordered area (R1, R2….Rn-2) and a new ordered area (Rn-1, Rn). Repeat this process until the number of elements in the ordered area is n-1, and the entire sorting process is completed. The operation process is as follows: 1) Initialize the heap: construct R[1..n] as a heap; 2) Exchange the top element R[1] of the current unordered area with the last record of the interval, and then adjust the new unordered area to a new heap. Therefore, for heap sorting, the two most important operations are constructing the initial heap and adjusting the heap. In fact, constructing the initial heap is actually the process of adjusting the heap, but constructing the initial heap is to adjust all non-leaf nodes.

具体步骤和实现大家可以参考《排序算法学习之路——堆排序》

6. 选择排序

选择排序是一种简单直观的排序算法。其基本思想是在未排序的序列中选择一个最大（或最小）元素放到末尾（注意：这里是未排序序列的末尾，可以认为是有序序列的起始位置）。

其实现步骤如下

1）首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置
2）再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
3）重复第二步，直到所有元素均排序完毕。

详细介绍和代码实现大家可以参考《排序算法学习之路——选择排序》

7. 冒泡排序

冒泡排序也是一种简单直观的排序算法。其思想是：它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

冒泡排序的步骤

1）比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2）对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
3）针对所有的元素重复以上的步骤，除了最后一个。
4）持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

详细介绍和代码实现大家可以参考《排序算法学习之路——冒泡排序》

8. 基数排序——LSD

基数排序（Radix Sort）：是一种非比较型的整数排序算法。

基数排序的基本原理是，按照整数的每个位数分组。在分组过程中，对于不足位的数据用0补位。

上面就是本人在学习排序算法中学习的算法，当然这些并不完整。后续会持续更新算法，希望大家持续关注。

基数排序按照对位数分组的顺序的不同，可以分为LSD基数排序和MSD基数排序。

LSD基数排序，是按照从低位到高位的顺序进行分组排序。例如：1,2,3,4,5,6,7,8,9,10第一次分组后为 10,1,2,3,4,5,6,7,8,9。

首先我们看LSD基数排序是如何进行的

对于序列中的每个整数的每一位都可以看成是一个桶，而该位上的数字就可以认为是这个桶的键值。这句话应该怎么理解呢，我们来看这样的一个序列

170, 45, 75, 90, 802, 2, 24, 66

这是一个整数序列，我们知道，对于每个整数的每一位上的值肯定是介于0和9之间的。因此，要想对这个序列进行LSD排序，那就必须有10个桶。这10个桶的索引分别就是0——9这十个数。对于LSD基数排序来说，每一次分组过程就是将相应的整数放进相应的桶中。

拿第一次分组来说吧，对于每个整数要按照个位上的数进行分组。那么我们看170，其个位为0，所以说170应该放进0这个桶中。然后以此类推 45放在5这个桶中。

所以上述序列的第一次分组后，各个整数所在的桶如下

0: 170, 090
1: 空
2: 802, 002
3: 空
4: 024
5: 045, 075
6: 066
7–9: 空

然后再将这些数依次收集起来，第一次分组再组合以后的序列为

170, 90, 802, 2, 24, 45, 75, 66

接着就是针对十位上的数进行分组入桶，入桶的情况如下

0: 802, 002
1: 空
2: 024
3: 空
4: 045
5: 空
6: 066
7: 170, 075
8: 空
9: 090

再次整理起来以后为下面的序列

802, 2, 24, 45, 66, 170, 75, 90

最后再次进行第三次（百位上的数）分组入桶

0: 002, 024, 045, 066, 075, 090
1: 170
2–7: 空
8: 802
9: 空

整理起来以后，我们发现整个序列已经是有序的了

2, 24, 45, 66, 75, 90, 170, 802

详细介绍和代码实现大家可以参考《排序算法学习之路——基数排序（LSD）》

9. 基数排序——MSD

MSD基数排序是从最高位开始对序列进行分组，到最低位为止。但是其实现过程是和LSD基数排序不同的，排序过程中需要用到递归函数。

待排序序列

170, 45, 75, 90, 2, 24, 802, 66

我们看到，这里面的最大的数是3位数。所以说我们开始从百位对这些数进行分组

0: 045, 075, 090,002, 024, 066
1: 170
2-7: 空
8: 802
9: 空

From here on, it is different from LSD radix sort. In LSD radix sort, after each grouping, the data in the bucket is collected. Then the collected sequence is grouped according to the next bit. For MSD, the data in the bucket is not collected here. What we need to do is to check the data in each bucket. When the number of elements in the bucket is more than 1, the bucket should be recursively grouped for the next bit.

In this example, we want to group all the elements in bucket 0 according to the digits in the tens place.

0: 002
1: Empty
2: 024
3: Empty
4: 045
5: Empty
6: 066
7: 075
8: Empty
9: 090

According to what is said above, we should recursively group the elements in each bucket according to the number in the ones place. However, we find that the number of elements in each bucket is less than or equal to 1. Therefore, we start to back off at this step. In other words, we start to collect the data in the bucket. After the collection is completed, we back off to the previous level. At this time, the buckets grouped according to the hundreds place become as follows

0: 002, 024, 045,066, 075, 090
1: 170
2-7: Empty
8: 802
9: Empty

Then we collect the data in this bucket. After collection, the sequence is as follows

2, 24, 45, 66, 75, 90, 170, 802

The entire MSD cardinality sorting is performed according to the above process.

For detailed introduction and code implementation, please refer to "The Road to Learning Sorting Algorithms - Radix Sorting (MSD)"

The above is the algorithm I learned in the learning sorting algorithm, of course, these are not complete. I will continue to update the algorithm in the future, and I hope everyone will continue to pay attention.