This is the 12th day of my participation in the August Challenge

Selection sort

The basic idea of selection sort is: in each trip, select the element with the smallest keyword (or the largest) to be sorted and add it to the ordered subsequence.

Simple selection sort

concept

If the sorting table is L[1… N], the ith sorting is to select the element with the smallest keyword from L[1… N] and swap with L (I), each sorting can determine the final position of an element, so that the whole sorting table can be ordered after n-1 sorting.

Algorithm implementation

void select_sort(ElemType A[],int n) { int i, j,min; for (i = 0; i < n-1; i++) { min = i; For (j = I + 1; j < n; J++) / / in A 【 I... n - 1 】 if choose the smallest element in (A) [j] < A/min) min = j; // Update the minimum element position if (min! = i) swap(A[i],A[min]); }}Copy the code

Heap sort

concept

  1. Heap sorting is learned in combination with the properties of a complete binary tree for sequential storage. For complete binary trees:

  • The left child of node I is 2i

  • The right child of node I is 2i plus 1

  • The parent of node I is I /2

  • Nodes numbered <= n/2 are branch nodes

  1. A sequence of n keywords L[1… n] is called a heap. The one-dimensional array can be treated as a complete binary tree if and only if L(I)>=L(2i) and L(I)>=L(2i+1), and a heap satisfying this condition is called a large root heap. The largest element of the large root heap is stored at the root node, and the value of any non-root node is less than or equal to its parent node value. The small root heap is reversed.

  2. The idea of heap sorting is simple: first, the N elements stored in L[1… N] are built into the initial heap. Due to the nature of the heap itself (take the large root heap as an example), the top element is the maximum. After the top element is output, the bottom element is usually sent to the top of the heap. At this time, the root node no longer meets the nature of the big top heap, and the pair is destroyed. The top element is adjusted downward to keep the nature of the big top heap, and then the top element is output. This is repeated until only one element is left in the heap.

  3. To build the initial heap: First adjust the bottom right subtree of the complete binary tree to make it into a heap (if the child of this node is older than it, the eldest child is switched with the parent node), then filter the subtree root of each node ([N/2]-1~1) in order to see whether the node is greater than the value of its left and right children, if not, swap. Swapping may destroy the next level of the heap, so continue building the next level of the heap using the above method until the subtree rooted in this node forms the heap. Build the heap again and again using the above method of adjusting the heap up to the root node.

Algorithm implementation

Void Build_Max_Heap(ElemType A[],int len) {// Build the large root heap int I; for (int i = len / 2; i > 0; I --) // From I =[n/2]~1, adjust HeadAdjust(A, I,len); } void HeadAdjust(ElemType A[],int k,int len) {void HeadAdjust(ElemType A[],int k,int len); A[0] = A[k]; //A[0] for (I = 2 * k; i <= len; I * = 2) / / filter down the key large child node {the if (I < len && A [I] < A [I + 1]) {i++; } if (A[0] >= A[I]) break; Else {A[k] = A[I]; // set A[I] to k = I; }} A[k] = A[0];}} A[k] = A[0]; } void Heap_Sort(ElemType A[],int len) {void Heap_Sort(ElemType A[],int len) { Build_Max_Heap(A,len); For (I = len; i > 1; I ++) //n-1 swap and heap process {swap(A[I],A[1]); // Print the top element (swap with the bottom element) HeadAdjust(A,1,i-1); // Resize the remaining i-1 elements into a heap}}Copy the code