Raptor inputs n data to sort_Review the top ten classic sorting algorithms

1.4, Algorithm Classification

1.5. The difference between comparison and non-comparison

Common quick sort, merge sort, heap sort, bubble sort, etc. belong to comparison sort. In the final result of sorting, the order between elements depends on the comparison between them. Each number must be compared with other numbers to determine its position. In sorting such as bubble sorting, the problem size is n, and because n times of comparison are required, the average time complexity is O(n2). In sorting such as merge sort and quick sort, the problem size is reduced to logN times through the divide and conquer method, so the average time complexity is O(nlogn). The advantage of comparative sorting is that it is suitable for data of all sizes and can be sorted regardless of the distribution of the data. It can be said that comparison sorting is suitable for all situations that require sorting. Counting sort, radix sort, and bucket sort are non-comparative sorting. Non-comparative sorting sorts by determining how many elements should precede each element. For the array arr, calculate how many elements there are before arr[i], then the position of arr[i] in the sorted array is uniquely determined. Non-comparative sorting only needs to determine the number of existing elements before each element, and all can be solved in one traversal. The algorithm time complexity is O(n). Non-comparative sorting has the lowest time complexity, but it takes up space to determine the unique position. Therefore, there are certain requirements for data scale and data distribution.

2. Bubble Sort

Bubble sort is a simple sorting algorithm. It repeatedly walks through the sequence to be sorted, comparing elements two at a time and swapping them if they are in the wrong order. The work of visiting the array is repeated until no more exchanges are needed, which means that the array has been sorted. The name of this algorithm comes from the fact that smaller elements will slowly “float” to the top of the array through swapping.

2.1, Algorithm Description

Compare adjacent elements. If the first is greater than the second, swap them both;

Do the same for each pair of adjacent elements, from the first pair at the beginning to the last pair at the end, so that the element at the end should be the largest number;

Repeat the above steps for all elements except the last one;

Repeat steps 1~3 until sorting is completed.

2.2, animation demonstration

?2.3, code implementation

/**

2.4, Algorithm Analysis

Best case: T(n) = O(n) Worst case: T(n) = O(n2) Average case: T(n) = O(n2)

3. Selection Sort

One of the most stable sorting algorithms, because no matter what data is entered, the time complexity is O(n2), so when using it, the smaller the data size, the better. The only advantage may be that it does not occupy additional memory space. Theoretically speaking, selection sort may also be the most common sorting method that most people think of when sorting. Selection-sort is a simple and intuitive sorting algorithm. How it works: First, find the smallest (large) element in the unsorted sequence and store it at the starting position of the sorted sequence. Then, continue to find the smallest (large) element from the remaining unsorted elements, and then put it into the sorted sequence. the end of. And so on until all elements are sorted.

3.1. Algorithm description

Direct selection sorting of n records can obtain ordered results through n-1 direct selection sorting passes. The specific algorithm is described as follows:

Initial state: The unordered area is R[1..n], and the ordered area is empty;

When the i-th sorting (i=1,2,3…n-1) starts, the current ordered area and unordered area are R[1..i-1] and R(i..n) respectively. This sorting operation selects the record R[k] with the smallest key from the current disordered area, and exchanges it with the first record R in the disordered area, so that R[1..i] and R[i + 1 ..n) respectively become a new ordered area with the number of records increased by 1 and a new unordered area with the number of records reduced by 1;

At the end of n-1 passes, the array is sorted.

3.2, animation demonstration

3.3, code implementation

/**

3.4, Algorithm Analysis

Best case: T(n) = O(n2) Worst case: T(n) = O(n2) Average case: T(n) = O(n2)

4. Insertion Sort

The algorithm description of insertion sort (Insertion-Sort) is a simple and intuitive sorting algorithm. It works by constructing an ordered sequence. For unsorted data, it scans from back to front in the sorted sequence, finds the corresponding position and inserts it. In the implementation of insertion sort, in-place sorting is usually used (that is, sorting that only uses O(1) extra space). Therefore, during the scanning process from back to front, it is necessary to repeatedly and gradually shift the sorted elements backward. , providing insertion space for the latest element.

4.1, Algorithm Description

• Generally speaking, insertion sort is implemented on arrays using in-place. The specific algorithm is described as follows:
• Starting from the first element, the element can be considered to have been sorted;
• Take out the next element and scan from back to front in the sorted element sequence;
• If the element (sorted) is larger than the new element, move the element to the next position;
• Repeat step 3 until you find a position where the sorted element is less than or equal to the new element;
• After inserting the new element at that position;
• Repeat steps 2~5.

4.2, animation demonstration

?4.3, code implementation

/**

4.4, Algorithm Analysis

Best case: T(n) = O(n) Worst case: T(n) = O(n2) Average case: T(n) = O(n2)

5. Shell Sort

Hill sorting is a sorting algorithm proposed by Donald Shell in 1959. Hill sorting is also an insertion sort. It is a more efficient version of simple insertion sort, also known as reduced incremental sorting. At the same time, this algorithm is one of the first algorithms to break through O(n2). It differs from insertion sort in that it compares elements that are farther away first. Hill sort is also called reducing increment sort. Hill sorting is to group records according to a certain increment in the table, and use the direct insertion sort algorithm to sort each group; as the increment gradually decreases, each group contains more and more keywords. When the increment is reduced to 1 , the entire file is divided into one group, and the algorithm terminates.

5.1, Algorithm Description

Let’s take a look at the basic steps of Hill sorting. Here we choose the increment gap=length/2, and the reduction increment continues with gap = gap/2. This incremental selection can be represented by a sequence, { n/2,(n/2)/2…1}, called the incremental sequence. The selection and proof of the increment sequence of Hill sorting is a mathematical problem. The increment sequence we chose is relatively commonly used and is also the increment recommended by Hill. It is called Hill increment. However, in fact, this increment sequence is not the most optimal one. Excellent. Here we use Hill increment as an example. First, the entire record sequence to be sorted is divided into several subsequences for direct insertion sorting. The specific algorithm is described:

Select an incremental sequence t1, t2,…,tk, where ti>tj, tk=1;

Sort the sequence k times according to the number of incremental sequences k;

In each sorting pass, the column to be sorted is divided into several subsequences of length m according to the corresponding increment ti, and direct insertion sorting is performed on each subtable. Only when the increment factor is 1, the entire sequence is processed as a table, and the length of the table is the length of the entire sequence.

5.2, process demonstration

5.3, code implementation

/**

5.4. Algorithm analysis

Best case: T(n) = O(nlog2 n) Worst case: T(n) = O(nlog2 n) Average case: T(n) =O(nlog2n)

6. Merge Sort

Like selection sort, the performance of merge sort is not affected by the input data, but its performance is much better than selection sort because it always has a time complexity of O(n log n). The price is additional memory space. Merge sort is an effective sorting algorithm based on merge operations. This algorithm is a very typical application using the divide and conquer method (Divide and Conquer). Merge sort is a stable sorting method. Merge the already ordered subsequences to obtain a completely ordered sequence; that is, first make each subsequence orderly, and then make the subsequence segments orderly. If two ordered lists are merged into one ordered list, it is called a 2-way merge.

6.1, Algorithm Description

Divide the input sequence of length n into two subsequences of length n/2;

Use merge sorting on these two subsequences;

Merge two sorted subsequences into a final sorted sequence.

6.2, animation demonstration

?6.3, code implementation

/**

6.4, Algorithm Analysis

Best case: T(n) = O(n) Worst case: T(n) = O(nlogn) Average case: T(n) = O(nlogn)

7. Quick Sort

The basic idea of quick sorting is to separate the records to be sorted into two independent parts through one sorting. If the keywords of one part of the record are smaller than the keywords of the other part, then the two parts of the records can be sorted separately to achieve The entire sequence is in order.

7.1, Algorithm Description

Quick sort uses the divide-and-conquer method to divide a string (list) into two sub-strings (sub-lists). The specific algorithm is described as follows:

Picking out an element from the sequence is called a “pivot”;

Reorder the array so that all elements smaller than the base value are placed in front of the base, and all elements larger than the base value are placed behind the base (the same number can go to either side). After this partition exits, the base is in the middle of the sequence. This is called a partition operation;

Recursively sort the subarray of elements less than the base value and the subarray of elements greater than the base value.

7.2, animation demonstration

?7.3, code implementation

/**

7.4, Algorithm Analysis

Best case: T(n) = O(nlogn) Worst case: T(n) = O(n2) Average case: T(n) = O(nlogn)　

8. Heap Sort

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

8.1, Algorithm Description

• Construct the initial sequence of keywords to be sorted (R1, R2…Rn) into a large top heap, which is the initial unordered area;
• Exchange the top element R[1] with the last element R[n], and then get a new unordered area (R1, R2,…Rn-1) and a new ordered area (Rn), and satisfy R [1,2…n-1]<=R[n];
• Since the new heap top R[1] after the exchange may violate the properties of the heap, it is necessary to adjust the current disordered area (R1, R2,…Rn-1) to a new heap, and then combine R[1] with the disordered area again. The last element of the area is exchanged to obtain a new unordered area (R1, R2…Rn-2) and a new ordered area (Rn-1, Rn). This process is repeated until the number of elements in the ordered area is n-1, then the entire sorting process is completed.

8.2, animation demonstration

8.3, code implementation

//Declare global variables for recording the length of the array;

8.4, Algorithm Analysis

Best case: T(n) = O(nlogn) Worst case: T(n) = O(nlogn) Average case: T(n) = O(nlogn)

9. Counting Sort

The core of counting sort is to convert the input data values into keys and store them in the additionally opened array space. As a linear time complexity sort, counting sort requires that the input data must be integers within a certain range. Counting sort is a stable sorting algorithm. Counting sort uses an additional array C, where the i-th element is the number of elements whose value is equal to i in the array A to be sorted. Then arrange the elements in A to the correct position according to the array C. It can only sort integers.

9.1. Algorithm description

• Find the largest and smallest elements in the array to be sorted;
• Count the number of occurrences of each element with value i in the array and store it in the i-th item of array C;
• Accumulate all counts (starting from the first element in C, each item is added to the previous item);
• Fill the target array in reverse: Place each element i in the C(i)th item of the new array, and subtract 1 from C(i) for each element placed.

9.2, animation demonstration

9.3, code implementation

/**

9.4, Algorithm Analysis

When the input elements are n integers between 0 and k, its running time is O(n + k). Counting sort is not comparison sort, and sorting is faster than any comparison sort algorithm. Since the length of the array C used for counting depends on the range of the data in the array to be sorted (equal to the difference between the maximum value and the minimum value of the array to be sorted plus 1), this makes counting sorting require a large amount of data for arrays with a large data range. time and memory. Best case: T(n) = O(n + k) Worst case: T(n) = O(n + k) Average case: T(n) = O(n + k)

10. Bucket Sort

Bucket sort is an upgraded version of counting sort. It makes use of the mapping relationship of functions. The key to efficiency lies in the determination of this mapping function. The working principle of Bucket sort: Assume that the input data obeys a uniform distribution, divide the data into a limited number of buckets, and then sort each bucket separately (it is possible to use other sorting algorithms or continue to use it recursively) Bucket sorting is performed.

10.1. Algorithm description

• Set a BucketSize manually to determine how many different values each bucket can hold (for example, when BucketSize==5, the bucket can store {1, 2, 3, 4, 5}, but the capacity is not limited. That is, 100 pieces can be stored 3);
• Traverse the input data and put the data into the corresponding buckets one by one;
• To sort each bucket that is not empty, you can use other sorting methods, or you can use bucket sorting recursively;
• Concatenate sorted data from buckets that are not empty.
• Note that if bucket sorting is used recursively to sort each bucket, when the number of buckets is 1, you must manually reduce BucketSize and increase the number of buckets in the next cycle, otherwise it will fall into an infinite loop and cause memory overflow.

10.2, Picture Demonstration

10.3, code implementation

/**

10.4, Algorithm Analysis

Bucket sorting uses linear time O(n) in the best case. The time complexity of bucket sorting depends on the time complexity of sorting the data between each bucket, because the time complexity of other parts is O(n). Obviously, the smaller the buckets are divided, the less data there is between each bucket, and the less time it takes to sort. But the corresponding space consumption will increase. Best case: T(n) = O(n + k) Worst case: T(n) = O(n + k) Average case: T(n) = O(n2)　

11. Radix Sort

Radix sorting is also a non-comparison sorting algorithm. It sorts each bit, starting from the lowest bit. The complexity is O(kn), which is the length of the array, and k is the largest number of digits in the array; radix sorting is based on The low-order bits are sorted first, and then collected; then the high-order bits are sorted, and then collected; and so on, until the highest bit. Sometimes some attributes have a priority order, sorted by low priority first, and then by high priority. The final order is that those with higher priority come first, and those with the same high priority and lower priority come first. Radix sorting is based on separate sorting and separate collection, so it is stable.

11.1. Algorithm description

Get the maximum number in the array and get the number of digits;

arr is the original array, and each bit is taken from the lowest bit to form the radix array;

Perform counting sorting on radix (using the feature of counting sorting suitable for small range numbers);

11.2, animation demonstration

11.3, code implementation

/**

11.4, Algorithm Analysis

Best case: T(n) = O(n * k) Worst case: T(n) = O(n * k) Average case: T(n) = O(n * k). There are two methods of radix sorting: MSD sorts from high bits and LSD sorts from low bits. Radix sort vs counting sort vs bucket sort. These three sorting algorithms all use the concept of buckets, but there are obvious differences in how they are used:

• Radix sort: allocate buckets based on each digit of the key value
• Counting sort: Each bucket only stores a single key value
• Bucket sorting: Each bucket stores a certain range of values

Copyright Statement: This article is an original article by CSDN blogger “A Cup of Sweet Wine” and follows the CC 4.0 BY-SA copyright agreement. Please attach the original source link and this statement when reprinting.

Original link: https://blog.csdn.net/u012562943/article/details/100136531