C language implements eight sorts (3)

3. Selection sort

3.1 Selection sort

What is selective sorting ？

Selection sort （Selection sort） It is a simple and intuitive sorting algorithm .

principle ： Select the smallest data element from the data elements to be sorted for the first time （ Or maximum ） An element of , Store at the beginning of the sequence , And then find the smallest of the remaining unsorted elements （ Big ） Elements , Then put it at the end of the sorted sequence . And so on , Until the number of all data elements to be sorted is zero . Selective sorting is an unstable sorting method .

The code implementation is as follows ：

void swap(int*a,int i,int j){ 
	int temp=a[i];
	a[i]=a[j];
	a[j]=temp;
}
void SelectSort(int*a,int length){
	int i,j;
	for(i=0;i<length-1;i++){ // perform n-1 This cycle is because n-1 Sorting has been completed after times , There is no need for the last sort  
		int k=i;
		for(j=i+1;j<length;j++){  // Compare from the next position 
			if(a[k]>a[j]){  // The subscript of the required value is recorded here 
				k=j;
			}
		}
		if(k!=i){//  If k==i Then it means that the current number is what I ask , There is no need to exchange  
			swap(a,k,i);
		}
	}
}

3.2  Heap sort

Our blog also talked about piles before , Those who are not familiar with the heap can see our previous blog

The basic introduction of heap

We can use the special properties of heap to realize sorting

The code implementation is as follows ：

void swap(int*a,int i,int j){
	int temp=a[i];
	a[i]=a[j];
	a[j]=temp;
}
void HeapAdjust(int*a,int i,int length){
	
	int rc=a[i];
	for(int j=2*i+1;j<length;j=j*2+1){
          if((j<length-1)&&a[j]<a[j+1]){ //j<length-1 Guarantee a[j+1] Do not cross the line  
          	j++;
		  }		
		  if(a[j]<rc){
		  	break;
		  }
		  // If the root node is smaller than the child node, exchange  
		  a[i]=a[j];
		  a[j]=rc;
		  i=j;
	}
}
void HeapSort(int*a,int length){
	int last=length-1;// The last element subscript 
	int parent=(last-1)/2;// Heap building from the last parent node , Because every leaf node is a heap 
	for(int i=parent;i>=0;i--){
		HeapAdjust(a,i,length); 
	} 
	for(int i=length-1;i>0;i--){
		swap(a,0,i); // Swap the first and last  
		HeapAdjust(a,0,i); // Readjust the heap  
	}
	
} 

We only need to exchange the first and last to complete the sorting .