Sort a K sorted array

Question:
given an array of n unsorted integers and each number is at most k positions away from its final sorted position, give an e-cient sorting algorithm. For example, let us consider k is 2, an element at index 7 in the sorted array, can be at indexes 5, 6, 7, 8, 9 in the given array.
분석:
순 서 를 배열 한 후의 0 번 째 요 소 는 원래 배열 의 0 ~ k 중의 요소 (그리고 최소 요소) 일 수 있 습 니 다. 첫 번 째 요 소 는 0 ~ k + 1 중의 두 번 째 작은 요소 로 k + 1 개의 요 소 를 가 진 작은 지붕 더 미 를 사용 할 수 있 습 니 다.처음에 0 ~ k 요 소 를 사용 하여 작은 지붕 더 미 를 만 들 었 습 니 다. 지붕 요 소 는 0 번 위치 에 있 는 요소 입 니 다. 그 다음 에 배열 의 k + 1 요 소 를 더미 에 넣 고 조정 한 후에 지붕 요 소 는 1 번 위치 에 있 는 요소 입 니 다.
시간 복잡 도:
쌓 아 올 리 는 시간 복잡 도 = > (아래 증명)
n 개의 요 소 를 가 진 완전 이 진 트 리, 나무의 높이 h = log2n + 1 (n = 2 ^ h - 1), 아래 에서 위로 쌓 을 때 맨 아래 비 엽 노드 (h - 1 층), 모두 2 ^ (h - 2) 개의 잎 노드 가 있 습 니 다. 이 층 에 소요 되 는 시간 은 2 ^ (h - 2), i 층 (i = 1, 2,... h - 1) 에 소요 되 는 시간 은 2 ^ (i - 1) * (h - i) 입 니 다. 총 소요 시간:
  S =                 2^(h-2)*1+2^(h-3)*2+...+2^1*(h-2)+2^0*(h-1)
2S = 2^(h-1)*1+2^(h-2)*2+2^(h-3)*3+...+2^1*(h-1)
S = 2S-S=2^(h-1)+2^(h-2)+2(h-3)+...+2-(h-1)=2^h-h+1=n-logn+2
그래서 쌓 는 시간의 복잡 도 는 O (n) 이다.
쌓 인 시간 복잡 도 조정: 한 번 에 조정 하 는 시간 복잡 도 O (h) = O (logn)
= = > 이 정렬 방법의 시간 복잡 도 O (k) + O (n - k) logk) = O (nlogk)

//   root         
static void MinHeapify(int* minHeap, int len, int root){
	if (rootminHeap[lchild])
				minIndex = lchild;
			if (rchildminHeap[rchild])
				minIndex = rchild;
			if (minIndex == root)
				break;
			minHeap[minIndex] ^= minHeap[root];
			minHeap[root] ^= minHeap[minIndex];
			minHeap[minIndex] ^= minHeap[root];
			root = minIndex;
			lchild = 2*root+1;
		}
	}
}
static void CreateMinHeap(int* minHeap, int len){
	if (len<=1)
		return;
	int parent = (len-2)/2;	//        
	while (parent>=0){
		MinHeapify(minHeap, len, parent);
		parent--;
	}
}
void SortKSortedArray(int*pData, int len, int k){
	if (len<=0)
		return;
	if (k+1 > len)
		k = len-1;
	int minHeapLen = k+1;
	int* minHeap = new int[minHeapLen];
	memcpy(minHeap, pData, minHeapLen*sizeof(int));
	CreateMinHeap(minHeap, minHeapLen);
	for (int i=0; i1) {//           （       k   ）
			minHeap[0] = minHeap[minHeapLen-1];
			minHeapLen--;
		}
		MinHeapify(minHeap, minHeapLen, 0);
	}
	delete[] minHeap;
}