[4] Select sort
Basic thinking is: Electing the number I of the record, put in the i-th position (i's starting point is 0, according to this, the 0th small record is actually the smallest, there is a little awkward, no matter how much) . When I = N-1 is finished.
Direct selection
Direct election is simple and reproduce the basic idea of selecting sort. The price of the first look for the minimum element is O (n). If you do not do some special processing, you will use the simplest search method every time you use the easiest way to find the time. The complexity is O (N2).
Template
Void Selectsort (T A [], INT N, INT & KCN, INT & RMN)
{
KCN = 0; RMN = 0;
For (int i = 0; i { For (int J = i 1, k = i; j IF (k! = i) {swap (a [k], a [i]); RMN = 3; } } Test Results: Sort ascending n = 10000 timeespared: 721ms KCN = 49995000 kcn / n = 4999.5 kcn / n ^ 2 = 0.49995 kcn / nlogn = 376.25 RMN = 0 RMN / N = 0 RMN / N ^ 2 = 0 RMN / NLOGN = 0 Sort randomness n = 10000 Timespared: 711ms KCN = 49995000 kcn / n = 4999.5 kcn / n ^ 2 = 0.49995 kcn / nlogn = 376.25 RMN = 29955 RMN / N = 2.9955 RMN / N ^ 2 = 0.00029955 RMN / NLOGN = 0.225434 Sort descending n = 10000 timeespared: 711ms KCN = 49995000 kcn / n = 4999.5 kcn / n ^ 2 = 0.49995 kcn / nlogn = 376.25 RMN = 15000 rmn / n = 1.5 rmn / n ^ 2 = 0.00015 RMN / NLOGN = 0.112886 It can be seen that the KCN is fixed to N (N-1) / 2. Another interesting thing is that the normal time of RMN = 0 is still more sequences close to 3 (N-1) in RMN. First, the test accuracy is not enough, and the floating 10ms in my machine is more frequently floating 10ms; the second is that the N (N-1) / 2 of KCN is 3 (N-1) of RMN. Some are slightly short. Champion sort From direct sequencing, the bottleneck of the algorithm is KCN, and in fact, for subsequent search minimum, the time complexity can be reduced to O (logn). The most direct practice is to use the tournament method. After the champion is taken away, just put the championship over again, then the "champion" in the remaining people will produce, and the number of race is the competition tree depth. When you are actually written, you can't get "stupid", not only a lot of memory, which will also lead to useless judgment. I have never seen a satisfactory routine (I am too disgusting in Yin version), I can't write it again, and I don't show ugly (in fact, this is inert, there is a quick row, most People will not interested in other internal, except for the base sorting). When you are bored, you may wish to write (or improve) the champion sort to send time, ^ _ ^. Stack sort There are too many additional storage of the champion sort, and the maximum value or minimum value is high efficient, and we have a plot. Here, the maximum heap is used, and the space to be recorded is used as a stack of space, and the last record of the top record (current maximum) and the stack is exchanged. When the heap gradually shrinks into 1, the record is sorted. Obviously, the time complexity is O (nlogn), and there is no worse case. Template Void Filterdown (T A [], INT I, INT N, INT & KCN, INT & RMN) { INT child = 2 * i 1; t temp = a [i]; While (Child { CHILD IF ( KCN && Temp> = a [child]) BREAK; / / Do not need to be adjusted, end adjustment a [i] = a [child]; RMN ; i = child; child = 2 * i 1; } A [I] = TEMP; RMN ; } Template Void Heapsort (T A [], INT N, INT & KCN, INT & RMN) { INT I; For (i = (n - 2) / 2; i> = 0; I -) FilterDown For (i = n - 1; i> 0; I -) { SWAP (a [0], A [i]); RMN = 3; FilterDown (A, 0, I, KCN, RMN); } } Test results, direct testing n = 100000: Sort ascending n = 100000 Timespared: 110ms KCN = 1556441 kcn / n = 15.5644 kcn / n ^ 2 = 0.000155644kcn / nlogn = 0.937071 RMN = 2000851 RMN / N = 20.0085 RMN / N ^ 2 = 0.000200085RMN / NLOGN = 1.20463 Sort randomness n = 100000 Timespared: 160mskcn = 3047006 kcn / n = 30.4701 kcn / n ^ 2 = 0.000304701kcn / nlogn = 1.83448 RMN = 3898565 RMN / N = 38.9857 RMN / N ^ 2 = 0.000389857RMN / NLOGN = 2.34717 Sort descending n = 100000 Timespared: 90ms KCN = 4510383 kcn / n = 45.1038 kcn / n ^ 2 = 0.000451038kcn / nlogn = 2.71552 RMN = 5745996 RMN / N = 57.46 RMN / N ^ 2 = 0.0005746 RMN / NLOGN = 3.45943 The overall performance is very good, the additional storage is 1, there is nothing wrong, if you really don't feel the worst case, the stack is really a good choice. There is still a case where KCN, RMN is more expensive - error 70ms is impossible, it seems that the role of CPU optimization is still very obvious (possibly related to cache).
