什么是树形选择排序算法?详述树形选择排序算法的原理?用C语言实...

杨数Tos

共 2959字,需浏览 6分钟

 · 2023-05-26

大家好,我是贤弟!
一、什么是树形选择排序?     树形选择排序(Tree Selection Sort)是一种基于堆的排序算法,是对选择排序的改进,由Donald Knuth于1971年提出。     它利用堆数据结构来实现选择排序,将时间复杂度从O(n^2)降低到O(nlogn),是一种高效的排序算法。
二、树形选择排序的原理     树形选择排序的原理是,利用堆数据结构对元素进行排序。首先将待排序的元素构建成一个完全二叉树,并将每个节点的值赋给其对应的元素。     然后找出所有叶子节点中最小的元素,将其和父节点交换;再找出最小的元素,将其和父节点交换;再找出最小的元素,将其和父节点交换…以此类推,直到找到最小的元素交换到了根节点,整个序列就已经有序排列。
三、代码示例     C语言实现树形选择排序的代码如下:
      
        
          #include <stdio.h>
        
      
      
        void swap(int *p1, int *p2) {
      
      
            int temp = *p1;
      
      
            *p1 = *p2;
      
      
            *p2 = temp;
      
      
        }
      
      
        
          

void siftDown(int arr[], int start, int end) { int i = start; // 当前节点的下标 int j = 2 * i + 1; // 左孩子的下标 int temp = arr[i]; // 当前节点的值 while (j <= end) { // 如果当前节点有子节点 if (j < end && arr[j] > arr[j + 1]) { // 如果有右孩子,并且右孩子的值比左孩子小 j++; // 则选择右孩子作为下一次比较的节点 } if (temp <= arr[j]) break; // 如果当前节点的值小于等于孩子节点,则退出 arr[i] = arr[j]; // 将孩子节点的值赋给父节点 i = j; // 更新当前节点 j = 2 * i + 1; // 计算左孩子的下标 } arr[i] = temp; // 将原来的节点值赋给最后停留在的位置 }

void treeSelectionSort(int arr[], int n) { // 建立初始堆 for (int i = n / 2 - 1; i >= 0; i--) { siftDown(arr, i, n - 1); } // 取出最小值 for (int i = n - 1; i > 0; i--) { swap(&arr[0], &arr[i]); siftDown(arr, 0, i - 1); } }

int main() { int arr[] = {6, 5, 3, 1, 8, 7, 2, 4}; int n = sizeof(arr) / sizeof(int);

treeSelectionSort(arr, n);

for (int i = 0; i < n; i++) { printf("%d ", arr[i]); }

return 0; }

输出结果:
    1 2 3 4 5 6 7 8



浏览 53
点赞
评论
收藏
分享

手机扫一扫分享

举报
评论
图片
表情
推荐
点赞
评论
收藏
分享

手机扫一扫分享

举报