Shulou(Shulou.com)06/01 Report--

In this issue, the editor will bring you about the sorting algorithm and its C implementation. The article is rich in content and analyzes and describes it from a professional point of view. I hope you can get something after reading this article.

Sorting algorithm (Sorting Algorithm) is a part of computer algorithm.

The goal of sorting is to rearrange a set of data (that is, a sequence) in the order from large to small (or from small to large). This is an old but still challenging question. The third volume of Donald Knuth's classic Art of computer programming (The Art of Computer Programming) is devoted to sorting and finding. From disorder to order, it effectively reduces the entropy of the system and increases the degree of order of the system. Ordering is very useful a priori knowledge for an unknown system. Therefore, sorting algorithms often form the basis of other fast algorithms, such as dichotomy is a search algorithm based on ordered sequences. Until today, sorting algorithm is still an active exploration direction of computer science.

I list some of the most common sorting methods here and try to implement them in the C language. A set of data is stored as an array a, which has n elements. A [I] is an element in the array, and I is the position of the element in the array (index). According to C, the array subscript starts at 0. Suppose the array is arranged from left to right, and the element with subscript 0 is on the far left of the array.

The sequence will eventually be arranged from small to large. The parameter ac in the following function is the number of elements in the array, that is, n.

(the array names in C language are all converted to pointers and passed to the function, so you need to pass the number of elements in the array ac to the function, see "Expert C Programming: Deep C Secrets" for details.)

Starting sequence (unsorted)

Ordered sequence (sorted)

Bubble sort (Bubble Sort)

For a sequence that has been sorted, any two adjacent elements of it should satisfy a [I-1] j; I muri -) {if (a [I-1] > a [I]) {sign = 1; swap (axii, a+i-1);}} if (sign = = 0) break;}

Insert sort (Insertion Sort)

Suppose we line up the freshmen according to their height when they check in. If a student joins us at this time, we will add that student to the end of the line. If the student is lower than the previous student, let the student change places with the previous student. The student will eventually change to his proper position. This is the basic principle of insertion sorting.

For the starting array, we think that initially, there is a student, that is, the leftmost element (item0), to form an orderly team.

Then a second student (iTun1) joins the team, the second student exchanges to where he should be, and then the third student joins the team, and the third student exchanges to where he should be. When all the n students join the team, our ranking is finished.

/ * By Vamei*//*insert the next element into the sorted part*/void insert_sort (int a [], int ac) {/ * use swap*/ int iJournal j; for (jung1; j)

= 0) & & (a [iTun1] < a [I]) {swap (a+i+1, ahumi); iMurmuri;}} Select sort (Selection Sort)

The final result of the sort: no element is larger than the element to its right (a [I]

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.