首页 > 代码库 > 堆排序

堆排序

堆排序


// 测试堆排序
 // @start:调整的起点
 // @end:调整的终点,在堆排序的过程中,不断地减小调整区间,end参数起作用
 void SiftDown(int arr[], int start, int end)
 {
	 int i = start;
	 int j = 2*i + 1; // j记录的是i结点的左孩子
	 int temp = arr[i];
	 while (j <= end)
	 {
		 // (j<end)很巧妙的判断i结点是否有右孩子
		 if (j < end && arr[j] < arr[j+1])
		 {
			 ++j; // 如果i结点存在右孩子,并且右孩子大于左孩子
		 } // 到目前为止,j指向的是i结点中较大的孩子结点
		 if (temp >= arr[j]) // 如果i结点大于等于孩子结点中较大的,则不需要再调整下去,直接跳出循环
		 {
			 break;
		 }else
		 {
			 arr[i] = arr[j]; // 否则做调整,把i和j整体下移一层
			 i = j;
			 j = 2*j +1;
		 }
	 }
	 arr[i] = temp; // 最后i所指向的位置,就是空缺出来的arr[0]该放的位置
 }

 void BuildHeap(int arr[], int n)
 {
	 // 因为数组是从0开始索引,所以堆的最后一个有孩子的结点位于(n-2)/2处
	 for (int i = (n-2)/2; i >= 0; --i)
	 {
		 SiftDown(arr, i, n-1); // 在建堆的过程中,调整的右边界始终是数组的最后一个索引值
	 }
 }

 void HeapSort(int arr[], int n)
 {
	 BuildHeap(arr, n);
	 int temp;
	 for (int i = n-1; i > 0; --i)  // 从数组的最后一个索引值开始,到索引为1(数组中的第二个元素)
	 {
		 temp = arr[0];  // 堆顶和i位置交换
		 arr[0] = arr[i];
		 arr[i] = temp;
		 // 在这个过程中的调整左边界始终为0,而右边界一直在缩小,因为右边界右面的都是排好序的
		 SiftDown(arr, 0, i-1);
	 }
 }