The sorting algorithm is a substantially and common algorithm. Sorting algorithm is sorted due to huge amounts in actual work
The speed of the algorithm itself is high.
And the performance of our so-called algorithm is mainly the complexity of the algorithm, generally expressed in an O method. I will
A detailed description is given.
For sorting algorithms, I want to do a simple introduction first, and give this article an outline.
I will analyze the algorithm from simple to difficulty in accordance with the complexity of the algorithm.
The first part is a simple sort algorithm, and later you will see their common point is O (n * n) (because no
Use Word, so you can't play the marketer and the subscript).
The second part is the advanced sort algorithm, complexity is O (log2 (n)). Here we only introduce one algorithm. There are still several
The algorithm is not discussed here because it involves the concept of the tree and the heap.
The third part is similar to the brain. The two algorithms here are not the best (even the slowest), but the algorithm itself compares
Strange, worth reference (programming angle). At the same time, we can let us know this issue from another perspective.
The fourth part is a meal after I gave you a meal - a template-based universal rapid sort. Because it is a template function
You can sort any data type (sorry, some forum experts are used).
Now let's get started:
First, simple sort algorithm
Since the program is relatively simple, there is no comment. All programs give full running code and in my VC environment
Upload. Because there is no content involving the MFC and Windows, there should be no more on the platform of Borland C .
questionable. After the code is given, the running process is given, I hope to help understand.
Expeed method:
This is the most primitive, and it is also the slowest algorithm. The origin of his name is because of its work seems to be bubbling:
#include
Void bubblesort (int * pdata, int count)
{
INT ITEMP;
For (int i = 1; i { For (int J = count-1; j> = i; j -) { IF (PDATA [J] { Itemp = pdata [j-1]; PDATA [J-1] = PDATA [J]; PDATA [J] = ItemP; } } } } void main () { INT data [= {10, 9, 8, 7, 6, 5, 4}; Bubblesort (Data, 7); For (int i = 0; i <7; i ) COUT << Data [i] << " Cout << "/ n"; } Reverse (worst) First round: 10, 9, 8, 7-> 10, 9, 7, 8-> 10, 7, 9, 8-> 7, 10, 9, 8 (exchange 3 times) The second round: 7, 10, 9, 8-> 7, 10, 8, 9-> 7, 8, 10, 9 (exchange 2 times) First round: 7, 8, 10, 9-> 7, 8, 9, 10 (exchange 1 time) Number of cycles: 6 times Exchange number: 6 times other: First round: 8, 10, 7, 9-> 8, 10, 7, 9-> 8, 7, 10, 9-> 7, 8, 10, 9 (exchange 2 times) Second round: 7, 8, 10, 9-> 7, 8, 10, 9-> 7, 8, 10, 9 (exchange 0 times) First round: 7, 8, 10, 9-> 7, 8, 9, 10 (exchange 1 time) Number of cycles: 6 times Exchange number: 3 times Above we give the block, now we analyze it: Here, the main part of affecting our algorithm performance is cycle and exchange, obviously, the number of times, the poor performance. From the above program we can see that the number of cycles is fixed, 1 2 ... N-1. The formula is 1/2 * (n-1) * n. Note now, we give a definition of the O method: If there is a constant K and the starting point N0, when n> = N0, F (n) <= k * g (n) is present, then f (n) = O (g (n)). (Oh, don't say no Learn more than mathematics, it is very important for programming mathematics! ! ! ) Now let's see 1/2 * (n-1) * n, when K = 1/2, N0 = 1, g (n) = n * n, 1/2 * (n-1) * n <= 1/2 * n * n = k * g (n). So f (n) = O (g (n)) = O (n * n). Therefore, our program cycle has an complexity of o (n * n). Look at the exchange. The table followed by the program can be seen, the cycles of the two cases are the same, and the exchange is different. In fact, exchange itself with data source Ordered levels have a great relationship, when the data is inverted, the number of exchanges is the same as the cycle (each cycle is judged), The complexity is O (n * n). When data is a positive order, there will be no exchange. The complexity is O (0). In the middle of the chart. It is because of this Cause, we are usually comparable to the number of cycles. 2. Exchange method: The program of the exchange method is the clearest and simple, and each time it is compared and exchanged with the current elements. #include Void ExchangeEsort (int * pdata, int count) { INT ITEMP; For (INT i = 0; i { For (int J = i 1; j { IF (PDATA [J] PDATA [I]) { Itemp = pdata [i]; PDATA [I] = PDATA [J]; PDATA [J] = ItemP; } } } } void main () { INT data [= {10, 9, 8, 7, 6, 5, 4}; Exchangesort (Data, 7); For (int i = 0; i <7; i ) COUT << Data [i] << " Cout << "/ n"; } Reverse (worst) First round: 10, 9, 8, 7-> 9, 10, 8, 7-> 8, 10, 9, 7-> 7, 10, 9, 8 (exchange 3 times) The second round: 7, 10, 9, 8-> 7, 9, 10, 8-> 7, 8, 10, 9 (exchange 2 times) First round: 7, 8, 10, 9-> 7, 8, 9, 10 (exchange 1 time) Number of cycles: 6 times Exchange number: 6 times other: The first round: 8, 10, 7, 9-> 8, 10, 7, 9-> 7, 10, 8, 9-> 7, 10, 8, 9 (exchange 1 time) The second round: 7, 10, 8, 9-> 7, 8, 10, 9-> 7, 8, 10, 9 (exchange 1 time) First round: 7, 8, 10, 9-> 7, 8, 9, 10 (exchange 1 time) Number of cycles: 6 times Exchange number: 3 times From the work-run table, exchange is almost as bad as the bubble. The fact is indeed true. The number of cycles and the bubbling is also 1/2 * (n-1) * n, so the complexity of the algorithm is still O (n * n). Since we can't give all the situation, Can only tell you directly that they are also the same as the same is true (slightly better in some cases, slightly poor in some cases). 3. Select: Now we can finally see a point: the choice method, this method has improved a little performance (in some cases) This method is similar to our artificial sorting habits: the minimum exchange is exchanged from the data, in the part of the other part Choose the minimum and second exchange, so that you recover. #include Void SelectSort (int * pdata, int count) { INT ITEMP; INT IPOS; For (INT i = 0; i { Itemp = pdata [i]; IPOS = i; For (int J = i 1; j { IF (PDATA [J] { Itemp = pdata [j]; IPOS = J; } } PDATA [IPOS] = PDATA [i]; PDATA [I] = itemp; } } void main () { INT data [= {10, 9, 8, 7, 6, 5, 4}; SelectSort (Data, 7); For (int i = 0; i <7; i ) COUT << Data [i] << " Cout << "/ n"; } Reverse (worst) First round: 10, 9, 8, 7-> (itemp = 9) 10, 9, 8, 7 -> (itemp = 8) 10, 9, 8, 7 -> (itemp = 7) 7, 9, 8, 10 (exchange 1 time) The second round: 7, 9, 8, 10-> 7, 9, 8, 10 (itemp = 8) -> (itemp = 8) 7, 8, 9, 10 (exchange 1 time) First round: 7, 8, 9, 10 -> (itemp = 9) 7, 8, 9, 10 (exchange 0 times) Number of cycles: 6 times Exchange number: 2 times other: First rounds: 8, 10, 7, 9 -> (itemp = 8) 8, 10, 7, 9 -> (itemp = 7) 8, 10, 7, 9 -> (itemp = 7) 7, 10, 8, 9 (exchange 1 time) Second Wheel: 7, 10, 8, 9 -> (itemp = 8) 7, 10, 8, 9 -> (itemp = 8) 7, 8, 10, 9 (exchange 1 time) First round: 7, 8, 10, 9 -> (itemp = 9) 7, 8, 9, 10 (exchange 1 time) Number of cycles: 6 times Exchange number: 3 times Unfortunately, the number of cycles required by the algorithm is still 1/2 * (n-1) * n. Therefore, the algorithm complexity is O (n * n). Let's see his exchange. Since each outer cycle only generates a exchange (only one minimum). So f (n) <= n So we have F (n) = O (n). Therefore, when the data is chaotic, it can reduce a certain number of exchanges. 4. Insert: The insert is more complicated. Its basic working principle is to draw a card, looking for the corresponding location in the previous card, then continue the next one #include Void insertsort (int * pdata, int count) { INT ITEMP; INT IPOS; For (int i = 1; i { Itemp = pdata [i]; IPOS = I-1; While ((iPOS> = 0) && (itemp { PDATA [IPOS 1] = PDATA [IPOS]; IPOS-- } PDATA [IPOS 1] = ItemP; } } void main () { INT data [= {10, 9, 8, 7, 6, 5, 4}; INSERTSORT (DATA, 7); For (int i = 0; i <7; i ) COUT << Data [i] << " Cout << "/ n"; } Reverse (worst) First round: 10, 9, 8, 7-> 9, 10, 8, 7 (exchange 1 time) (1 time) The second round: 9, 10, 8, 7-> 8, 9, 10, 7 (exchange 1 time) (2 times a cycle) The first round: 8, 9, 10, 7-> 7, 8, 9, 10 (exchange 1 time) (3 times a cycle) Number of cycles: 6 times Exchange number: 3 times other: First round: 8, 10, 7, 9-> 8, 10, 7, 9 (exchange 0 times) (1 cycle) The second round: 8, 10, 7, 9-> 7, 8, 10, 9 (exchange 1 time) (2 times a cycle) First round: 7, 8, 10, 9-> 7, 8, 9, 10 (exchange 1 time) (1 time) Number of cycles: 4 times Exchange number: 2 times Behavioral analysis ended in facts, it has caused a description, let us think this algorithm is the best in simple algorithm, in fact, no, Because the number of cycles is not fixed, we can still use the O method. As can be seen from the above results, the number of cycles f (n) <= 1/2 * n * (N-1) <= 1/2 * n * n. Therefore, its complexity is still o (n * n) (herein, in fact, if it is not to show these simple Different sorting, the number of exchanges can still be derived). Now, exchange, from the appearance, the number of exchanges is o (n) (derived similar The selection method), but we have to perform the '=' operation of the same number of inner cycles each time. Normal exchange we need three times '=' And it is obviously more, so we waste time. In the end, I personally think that in the simple sort algorithm, the choice method is best. Second, advanced sorting algorithm: In the advanced sorting algorithm, we will only introduce this, and it is the fastest in my current (I have seen the information). Its work looks still like a binary tree. First we chose a middle value middle program we use the array intermediate value, then Put the left side than it, the big place is on the right (the specific implementation is found from both sides, find a pair of posts). Then the two sides are respectively Use this process (the easiest way - recursive). 1. Quick sort: #include Void Run (int * PDATA, INT LEFT, INT RIGHT) { INT I, J; Int middle, itemp; i = Left; J = Right; Middle = PDATA [(Left Right) / 2]; // Seeking intermediate value Do { While ((PDATA [i] While ((PDATA [J]> Middle) && (j> LEFT)) // From the right scan greater than the medium value J -; IF (i <= j) // found a pair of values { //exchange Itemp = pdata [i]; PDATA [I] = PDATA [J]; PDATA [J] = ItemP; i ; J -; } } while (i <= j); // stop (complete once) if the subscript is interlaced in both sides / / When the left part is value (Left IF (Left Run (PDATA, LEFT, J); / / When a part of the right side (Right> i), recursive right half IF (Right> i) Run (PDATA, I, RIGHT); } Void Quicksort (INT * PDATA, INT COUNT) { Run (PDATA, 0, Count-1); } void main () { INT data [= {10, 9, 8, 7, 6, 5, 4}; Quicksort (DATA, 7); For (int i = 0; i <7; i ) COUT << Data [i] << " Cout << "/ n"; } Here I didn't give an analysis of behavior, because this is very simple, we directly analyze the algorithm: First we consider the ideal situation 1. The magnitude of the array is 2 power, so that it can always be divided by 2. Assume that K = log2 (n) is assumed to be 2. 2. Each time we have selected is just an intermediate value, so that the array can be aliquoted. The first layer recursive, circulating N times, the second layer cycle 2 * (N / 2) ... So there is N 2 (N / 2) 4 (N / 4) N * (N / N) = N N ... N = K * n = log2 (n) * n Therefore, the algorithm has a complexity of O (log2 (n) * n) Other situations are only poor than this situation, the worst case is that each selected Middle is the minimum or maximum, then he will change Becoming method (due to the use of recursion, the situation is worse). But how big is you think of this situation? ? Oh, you are completely Don't worry about this problem. Practice has proved that most cases, rapid sorting is always best. If you are worried about this problem, you can use the heap sorting, this is a stable O (log2 (n) * n) algorithm, but usually the speed is slow Sort quickly (because of the restructuring stack). Third, other sort 1. Bidirectional bubble: Usually bubbles are unidirectional, and here is two-way, that is, the reverse operation is necessary. The code looks complicated. If you care about it, it is a way to go back and forth. The author writes this code believes that this can reduce some exchanges on the basis of the bubble (I don't think so, maybe I am wrong). Anyway, I think this is a fun code, it is worth seeing. #include Void Bubble2Sort (int * PDATA, INT COUNT) { INT ITEMP; INT LEFT = 1; INT Right = count -1; Int T; DO { // forward part For (int i = right; i> = left; i -) { IF (PDATA [i] { Itemp = pdata [i]; PDATA [I] = PDATA [I-1]; PDATA [I-1] = itemp; T = I; } } Left = t 1; // Reverse part For (i = left; i { IF (PDATA [i] { Itemp = pdata [i]; PDATA [I] = PDATA [I-1]; PDATA [I-1] = itemp; T = I; } } Right = T-1; WHILE (LEFT <= Right); } void main () { INT data [= {10, 9, 8, 7, 6, 5, 4}; Bubble2sort (Data, 7); For (int i = 0; i <7; i ) COUT << Data [i] << " Cout << "/ n"; } 2. SHELL sort This sort is very complicated. I will know if I have read the program. First, a decreasing step is required, where we use 9, 5, 3, 1 (the last step must be 1). The working principle is first sorted by all of the contents of 9-1 elements, and then use the same method to sort the 5-1 elements separated by the same method. Push it by secondary. #include Void shellsort (int * pdata, int COUNT) { Int Step [4]; Step [0] = 9; Step [1] = 5; Step [2] = 3; Step [3] = 1; INT ITEMP; INT K, S, W; For (int i = 0; i <4; i ) { K = step [i]; s = -k; For (int J = k; j { Itemp = pdata [j]; W = j-k; // ask the subscript of STEP elements IF (s == 0) { s = -k; S ; PDATA [S] = itemp; } While (itemp { PDATA [W K] = PDATA [W]; W = W-K; } PDATA [W K] = ItemP; } } } void main () { INT data [] = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1, -10, -1}; Shellsort (DATA, 12); For (int i = 0; i <12; i ) COUT << Data [i] << " Cout << "/ n"; } Oh, the program looks a little headache. But it is not very difficult, it's easy to remove the block of s == 0, here is to avoid using 0 The steps written by the steps caused by the process. I think it is worth seeing this code. This algorithm is named because the name of the inventors D.L.Shell. According to the reference, "" due to complex mathematics reasons Avoid using 2 power steps, it can reduce algorithm efficiency. "Different algorithms have a 1.2 power of N, which is also because it is very complex and" exceeding the discussion of this book "(I don't know the process), we only have the result. Fourth, the common sort of template is: I want to have no analysis of this program, you can see it. I don't understand, I can ask in the forum. MyData.h file /// Class CMYDATA { PUBLIC: CMYDATA (INT INDEX, CHAR * STRDATA); CMYDATA (); Virtual ~ cmydata (); INT M_IINDEX; INT getDataSize () {return m_idatasize;}; Const char * getdata () {return m_StrDataMember; / / Here, the operator is overloaded: CMYDATA & OPERATOR = (CMYDATA & SRCDATA); Bool Operator <(CMYDATA & DATA); BOOL Operator> (CMYDATA & DATA); Private: Char * m_strdatamember; INT m_idataze; } MyData.cpp file CMYDATA :: CMYDATA (): m_iindex (0), m_idatasize (0), M_StrDataMember (NULL) { } CMYDATA :: ~ CMYDATA () { IF (m_strdatamember! = null) DELETE [] M_STRDATAMEMBER; m_StrDataMember = NULL; } CMYDATA :: CMYDATA (int Index, Char * STRDATA): m_iindex (index), m_idatasize (0), M_StrDataMember (NULL) { m_idatasize = Strlen (strdata); M_StrDataMember = new char [m_idatasize 1]; STRCPY (M_StrDataMember, strdata); } CMYDATA & CMYDATA :: Operator = (CMYDATA & SRCDATA) { m_iindex = srcdata.m_iindex; m_idataasize = srcdata.getDataSize (); M_StrDataMember = new char [m_idatasize 1]; STRCPY (m_strdatamember, srcdata.getdata ()); RETURN * THIS; } Bool CMYDATA :: Operator <(CMYDATA & DATA) { Return M_IINDEX } Bool CMYDATA :: Operator> (CMYDATA & DATA) { Return M_IINDEX> DATA.M_IINDEX; } /// // // Main program part #include #include "mydata.h" Template Void Run (T * PDATA, INT LEFT, INT RIGHT) { INT I, J; T middle, itemp; i = Left; J = Right; // The following comparison calls our heavy load operator function Middle = PDATA [(Left Right) / 2]; // Seeking intermediate value Do { While ((PDATA [i] i ; While ((PDATA [J]> Middle) && (j> LEFT)) // From the right scan greater than the medium value J -; IF (i <= j) // found a pair of values { //exchange Itemp = pdata [i]; PDATA [I] = PDATA [J]; PDATA [J] = ItemP; i ; J -; } } while (i <= j); // stop (complete once) if the subscript is interlaced in both sides / / When the left part is value (Left IF (Left Run (PDATA, LEFT, J); / / When a part of the right side (Right> i), recursive right half IF (Right> i) Run (PDATA, I, RIGHT); } Template Void Quicksort (T * PDATA, INT COUNT) { Run (PDATA, 0, Count-1); } void main () { CMYDATA DATA [] = { CMYDATA (8, "xulion"), CMYDATA (7, "Sanzoo"), CMYDATA (6, "wangjun"), CMYDATA (5, "vckbase"), CMYDATA (4, "jacky2000"), CMYDATA (3, "cwally"), CMYDATA (2, "vcuser"), CMYDATA (1, "isdong") } Quicksort (DATA, 8); For (int i = 0; i <8; i ) COUT << Data [i] .m_iindex << "" << data [i] .Getdata () << "/ n"; Cout << "/ n"; }
