Improved heapsort algorithm of selection sort

The first thing to understand about the heap is that either none of the nodes is greater than the child node data or none is less than the child node data

The core idea of heap sort is to satisfy all nodes satisfy the above two points, how to do it, see the following

Heap sort steps:

1. First, a large top pile or a small top pile should be built. In the process of construction, the position of nodes should be adjusted. Why not the last one or something? For completeness and non-necessity, you simply start with the mother node of the last one (the heap below has a sequential structure by default, starting at index 0, so some binary tree features are available) and work your way up to the node with index node 0. When the adjustment is completed, it becomes a heap, but the data here is not sorted properly, so the next step adjusts the order.

2. Start with the last data, exchange with the first data, and then adjust the first data according to the meaning of the heap. Why choose the last data first? Because, by default, the last one is either larger or smaller, it satisfies the adjustment. At this point, consider all the current data minus the last one, because this is the largest or the smallest, don't worry about it. Sorting is complete until there is no data for the adjustment.

Specific legend is no longer identified, have this hobby can refer to other books or the introduction of the Internet, see the following heap sort code:

int HeapSort(MergeType* L)
{
 int i = 0;
 if (!L->elem)
 {
  return -1;
 }
 //Create a heap
 for (int i = L->len/2-1; i >= 0; i--)
 {
  HeapAdjust(L, i, L->len-1);
 }
 //Heap sort
 for (i = L->len-1; i >= 0; i-- )
 {
  swap(L->elem[i], L->elem[0]);
  HeapAdjust(L, 0, i-1);
 }
 return 0; 
}

Note:
1) due to the relationship between parent and child nodes, the first data index of for loop is actually L,len-1, but the relationship between parent node (I) and current node (p) : p = 2i+1 or 2i+2; If the first index of the node where the data is stored is not 0 but 1, where p=2i or p=2i+1, see the proof in the book, so the current parent node: I = (p-1)/2 = (l.en-1-1)/2 = l.en-2-1

2) since the data is adjusted again from the last data, data swap needs to be exchanged, and the current vertex data is the first data heap adjustment, but at this time, the object of adjustment is only (0~ I) these data, the others have been sorted, so there is no need to adjust

Now take a look at the adjustment code, as follows:

int HeapAdjust(MergeType* L, int nPos, int nEnd)
{
 for (int i = nPos*2+1; i < nEnd ; i = 2*i+1)
 {
  if (L->elem[i] <= L->elem[i+1])
  {
   i++;
  }
  if (L->elem[nPos] >= L->elem[i])
  {
   break;
  }
  swap(L->elem[nPos], L->elem[i]);
  nPos = i;
 }
 return 0;
}

This is a direct exchange of data at one level, which is not necessary because the data is placed last, so you can also use the following code to reduce the number of copies

int HeapAdjustEx(MergeType* L, int nPos, int nEnd)
{
 int nTempkey = L->elem[nPos];
 for (int i = nPos*2+1; i < nEnd ; i = 2*i+1)
 {
  if (L->elem[i] <= L->elem[i+1])//Pick the oldest child
  {
   i++;
  }
  if (nTempkey >= L->elem[i]) //Exits if the current node is greater than the largest child
  {
   break;
  }
  L->elem[nPos] = L->elem[i]; //Otherwise, data is exchanged
  nPos = i;
 }
 L->elem[nPos] = nTempkey;
 return 0;
}

Here you can reduce more copy operations, also known as the number of moving operations; Here, the starting node of for loop should be p=2i+1 according to the above inference, so the first node should be 2*nPos+1, corresponding to the child of the current node to be compared, the right child is 2*nPos+2, that is, the left child +1, please see the comments for others.
Time complexity: O (nlogn), the analysis process is brief