An algorithm is a set of well-defined rules used to solve a problem in a limited number of steps. To put it simply, it is the process of computer solving problems. In this process, whether you are forming a problem-solving idea or writing a program, you are implementing a certain algorithm. The former is an algorithm implemented by reasoning, and the latter is an algorithm implemented by operation.
An algorithm should have the following five important characteristics:
1. Finiteness: An algorithm must ensure that it ends after executing a finite number of steps;
2. Exactness: Each step of the algorithm must be clearly defined;
3. Input: An algorithm has 0 or more inputs to describe the initial situation of the operand;
4. Output: An algorithm has one or more outputs to reflect the results of processing the input data. An algorithm without an output is meaningless;
5. Feasibility: In principle, the algorithm can run accurately, and it can be completed by people using pen and paper to perform a limited number of operations.
Merge sort (MERGE SORT) is another type of different sorting method. The meaning of merging is to merge two or more ordered data sequences into a new ordered data sequence, so it is also called a merge algorithm. Its basic idea is to assume that array A has N elements, then array A can be regarded as consisting of N ordered subsequences, each subsequence has a length of 1, and then merged two by two to obtain an N/2 An ordered subsequence of length 2 or 1 is then merged two by two, and this is repeated until an ordered data sequence of length N is obtained. This sorting method is called 2-way merge sorting.
For example, array A has 7 data, which are: 49 38 65 97 76 13 27. Then the operation process of using the merge sort algorithm is shown in Figure 7:
Initial value[49][38][65][97][76][13][27]
Seen as consisting of 7 subsequences of length 1. After the first merger [38 49] [65 97] [13 76] [27]
Seen as consisting of 4 subsequences of length 1 or 2. After the second merger [38 49 65 97] [13 27 76]
Seen as consisting of 2 subsequences of length 4 or 3. After the third merger [13 27 38 49 65 76 97]
Figure 6 Merge sort algorithm process diagram The core operation of the merge algorithm is to merge two adjacent ordered sequences in a one-dimensional array into one ordered sequence. The merging algorithm can also be implemented using a recursive algorithm, which is relatively simple in form, but has poor practicality.
The number of merges in the merge algorithm is a very important quantity. According to calculations, when there are 3 to 4 elements in the array, the number of merges is 2, when there are 5 to 8 elements, the number of merges is 3, and when there are 9 to When there are 16 elements, the number of merges is 4. According to this rule, when there are N subsequences, it can be inferred that the number of merges is
X (2>=N, the smallest X that meets the sub-condition).
Bubble algorithm description:
Before explaining the bubble sort algorithm, let's first introduce an algorithm that puts the largest number among 10 numbers (in array A) at the last position. The algorithm is described as follows:
(1) From array A[1] to A[10], compare two adjacent numbers in pairs. That is, A[1] is compared with A[2], and after the comparison, A[2] is compared with A[3],...and finally A[9] is compared with A[10].
(2) During each comparison, if the previous number is greater than the latter number, the two numbers will be swapped, that is, the larger number will be moved to the back and the smaller number will be moved to the front. For example, in the first comparison, if A[1] is larger than A[2], the values of A[1] and A[2] are interchanged. The figure below uses 6 data to illustrate the above algorithm.
Assume that the 6 data are: A[]=5 7 4 3 8 6
A[1] A[2] A[3] A[4] A[5] A[6]
5 7 4 3 8 6 The first time, A[1]=5 and A[2]=7 are compared, 7>5, no swap is performed.
5 7 4 3 8 6 The second time, A[2]=7 and A[3]=4 are compared, 4<7, swap.
Then the data after the second comparison is 5 4 7 3 8 6
5 4 7 3 8 6 The third time, A[3]=7 and A[4]=3 are compared, 3<7, swap.
Then the data after the third comparison is 5 4 3 7 8 6
5 4 3 7 8 6 The fourth time, A[4]=7 and A[5]=8 are compared, 8>7, no swap is performed.
5 4 3 7 8 6 The fifth time, A[6]=6 and A[5]=8 are compared, 6<8, swap.
Then the fifth and final result is
5 4 3 7 6 8
*************************************************** *****
Description of selection sort algorithm:
Before introducing the selection sorting method, let's introduce an algorithm that puts the smallest number in the first position. Of course, you can also use the bubble sorting method mentioned above. Now we use a new algorithm: Its guiding ideology There is no rush to change the positions. First, check each one starting from A[1]. To see which number is the smallest, write down the position P of the number. After the scan is completed, swap A[P] and A[1]. , then the smallest data in A[1] to A[10] is moved to the front position. The steps of the algorithm are as follows:
1) First, assume that the number in A[1] is the smallest, and note the position P=1 at this time;
2) Compare A[P] and A[I] in sequence (I changes from 2 to 10). During each comparison, if the number in A[I] is smaller than the number in A[P], then I The value is assigned to P, so that P always points to the position of the smallest number currently scanned, that is to say, A[P] is always equal to the smallest number of all scanned numbers. After comparing one by one, P points to the position of the smallest number among the 10 numbers, that is, A[P] is the smallest number among the 10 numbers;
3) Reverse the numbers of A[P] and A[1], then the smallest number will be in A[1], that is, at the front.
If you now repeat this algorithm, but each time it is repeated, the range of the series being compared is moved backward one position. That is, in the second comparison, the range is from the 2nd number to the Nth number. Find the position P of the smallest number within this range, and then swap A[P] and A[2], so that from the 2nd The smallest number from the beginning to the Nth number is in A[2]. The third time is to find the smallest number from the 3rd number to the Nth number, and then put A[P] and A[ 3] Swap... After repeating this process N-1 times, the N numbers in the A array are arranged in order from small to large. This sorting method is selection sorting.
*************************************************** ***************
Insertion sort algorithm description:
By learning the above two methods, you can understand the basic idea of sorting, and you can also arrange any unordered array from large to small (descending order) or small to large (ascending order). Now assume that there is an already ordered data sequence, and it is required to insert a number into this already arranged data sequence, but it is required that the data sequence is still ordered after the insertion. At this time, a new sorting method will be used - Insertion sort method, the basic operation of insertion sort is to insert a data into the ordered data that has been sorted, so as to obtain a new ordered data with the number plus one.
Question: There are N pieces of data in array A, arranged in order from small to large. Enter a number X, and insert the value of X into array A, so that the inserted array A is still arranged in order from small to large.
Then the algorithm to solve this problem is:
1) Find the position where X should be inserted by comparing the size, if it should be placed at the I-th position;
2) Move all array elements starting from I (including I) one position backward, that is, A[I+1]:=A[I];
Quick sort is an improvement on bubble sort. Its basic idea is to divide the data to be sorted into two independent parts through one-way sorting. All the data in one part is smaller than all the data in the other part, and then the two parts of the data are sorted sequentially. For quick sorting, the entire sorting process can be performed recursively, so that the entire data becomes an ordered sequence.
Assume that the array to be sorted is A[1]...A[N]. First, randomly select a data (usually the first data) as the key data, and then put all numbers greater than it in front of it, and all numbers greater than it Large numbers are placed behind it. This process is called quick sorting. The algorithm for quick sort is:
1) Set two variables I and J. When sorting starts, I:=1, J:=N;
2) Use the first array element as the key data and assign it to X, that is, X:=A[1];
3) Search forward from J, that is, search forward from the back (J:=J-1), find the first value less than X, and exchange the two;
4) Search backward from I, that is, search from front to back (I:=I+1), find the first value greater than X, and exchange the two;
5) Repeat steps 3 and 4 until I=J;
For example: the values of array A to be sorted are: (initial key data X:=49)
A[1] A[2] A[3] A[4] A[5] A[6] A[7]:
49 38 65 97 76 13 27
After the first exchange: 27 38 65 97 76 13 49
(After searching from the back according to the third step of the algorithm for the second exchange: 27 38 49 97 76 13 65
(Follow the fourth step of the algorithm and start from the front to find the value >
After the third exchange: 27 38 13 97 76 49 65
(According to the fifth step of the algorithm, the third step of the algorithm will be executed again from the end to find the fourth exchange: 27 38 13 49 76 97 65
(Follow the fourth step of the algorithm and start from the front to find a value greater than X, 97>49, exchange the two, at this time J:=4)
At this time, when executing the third step, it is found that I=J, thus ending the quick sort. The result after quick sort is: 27 38 13 49 76 97 65, that is, all numbers greater than 49 are in 49 , so numbers less than 49 are all in front of 49.
Quick sorting is to call this process recursively - split the data sequence with 49 as the midpoint, perform similar quick sorting on the front part and the back part respectively, thereby completing the quick sorting of the entire data sequence, and finally turn the data sequence into a An ordered sequence. According to this idea, the whole process of quick sorting the above array A is shown in Figure 6:
Initial state {49 38 65 97 76 13 27}
After a quick sort, it is divided into {27 38 13} 49 {76 97 65}
Quickly sort the front and back parts respectively {13} 27 {38}
end end {49 65} 76 {97} 49 {65} end end
*************************************************** *************************
Figure 6 Algorithm description of quick sorting throughout the quick sorting process
1). Suppose N (assuming N=10) numbers are stored in the S array;
2), in S[1. . Take any element in N] as the comparison basis, for example, take T=S[1]. The initial purpose is to determine the position K where T should be in the sorting result. The position of K is: S[1]. . K-1]<=S[K]<=S[K+1..N], that is, the numbers before S[K] are all smaller than S[K], and the numbers after S[K] are all larger than S[ K];
3) Using the divide-and-conquer idea (that is, the strategy of making big and small small) can further improve S[1. . K-1] and S[K+1. . N] The two sets of data are then quickly sorted until there is only one data in the grouping object.
If the specific data is as follows, then the first quick sorting process is:
Array subscript: 1 2 3 4 5 6 7 8 9 10
45 36 18 53 72 30 48 93 15 36
ij
(1) 36 36 18 53 72 30 48 93 15 45
(2) 36 36 18 45 72 30 48 93 15 53
(3) 36 36 18 15 72 30 48 93 45 53
(4) 36 36 18 15 45 30 48 93 72 53
(5) 36 36 18 15 30 45 48 93 72 53