COCO Learning Programming (2) - Direct Selection Sort

zhaozj2021-02-11  217

COCO: I haven't come for a long time, I really want everyone, it is too lazy, and I don't come to class.

Me: This ... is really sorry. It is mainly because it has recently been looking for a new job and is rushing a project, relatively busy. There is often a thing that is still coming back, so there is no longer a long time.

COCO: According to I know ~ Someone will go home, because in Guangzhou, there is no time to find the road every time, and because of some of the dishes its stuck……

Me: Why always reveal my short ... -_- #

Coco: Hoho, class in class ~

Me: Ok, I will talk directly to the direct insertion, we start from improving it. In these days, what do you think about this algorithm?

Coco: Read in the book, repeated insertion and deletion node in the container is a very low-efficiency approach, not only slow, it will cause the memory fragmentation, which is like this.

I: Very correct, so usually, we should find a way to reduce the number of insertions and deletions. This can effectively avoid the debris of memory.

Coco: But for the choice of insertion method, we only move the node of the reverse order, what is the way to further reduce this insertion and deletion?

Me: There is a way, it is not to use Del and Insert to display the deletion and insert operation, take advantage of the existing space of the container to switch the node to move it.

Coco: It is not understood.

Me: The easiest way to generate, in such a simple mathematical description, this is such a case, assuming a collection has {A1, A2, A3, ..., AN}, let us find the smallest one from the entire interval Element AM, if it does not equal it to A1, exchange it and the A1; then look for [A2, A3, ..., A] intervals, in which the minimum element is found, if it does not equal it, it will exchange it and A2; Repeat this process, you can sort the entire array.

COCO: It looks very simple, I will try it, the test code segment is used for the last time ~

# 以下 below is the coco code:

#Direct choice sort. It is a sample method.

Def DRTCHCSORT (THEARRY):

#Move the begin of search.

For i in range (len (array):

Curmrk = i

#Find the min node.

For J in Range (I, Len (THEARRY):

IF THEARRAY [J]

Curmrk = j

#Move it to front.

IF not (curmrk == i):

THEARRAY [CURMRK], THEARRAY [i] = THEARRAY [i], thearray [curMrk]

Array = [6, 16, 10, 9, 15, 5, 11, 1, 19, 4, 14, 18, 0, 13, 3, 17, 12, 2, 8, 7]

Print Array

DRTCHCSORT (ARRAY)

Print Array

COCO: This approach is more simpler than the last time, why don't you teach me this?

I: I want you to write these algorithms, it is not really practical, mainly practicing. Otherwise, the easiest way to sort Python's array should be: array.sort ()

COCO: Pour ~ Ok, if you make sense, just exchange the elements in the list directly: "THEARRAY [curmrk], THEARRAY [i] = THEARRAY [i], THEARRAY [curmrk]" really guaranteed memory Will defragment, reduce insertion and deletion?

I: Honestly, I don't know, because Python is encapsulated by the operation of this linear container, from our use layer, it can't be seen. However, we avoid the displayed and deletion of operations. If it is said to program "there may be bad results", the displayed incoming operation is "almost certainly there will be bad results". If the language directly operating in the C language, the effect is very clear. .

Coco: Why do you say "almost"?

I: Because Python has its memory management mechanism, it can be garbage recycled, so the debris and loss of memory will be controlled, especially Jython, due to the use of Java platforms, basically there is no memory. However, it is not a good idea to rely too much, at least give the virtual machine unnecessary burden.

Coco: I have a reasonable look, I still have a question, in this sort, we exchange the elements of the previously sorted intervals directly exchanged with the minimum elements in the unsorted interval, which will not cause the back. The sorting interval is getting more chaotic, give us extra trouble?

I: This type of exchange has indeed increasing confusion - image, just like the possibility of "entropy" in thermo, but if this algorithm only considers a piece of linked list, it is basically not used. From the statistical perspective, "entropy" in the unsorted interval

It will not increase.

COCO: Understand, but this algorithm is too simple, talk more.

Me: I have a friend asking the meaning of recursive, do you know?

Coco: Retroses polynomial, an expression, each of which is determined by the formula used by the previous item.

Me: How to watch this is familiar, where is it?

Coco: Let you see so soon, "Jinshan word tyrant" 喽 ~

I: I will be lazy, simply say that recursive means that it will use itself in a method.

Coco: It sounds weird, let's take a look.

I: European ride algorithm, removing the biggest public factor, how? You will write this app, it's not more difficult.

COCO: I am really lazy ~

DEF GBA (A, B):

R = a% B

IF r == 0:

Return B

Else:

Return (B, R)

COCO: Calling this function can get the biggest average of A and B. This function is a recursive function by calling itself to enter the next step.

I: Yes, the calculation method corresponding to it is iteration, that is, re-record the current state by a method, then generates the algorithm of this state, this does not need to repeat the call function, it is better than recursive than recursive, but Readability is usually different. For example, the recursive form of the GBA (A, B) should be like this:

DEF GBA (A, B):

R = a% B

While r! = 0:

A, B = B, R

R = a% B

Return B

Coco: It seems to be understood. what's next?

Me: When I went to the CN99 news group, I asked what you said in the dish, I have a good response called Chad Netzer, although my problem is delicious (Coco: This stupid will not know in Python How to exchange elements, I also dare to teach others, I am really not awkward ~), but the reply written by this friend is more valuable than my problem. If you have time tomorrow, I translated it to you. . But today, take this, these two days have a cold, not very comfortable, I have to go to work tomorrow. COCO: I have a cold, I said, don't be transmitted to me, flash ~

转载请注明原文地址:https://www.9cbs.com/read-4584.html

New Post(0)