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

This article mainly shows you "how to use the sorting algorithm in C language". The content is easy to understand and clear. I hope it can help you solve your doubts. Let me lead you to study and learn this article "how to use sorting algorithms in C language".

The concept of sorting and its Application

Sorting: the so-called sorting is the operation of arranging a string of records according to the size of one or some of the keywords.

Stability: assume that there are multiple records with the same keywords in the sequence of records to be sorted, and if sorted, the relative times of these records

The order remains unchanged, that is, in the original sequence, r [I] = r [j], and r [I] is before r [j], while in the sorted sequence, r [I] is still before r [j].

The ordered algorithm is stable; otherwise, it is called unstable. Internal sort: a sort in which all data elements are placed in memory.

External sorting: there are too many data elements to be placed in memory at the same time, and the sorting of data cannot be moved between internal and external memory according to the requirements of the sorting process.

Sort application

University ranking:

Next, I will introduce several common sorting algorithms.

Insert sort directly insert sort

Direct insertion sorting is a simple insertion sorting method.

The basic idea: insert the records to be sorted into an ordered sequence one by one according to the size of their key code values, until all the records have been inserted, and get a new ordered sequence.

Implementation of the code

/ / directly insert sort void InsertSort (int* a, int n) {assert (a); / / the incoming array is not a null pointer int i; for (I = 0; I

< n - 1; i++) { int end = i; int x = a[end + 1]; while (end >

= 0) {/ / Ascending if (a [end] > x) {a [end + 1] = a [end]; end-- } else {break;}} a [end + 1] = x;}} Hill sort

Analysis

Hill sorting is pre-arranged before direct sorting, and some extreme data are arranged faster in front of the sequence to form a nearly arranged sequence, and finally a direct insertion sort is carried out.

The principle of pre-arrangement is also insertion arrangement, except that here the array is divided into gap groups, and each group is inserted and sorted separately.

/ / Hill sorts void ShellSort (int* a, int n) {int gap = n; while (gap > 1) {gap / = 2; for (int I = 0; I)

< n - gap; i++) { int end = i; int x = a[end + gap]; while (end >

= 0) {if (a [end] > x) {a [end + gap] = a [end]; end-=gap } else break;} a [end + gap] = x;}

When gap > 1, it is pre-sorted in order to make the array more ordered. When gap = = 1, the array is close to ordered, so it will be very fast. In this way, on the whole, the optimization effect can be achieved. After we implement it, we can compare the performance test.

Select sort directly select sort

Analysis

Each time you traverse the data elements to be sorted, select the smallest (or largest) element and store it at the beginning (or end) of the sequence until all the data elements to be sorted are finished.

Implementation of the code

/ / Select sort void SelectSort (int* a, int n) {int begin = 0, end = n-1

< end) { int mini = begin; for (int i = begin; i a[child]) { child++; } //父节点数据小于子节点就交换 if (a[parent] < a[child]) { Swap(&a[parent], &a[child]); //更新下标 parent = child; child = parent * 2 + 1; } else//否则向下调整完毕 break; }}// 堆排序(升序)建大堆void HeapSort(int* a, int n){ int i; //建大堆 for (i = (n - 1 - 1) / 2; i >

= 0; iMub -) {Adjustdown (a, n, I);} / exchange adjustment for (I = n-1; I > = 0; iMub -) {Swap (& a [0], & a [I]); / / exchange Adjustdown (a, I, 0) with current tail data / / A pair of data at the top of the stack after exchange are adjusted downwards}}

Summary:

Heap sorting uses heap to select numbers, which is much more efficient.

Time complexity: O (N*logN)

Space complexity: O (1)

Stability: instability

Bubble sort of commutative sort

Bubbling sort

Each time traverses the array, compares the adjacent data, and exchanges if it does not meet the sorting requirements.

Implementation of the code

/ / Bubble sort void BubbleSort (int* a, int n) {int I, j; for (I = 0; I

< n - 1; i++)//趟数 { for (j = 0; j < n - 1 - i; j++)//比较次数 { if (a[j] >

A [j + 1]) / / meet the conditions Swap (& a [j], & a [j + 1]); / / Exchange} above is all the content of the article "how to use sorting algorithms in C language". Thank you for reading! I believe we all have a certain understanding, hope to share the content to help you, if you want to learn more knowledge, welcome to follow the industry information channel!

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.