苗火 Nicholas

[Data structures]Heap sort

2019-5-21 萧 写技术

#include <stdio.h>
#include <stdlib.h>

void heapAdjust(int *queue, int len, int start)
{
	int p = start;
	int left = (p+1)*2 - 1;
	int right = (p+1)*2;
	int min = 0;
	int tmp;
	while( left <= len-1 ){
		if(right <= len-1){
			if(queue[left] < queue[right]){
				min = left;	
			}else{
				min = right;
			}
		}else{
			min = left;
		}
		if(queue[min] < queue[p]){
			tmp = queue[p];
			queue[p] = queue[min];
			queue[min] = tmp;	
		}

		p = min;
		left = (p+1)*2 - 1;
		right = (p+1)*2;
	}	
}

void heapSort(int *seq, int len)
{
	int i,j;
	int queue[100];
	for(i=0; i<len; i++){
		queue[i] = seq[i];
	}

	for( i=len/2-1; i>=0; i--){
		heapAdjust(queue, len, i);
	}

	j = 0;
	for( i=len-1; i>=0; i--){
		seq[j++] = queue[0];
		queue[0] = queue[i];
		heapAdjust(queue, i+1, 0);
	}
}
		
void main()
{
	int ancient[] = {49,38,65,97,76,13,27,49};
	int seq[] = {49,38,65,97,76,13,27,49};
	int n = sizeof(seq)/sizeof(int);
	int i;

	printf("Simple selection sort: \n");
	printf("Seq:\n");
	for (i=0; i<n; i++) {
		seq[i] = ancient[i];
		printf(" %2d", seq[i]);
	}	
	printf("\n");
	heapSort(seq, n);
	for (i=0; i<n; i++) {
		printf(" %2d", seq[i]);
	}	
	printf("\n");

}

标签: Data Structures data_structures