201702(10.20.23.18)

堆排序

void Swap(int sortArr[],int i,int j){
	sortArr[i] = sortArr[i] xor sortArr[j];
	sortArr[j] = sortArr[i] xor sortArr[j];
	sortArr[i] = sortArr[i] xor sortArr[j];
}
int main()
{
	/* 第二题,堆排序算法 */
	int n = 0;
	//输入数据规模
	cin >> n;
	int elemLenth = n+1;
	int sortArr[elemLenth] = {0};
	// srand((unsigned)time(NULL)); 
	for(int i=1;i<=n;++i){
		//依次输入各个元素　
		sortArr[i] = (rand() % (2000));
	}
	//找到第一个非叶结点,开始向上调整
	int gap = 0;
	int time = elemLenth - 1;
	while(time>0){
		gap = time/2;	
		while(gap > 0){
			int lc = gap*2;
			int rc = gap*2 + 1;
			if(rc>elemLenth){
				if(sortArr[lc]<sortArr[gap]){
					Swap(sortArr,lc,gap);
				}
			}else{
				if(sortArr[lc] < sortArr[gap] && sortArr[lc] < sortArr[rc]){
					Swap(sortArr,lc,gap);
				}else if(sortArr[rc] < sortArr[gap] && sortArr[rc] < sortArr[lc]){
					Swap(sortArr,rc,gap);
				}
			}
			gap--;
		}
		printf("%d\n", sortArr[1]);
		Swap(sortArr,1,time);
		//调整完成,输出第一个元素,再将第一个元素和堆的最后一个元素交换，堆缩容
		time--;
	}

测试了一下,规模达到10000时,会乱调,和我之前一篇用java写的代码基本一样啊,为什么会乱？

import java.util.Scanner;
import java.lang.Math;

public class heapsort{
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		System.out.println("待排序的数字数量:");
		int n = in.nextInt();
		int heap[] = new int[n+1];//堆数组
		System.out.println("请输入待排序的数字:");
		//创建堆
		for(int i = 1;i<=n;i++) {
			heap[i] = (int)(Math.random()*1000);
	  	}
		int len = heap.length-1;
		long begin = System.nanoTime();
		alterheap(heap, len);//算法入口
		long end = System.nanoTime();
		System.out.println("time"+(end-begin));//计算排序时间
	}
	
	//调整堆
	static void alterheap(int[] heap,int l) {
		int len = l;
		while(len > 0) {
			int gap = len >> 1;
			//向上调整
			for(int i = gap;i>=1;i--) {
				if((i<<1)+1 > len)//表示只有左孩子
				{
					if(heap[i]>heap[i<<1]) {
						swap(i,i<<1,heap);
					}
				}else {
					//左右子孩子都存在，选择其中最小的一个进行交换
					boolean isLeft = heap[i<<1]<heap[(i<<1)+1]?true:false;
					if(isLeft && heap[i] > heap[i<<1]) {
						swap(i,i<<1,heap);
					}
					if(!isLeft && heap[i] > heap[(i<<1) +1]) {
						swap(i,(i<<1)+1,heap);
					}
				}
			}
			
			//调整完成，输出顶部元素
			System.out.println(heap[1]);
			//将堆顶元素和堆里最后一个元素交换，堆缩容
			swap(1,len,heap);
			len--;
		}
	}
	
	//交换元素
	static void swap(int a,int b,int[] heap) {
		heap[a] = heap[a]^heap[b];
		heap[b] = heap[a]^heap[b];
		heap[a] = heap[a]^heap[b];
	}
}