看数据结构写代码(63) 堆排序
// HeapSort.cpp : 定义控制台应用程序的入口点。 // #include "stdafx.h" #include <cstdlib> #define LIST_MAX_SIZE 100 //顺序表 struct sqList{ int base[LIST_MAX_SIZE]; int len; }; typedef sqList Heap;//顺序表作为堆排序的基本类型 //初始化顺序表 void initHeap(Heap * list,int * array,int len){ //0号单元不存储. for (int i = 0; i < len; i++){ list->base[i+1] = array[i]; } list->len = len; } //向下筛选(最小堆) void siftDown(Heap *h,int i){ int len = h->len; int minIndex = i; bool finished = false;//完成标志 for (int j = 2 * i; j <= len && finished == false; j= 2 * i){ if (h->base[j] < h->base[i]){ minIndex = j; } if (j + 1 <= len){ if (h->base[j+1] < h->base[minIndex]){ minIndex = j + 1; } } if (minIndex != i){ int temp = h->base[minIndex]; h->base[minIndex] = h->base[i]; h->base[i] = temp; i = minIndex; } else{ finished = true;//完成筛选。 } } } //创建堆 void createHeap(Heap * h){ int len = h->len; for (int i = len / 2; i >= 1; i--){ siftDown(h,i); } printf("---------------创建堆---------------\n"); for (int i = 1; i <= h->len; i++){ printf("%d\t",h->base[i]); } printf("\n"); } void heapSort(Heap h){ printf("---------------堆排序---------------\n"); for (int i = h.len; i >= 1; i--){ printf("%d\t",h.base[1]); h.base[1] = h.base[i]; h.len--; siftDown(&h,1); } } int _tmain(int argc, _TCHAR* argv[]) { int testArray[10] = {77,66,44,33,11,22,55,99,88,100}; Heap h; initHeap(&h,testArray,10); createHeap(&h); heapSort(h); return 0; }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。