淘客网站如何做推广,网站开发技术方案实验报告,东莞网站建设网站建设多少钱,百度普通收录堆排序
思想#xff1a;假设数组放入完全二叉树中#xff0c;
1、初始化堆#xff1a;调节父结点与子结点的大小。让所有的子结点都小于父结点。
2、将完全二叉树中的叶子结点和根结点进行互换后#xff0c;继续调整堆。直至结束
#includeiostream
#include假设数组放入完全二叉树中
1、初始化堆调节父结点与子结点的大小。让所有的子结点都小于父结点。
2、将完全二叉树中的叶子结点和根结点进行互换后继续调整堆。直至结束
#includeiostream
#includestdio.h
#includestdlib.h
#includerandom
#includetime.h
#includesys/timeb.h
using namespace std;
#define MAX 9long getSystemTime()
{struct timeb tb;ftime(tb);return tb.time * 1000 tb.millitm; //毫秒
}void printArr(int arr[], int length)
{for (int i 0; i length; i){printf(%d , arr[i]);}printf(\n);
}
void swapElementme(int* a, int* b)
{int temp *a;*a *b;*b temp;
}//堆排序
void heapSortme(int arr[], int length)
{int mid length / 2 - 1;int lchild mid * 2 1;int rchild mid * 2 2;int max mid;//初始化堆for (int i mid; i length; i--) {if (arr[i] arr[lchild]){max lchild;}if (arr[mid] arr[rchild]){max rchild;}if (max ! mid){swapElementme(arr[mid], arr[max]);}}for (int i 0; i length; i){swapElementme(arr[0], arr[length - 1]);heapSortme(arr, length);}
}void swapElement(int arr[], int a, int b)
{int temp arr[a];arr[a] arr[b];arr[b] temp;
}
/*param arr 待调整的数组param index 待调整的结点的下标param length 数组长度
*/
void heapAdjust(int arr[],int index, int length)
{//保存当前结点的下标int max index;//保存右孩子的数组下标int lchild index * 2 1;//保存左孩子的数组下标int rchild index * 2 2;if (lchildlength arr[lchild]arr[max]){max lchild;}if (rchildlength arr[rchild]arr[max]){max rchild;}if (max ! index){//交换两个结点swapElement(arr, max, index);heapAdjust(arr, max, length);}}
void heapSort(int arr[], int length)
{//初始化堆for (int i length/2-1; i 0; i--){heapAdjust(arr, i, length);}//交换堆顶元素和最后一个元素for (int i length-1; i 0; i--){swapElement(arr, 0,i);heapAdjust(arr, 0, i);}
}int main()
{int arr[] { 4,2,8,0,5,7,1,3,9};long t_start getSystemTime();printArr(arr,MAX);heapSort(arr,MAX);printArr(arr, MAX);long t_end getSystemTime();printf(堆排序%d个元素所需时间%1d\n, MAX, t_end - t_start);system(pause);return 0;
}
运行结果
