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

This article mainly explains "C language sorting algorithm example analysis". The explanation content in this article is simple and clear, easy to learn and understand. Please follow the idea of Xiaobian and go deep into it slowly to study and learn "C language sorting algorithm example analysis" together.

1. Direct insertion sort

Basic idea: When inserting the i(i>=1) th element, the previous array[0],array[1],…,array[i-1] have been sorted. At this time, compare the sorting code of array[i] with the sorting code order of array[i-1],array[i-2],…, and find the insertion position, i.e., insert array[i]. The order of the elements in the original position is shifted backward!

Summary of features of direct insertion sort:

1. The closer the set of elements is to order, the more time efficient the direct insertion sort algorithm is.

2. Time complexity: O(N^2), space complexity: O(1)

3. Stability: Stable

void InsertSort(int* a, int n){ //insert sort directly---ascending for (int i = 0; i

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

= 0) { if (a[i] > tmp) //move back if larger than tmp { a[end + 1] = a[end]; --end; } else //If tmp is larger than the current element, then there is no need to swap positions, directly jump out of the loop! { break; } } a[end + 1] = tmp; //Finally put tmp after the element smaller than it! }}2. Hill sort (reduce incremental sort)

Basic idea: First select an integer, divide all records in the file to be sorted into groups, divide all records with gap distance into the same group, and sort the records in each group. Then repeat the grouping and sorting process. When gap=1 is reached, all records are sorted in a unified group.

Summary of Hill Sort Features:

1. Hill sort is an optimization of direct insertion sort.

2. When gap > 1 is pre-sorted, the purpose is to make the array closer to order. When gap == 1, the array is close to ordered, and so it will be very fast. In this way, overall, the optimization effect can be achieved.

3. The time complexity of Hill sorting is not easy to calculate. It needs to be derived. The average time complexity is derived: O(N^1.3- N^2).

4. Stability: Unstable

void ShellSort(int* a, int n){ //Hill Sort---Ascending int gap = n; while (gap > 1) { gap = gap / 2; for (int i = 0; i

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

= 0) { if (a[end] > tmp) { a[end + gap] = a[end]; end = end - gap; } else { break; } a[end + gap] = tmp; } } }}3, direct selection sorting

Basic idea:

Select the data element with the largest (smallest) key in the element set array[i]--array[n-1]. If it is not the last (first) element in the set, swap it with the last (first) element in the set in the remaining array[i]--array[n-2](array[i+1]--array[n-1]) set, and repeat the above steps until there is one element left in the set.

Summary of characteristics of direct selection sorting: (because it is particularly simple, it does not draw directly on the code)

1. Direct selection sorting thinking is easy to understand, but not very efficient. Very rarely used in practice

2. Time complexity: O(N^2), space complexity: O(1)

3. Stability: Unstable

Here we use an optimized version that determines the final position of two numbers at a time:

void Swap(int* p1, int* p2){ int tmp = *p1; *p1 = *p2; *p2 = tmp;} void SelectSort(int* a, int n){ int begin = 0; int end = n - 1; while (begin

< end) { int min = begin; int max = begin; for (int i = begin; i a[max]) { max = i; } } Swap(&a[min], &a[begin]); if (max == begin) //如果max等于begin的话就证明最大值是begin的位置 //需要修正max的位置 { max = min; } Swap(&a[max], &a[end]); ++begin; --end; }}4、堆排序 堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的 一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。 堆排序的特性总结： 1. 堆排序使用堆来选数，效率就高了很多。 2. 时间复杂度：O(N*logN) 、空间复杂度：O(1) 3. 稳定性：不稳定 void AdjustDown(int* a, int n, int root){ int parent = root; int child = parent * 2 + 1; while (child < n) { if (child + 1 < n && a[child] < a[child + 1]) { child = child + 1; } if (a[child] >

a[parent]) { Swap(&a[child], &a[parent]); parent = child; child = parent * 2 + 1; } else { break; } }} void HeapSort(int* a, int n){ for (int i = (n - 1 - 1) / 2; i >= 0; --i) { AdjustDown(a, n, i); } int end = n - 1; while (end > 0) { Swap(&a[0], &a[end]); AdjustDown(a, end, 0); --end; }} Thank you for reading, the above is the "C language sorting algorithm example analysis" of the content, after the study of this article, I believe that everyone has a deeper understanding of the C language sorting algorithm example analysis, the specific use of the situation also needs to be verified. Here is, Xiaobian will push more articles related to knowledge points for everyone, welcome to pay attention!

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.