C language to heap sort an algorithm idea and implementation code

Simple description of algorithm idea:

Heap sort is a kind of tree selection sort, which is an effective improvement on direct selection sort.

The heap is defined as follows: a sequence of n elements (h1,h2,...) ,hn) if and only if satisfying (hi > = h2i, hi > =2i+1 or (hi) < = h2i, hi < = 2 + 1) I (I = 1, 2,... N over 2) is called the heap. Only heaps that satisfy the former condition are discussed here.

As you can see from the definition of the heap, the top element (that is, the first element) must be the largest term. A complete binary tree can visually represent the structure of the heap. The top of the heap is the root, and the rest is the left subtree and the right subtree.

Initially, think of the sequence of Numbers to be sorted as a binary tree stored sequentially, and adjust their storage order to make it a heap, where the number of root nodes of the heap is the largest. The root node is then swapped with the last node of the heap. And then I'm going to rearrange the number of n minus 1 to make it a heap. And so on, until there are only two nodes in the heap, and exchange them, and finally an ordered sequence of n nodes.

From the description of the algorithm, heap sort requires two processes: one is to establish the heap, and the other is to exchange the position between the top of the heap and the last element of the heap. So heap sort consists of two functions. One is the percolation function of the heap, the other is to repeatedly call the percolation function to achieve the sorting function.

Heap sort is unstable. O(nlog2n).

void sift(int *x, int n, int s){
  int t, k, j;
  t = *(x+s);
  k = s;
  j = 2*k + 1;
  
  while (j{
    if (j< *(x+j+1)) && *(x+j) /> {  //Determine if the heap conditions are met: if so, proceed to the next round of comparison, otherwise adjust.
      j++;
    }
    if (t<*(x+j)){
      *(x+k) = *(x+j);
      k = j;
      j = 2*k + 1;
    }else{
      break;
    }
  }
  *(x+k) = t;
}

void heap_sort(int *x, int n){
  int i, k, t;
  int *p;
  for (i=n/2-1; i>=0; i--){
    sift(x,n,i);
  }
  for (k=n-1; k>=1; k--){
    t = *(x+0);
    *(x+0) = *(x+k);
    *(x+k) = t;
    sift(x,k,0);
  }
}

void main(){
  #define MAX 4
  int *p, i, a[MAX];

  p = a;
  printf("Input %d number for sorting :n",MAX);
  for (i=0; i<MAX; i++){
    scanf("%d",p++);
  }
  printf("n");
 
  p = a;
  select_sort(p,MAX);
  for (p=a, i=0; i++){
    printf("%d ",*p++);
  }
  printf("n");
  system("pause");
}