版权声明:本文为作者原创文章,可以随意转载,但必须在明确位置表明出处!!!
基数排序
- 找出待排序中的最大数确定需要排多少趟。
- 创建10个“桶”来装每个关键字的元素
- 将每隔待排元素按照个位依次放入对应的“桶”中。然后十位,百位,直到最大数的最高位排完为止。
时间复杂度:
最坏时间复杂度为O(d(r + n)),最好时间复杂度为O(d(n + rd)),平均复杂度为O(d(r + n ))。r表示关键字的基数,d表示长度,n表示关键字的个数
稳定性:
基数排序是稳定排序
算法实现
|
|
堆排序
算法的基本思想:
堆排序的基本思想是先将一个无序的集合整理为一个大根堆或小根堆的完全二叉树,然后交换根节点和最后一个叶子节点元素,然后重新整理n-1个节点为大根堆或小根堆,重复此操作直到n为0结束。
算法原理:
- 建堆,从nLength/2开是调整,一直到第一个节点。
- 调整堆,比较父节点和叶子节点的大小,若都小于叶子节点的大小则此结点无需调整,若不是则交换与该节点的左右叶子节点较小的一个元素
- 堆排序,交换根节点和nLength节点,按照上面步骤调整nLength - 1个节点,nLength – 直到nLength为0为止。
时间复杂度:
平均时间复杂度O(nlogn)
稳定性:
堆排序算法是不稳定的排序算法
为了更好的演示堆排序的过程,下面给出图像演示
原始堆
建堆过程
堆排序第一趟结果
堆排序第二趟结果
堆排序第三趟结果
堆排序第四趟结果
堆排序第五趟结果
堆排序第六趟结果
堆排序第七趟结果
堆排序第八趟结果
堆排序第九趟结果
算法实现:
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748template<class T>void Algorithm<T>::heapSort(T *array, int nLength, int (*fCompare)(const T*, const T*)){for(int nLoop = (nLength - 1) / 2 ; nLoop >= 0; nLoop --){//只有左子树并小于父节点int lChild = nLoop * 2 + 1;//左节点int rChild = lChild + 1;//右节点if(lChild == nLength - 1 && fCompare(&array[lChild], &array[nLoop]) <= 0){swap(array[lChild], array[nLoop]);}//从子树开始整理adjustHeap(array, nLength - 1, nLoop, fCompare);}while(nLength > 0){swap(array[nLength - 1], array[0]);nLength --;adjustHeap(array, nLength, 0, fCompare);}}template<class T>void Algorithm<T>::adjustHeap(T *array, int nLength, T element, int (*fCompare)(const T*, const T*)){int lChild = element * 2 + 1;//左节点int rChild = lChild + 1;//右节点while(rChild < nLength){//如果父节点小于它的左右孩子节点则改节点不需要整理if(fCompare(&array[element], &array[lChild]) < 0 && fCompare(&array[element], &array[rChild]) < 0) return;//比较左右子树确定哪个子树最小if(fCompare(&array[lChild], &array[rChild]) <= 0){swap(array[element], array[lChild]);element = lChild;}else{swap(array[element], array[rChild]);element = rChild;}lChild = element * 2 + 1;rChild = lChild + 1;}}
项目文件地址:https://github.com/Gavinxyj/Algorithm
推荐我的微信公众号:爱做饭的老谢
上一篇:FTP网络协议C++实现)
下一篇:设计模式(简单工厂模型)