Shulou(Shulou.com)05/31 Report--

This article mainly explains "how to achieve bubble sorting and insertion sorting algorithm in C#". The content of the explanation in this article is simple and clear, and it is easy to learn and understand. let's go deep into the editor's train of thought. Let's study and learn how to achieve bubble sorting and insertion sorting algorithm in C#.

1. Select sort (bubble sort)

Ascending order

Compare the first element with other elements, and if it is compared to other elements, swap to ensure that the element is the smallest. Then compare the second element with the rest to make sure that the second element is the smallest except the first. Cycle through the entire array in turn.

/ Select sort / public class Selection:BaseSort {public static long usedTimes = 0; public Selection () {} public static void Sort (IComparable [] a) {Stopwatch timer = new Stopwatch (); timer.Start (); for (var I = 0; I

< a.Length; i++) { int minIndex = i; for (var j = i + 1; j < a.Length; j++) { if (Less(a[j], a[minIndex])) { Exch(a, j, minIndex); //minIndex = j; } } } //交换次数更少，内循环只交换索引，最后再交换值 //for (var i = 0; i < a.Length; i++) //{ // int minIndex = i; // for (var j = i + 1; j < a.Length; j++) // { // if (Less(a[j], a[minIndex])) // minIndex = j; // } // Exch(a, minIndex, i); //} timer.Stop(); usedTimes = timer.ElapsedMilliseconds; } } 该算法的内循环是拿当前元素跟其他元素比较，交换元素的代码写在内循环之外，每次交换都能排定一个元素，因此交换总次数是 N 。所以算法的时间效率取决于比较的次数。 由代码可知，0 到 N-1 之间的任意 i 会进行一次交换和 N-1-i 次比较，所以总共有 N 次交换和（N-1）+ （N-2）+ ...+2+1 = N(N-1)/2 ~ N^2 / 2次比较。 缺点 为了找出最小元素需要扫描一遍数组，但这并没有为下一篇扫描数组提供什么信息。排序一个有序的数组或一个主键全部相同的数组同样需要和排序随机数组一样的时间。 优点 数据移动少。交换次数和数组大小是线性的。 2.插入排序 把一个元素插入一个有序的数组，右边元素需要右移一位。 与选择排序一样，当前索引左边的所有元素都是有序的，但它们的最终位置还不确定，为了给更小的元素腾出空间，它们可能会被移动。当索引达到最右端时，数组排序就完成了。初始时，可以认为第一个元素就是一个有序的数组。 和选择排序不同的是，插入排序所需的时间取决于元素的初始顺序。一个对部分有序的数组会比对随机数组排序要快的多。 public class Insertion : BaseSort { public static long usedTimes = 0; public static void Sort(IComparable[] a) { Stopwatch timer = new Stopwatch(); timer.Start(); /* * 将当前位置的值与前一个比较，如果小就互换， * 然后用前一个位置的值继续, * 直到遇到比它大的值，停止内循环、 * 相当于拿当前值跟左边有序数组依次比较，如果当前值小就交换，如果遇到比当前值大的元素就跳出内循环，说明已经找到合适的位置了。 */ for (var i = 0; i < a.Length; i++) { for (var j = i; j >

0 & & Less (a [j], a [j-1]); jmurm -) {Exch (a, j, j-1) }} / * * temp stores the current value * and compares the temp with the value on the left one by one * if the temp is small, move the compared value one bit to the right Until it encounters a number larger than temp or ends * put temp in the current position + 1 * / int N = a.Length / / for (int I = 1; I

< N; i++) //{ // IComparable temp = a[i]; // int j; // for (j = i - 1; j >

= 0 & & Less (temp, a [j]); usedTimes -) / {/ a [j + 1] = a [j]; / / a [j + 1] = temp; / /} timer.Stop (); usedTimes = timer.ElapsedMilliseconds;}}

In the worst case (reverse order), the insertion sort requires ~ N ^ 2 / 2 comparisons and ~ N ^ 2 / 2 swaps. Because each cycle requires I comparisons and exchanges (1+2.+N-1) * N.

For the best case (all ordered), the insertion sort requires 1 comparison and 0 swaps. Because it is orderly, there is no need for exchange, only for each loop comparison.

For randomly arranged arrays, the average insertion sort requires ~ N ^ 2 / 4 comparisons and ~ N ^ 2 / 4 swaps. Random array it is possible for each element to move half the length of the array on average.

The number of insertion sort comparisons is the number of exchanges plus an additional item, which is N minus the number of times that the element being inserted is exactly the smallest known element. At best (all ordered), each element is the smallest known element, so this term is Nmur1.

Insertion sorting is effective for non-random arrays (partially ordered). For example, an ordered array or an array with the same primary key has a linear run time.

Now consider the general situation is a partially ordered array. Inversion refers to two elements in an array that are in reverse order. For example, there are 11 pairs of inversion in E X A M P L E: Emura, Xmura, Xmurm M, Xmurp, Xmurl L, Xmure E, Mmurl L, Mmure E, Pmurl L, Pmure E, Lmure. If the number of inverts in the array is less than a multiple of the size of the array, the array is partially ordered.

Here is a typical partially ordered array:

Each element in the array is not far from its final position

An ordered large array followed by a small array

The position of only a few elements in the array is uncertain

When the number of inverts is small, insert sorting may be faster than any sorting algorithm.

The insertion sort requires the same number of swaps as the number of inverts in the array, and each swap is equivalent to reducing a pair of inverts. The number of times you need to compare is greater than or equal to the number of inversion, less than or equal to the number of inversion plus the size of the array minus one. Because each I between 1 and Nmur1 needs to be compared, and then each exchange corresponds to a comparison, there may be an intersection between the two comparisons, so it is less than or equal to.

The above insert sorting algorithm code is swapped whenever it encounters something larger than the current element. You can optimize this block, and the code commented above can reduce the number of array visits.

The run time of the insert sort is about half that of the selected sort.

Thank you for your reading, the above is the content of "how to achieve bubble sorting and insertion sorting algorithm in C#". After the study of this article, I believe you have a deeper understanding of how to achieve bubble sorting and insertion sorting algorithm in C#. The specific use of the situation also needs to be verified in practice. Here is, the editor will push for you more related knowledge points of the article, welcome to follow!

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.