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

Editor to share with you how to achieve selection sorting in c#, I believe most people do not know much about it, so share this article for your reference, I hope you can learn a lot after reading this article, let's learn about it!

Selective sorting (Selection sort) is a simple and intuitive sorting algorithm. It works by selecting the smallest (or largest) element from the data elements to be sorted each time and storing them at the beginning of the sequence until all the data elements to be sorted are finished.

Select sort:

Thought

The direct selection sorting of the files of n records can be sorted through the direct selection sorting of nmur1 times to get the ordered results:

The initial state of ①: the disordered region is R [1.. n], and the ordered zone is empty.

The first sort of ②

The record R [k] with the smallest key in the disordered area R [1... n] is selected and exchanged with the first record R [1] in the disordered area, so that R [1.. 1] and R [2... n] become a new ordered area with an increase in the number of records and a new disordered area with a decrease in the number of records.

……

Sort the first round of ③

At the beginning of the first sequence, the current ordered and disordered regions are R [1. I-1] and R (I. N), respectively. The sequence selects the record R [k] with the smallest key from the current disordered area, and exchanges it with the first record R in the disordered area, so that R [1. I] and R become a new ordered area with an increase in the number of records and a new disordered area with a decrease in the number of records, respectively.

Because there are many implementation methods, but also easy to implement, so only one code below is not the optimal algorithm or some improvement and optimization.

Because the selection sort of improvement and optimization may have BUG, and the implementation is similar to the following code, it is not listed one by one.

Void SelectiongSort (int* a, size_t size) / / Select sort {assert (a); int min; for (int I = 0; I

< size ; i++) { min = i; for (int j = i + 1; j < size; j++) if (a[j] < a[min]) min = j; swap(a[i], a[min]); }} 选择排序的交换操作介于 0 和 (n - 1） 次之间。选择排序的比较操作为 n (n - 1） / 2 次之间。选择排序的赋值操作介于 0 和 3 (n - 1） 次之间。 比较次数O(n^2），比较次数与关键字的初始状态无关，总的比较次数N=(n-1）+(n-2）+...+1=n*(n-1）/2。交换次数O(n），最好情况是，已经有序，交换0次；最坏情况交换n-1次，逆序交换n/2次。交换次数比冒泡排序少多了，由于交换所需CPU时间比比较所需的CPU时间多，n值较小时，选择排序比冒泡排序快。选择排序是给每个位置选择当前元素最小的，比如给第一个位置选择最小的，在剩余元素里面给第二个元素选择第二小的，依次类推，直到第n-1个元素，第n个元素不用选择了，因为只剩下它一个最大的元素了。那么，在一趟选择，如果一个元素比当前元素小，而该小的元素又出现在一个和当前元素相等的元素后面，那么交换后稳定性就被破坏了。 堆排序 堆分为大根堆和小根堆，是完全二叉树。大根堆的要求是每个节点的值都不大于其父节点的值，即A[PARENT[i]] >

= A [I]. In the non-descending sorting of arrays, the large root heap is needed, because according to the requirements of the large root heap, the maximum value must be at the top of the heap.

Since it is a heap sort, it is natural to build a heap first, and the core content of building a heap is to adjust the heap so that the binary tree meets the definition of the heap (the value of each node is not greater than the value of its parent node).

(the picture is intended to be given here, but it will not be given because of the problem of the website. I hope the reader will forgive me. )

Void Adjust (int* a, int I, int size) {assert (a); int parent = i; int child = 2i + 1; while (child)

< size) { if(child+1 < size && a[child+1]>

A [child]) + + child; if (a [parent]

< a[child]) { swap(a[parent],a[child]); parent =child; child = 2*parent +1; } else break; }}void HeapSort(int* a, size_t size) //堆排序{ for(int i = (size-2)/2 ; i >

0;-- I) Adjust (an int I = 0 position I); for (I = 0

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.