排序——选择排序

前面的文章介绍了排序的概念，插入排序和交换排序，大家可以通过下面的链接再去学习：

排序的概念及插入排序           

交换排序

这篇文章则介绍一下选择排序的相关内容。

一，简单选择排序

基本思想：

        每一趟在后面 n-i +1个中选出关键码最小的对象, 作为有序序列的第 i 个记录。

用代码实现排序过程：

void SelectSort(SqList &K){ for (i=1; i<L.length; ++i){ //在L.r[i..L.length] 中选择key最小的记录k=i;     for( j=i+1;j<=L.length ; j++)if ( L.r[j].key <L.r[k].key) k=j; if(k!=i)L.r[i]←→L.r[k];            }  
}

 算法分析：

 移动次数

---

 二，树形选择排序

改进：简单选择排序没有利用上次选择的结果，是造成速度慢的重要原因。如果，能够加以改进，将会提高排序的速度。

例：

选出次最小者，应利用上次比较的结果。从被 13 打败的结点 27、76、38 中加以确定。

算法步骤：

        将所有记录的关键字作为叶子节点构建成完全二叉树；非叶子节点的关键字设置为其孩子节点中较小的那个；经过层层比较，最终在根节点得到最小关键字；之后修改叶子节点中的最小值为正无穷，重复上述过程找出次小值，直至完成排序。

性能分析： 

• 时间复杂度：树形选择排序的时间复杂度为O(NlogN)，因为除了第一次选择最小关键字需要进行n-1次比较外，每选择一个次小关键字仅需进行log2n次比较。
• 空间复杂度：由于需要构建存储元素的二叉树，因此空间复杂度为O(N)。
• 稳定性：树形选择排序的稳定性依赖于具体实现方式，在某些情况下可能不稳定。
• 优势：相比简单选择排序，树形选择排序减少了不必要的比较次数，提高了排序效率。
• 劣势：树形选择排序需要额外的存储空间来构建二叉树，并且与“最大值”的比较多余

以下是一段完整的c语言树形选择排序代码： 

#include <stdio.h>
#include <stdlib.h>// 定义二叉树节点结构体
typedef struct Node {int data;struct Node *left, *right;
} Node;// 创建新节点
Node* newNode(int data) {Node* node = (Node*)malloc(sizeof(Node));node->data = data;node->left = NULL;node->right = NULL;return node;
}// 插入节点到二叉树中
Node* insert(Node* root, int data) {if (root == NULL) {return newNode(data);}if (data < root->data) {root->left = insert(root->left, data);} else if (data > root->data) {root->right = insert(root->right, data);}return root;
}// 查找最小值节点
Node* findMin(Node* root) {while (root->left != NULL) {root = root->left;}return root;
}// 删除节点
Node* deleteNode(Node* root, int data) {if (root == NULL) {return root;}if (data < root->data) {root->left = deleteNode(root->left, data);} else if (data > root->data) {root->right = deleteNode(root->right, data);} else {if (root->left == NULL) {Node* temp = root->right;free(root);return temp;} else if (root->right == NULL) {Node* temp = root->left;free(root);return temp;}Node* temp = findMin(root->right);root->data = temp->data;root->right = deleteNode(root->right, temp->data);}return root;
}// 打印二叉树（中序遍历）
void inorder(Node* root) {if (root != NULL) {inorder(root->left);printf("%d ", root->data);inorder(root->right);}
}// 树形选择排序函数
void treeSelectionSort(int arr[], int n) {Node* root = NULL;for (int i = 0; i < n; i++) {root = insert(root, arr[i]);}for (int i = 0; i < n; i++) {Node* minNode = findMin(root);arr[i] = minNode->data;root = deleteNode(root, minNode->data);}
}int main() {int arr[] = {64, 34, 25, 12, 22, 11, 90};int n = sizeof(arr) / sizeof(arr[0]);treeSelectionSort(arr, n);printf("Sorted array: \n");for (int i = 0; i < n; i++) {printf("%d ", arr[i]);}printf("\n");return 0;
}

---

三，堆排序 

 什么是堆？

 n个元素的序列{k1,k2,…,kn}，当且仅当满足下列关系时，成为堆：

如果将序列看成一个完全二叉树，非终端结点的值均小于或大于左右子结点的值。

利用树的结构特征来描述堆，所以树只是作为堆的描述工具，堆实际是存放在线形空间中的。

 堆又分为大根堆和小根堆：

 下面的两个树就不满足堆的性质

例：判定(80,75,40,62,73,35,28,50,38,25,47,15)是否为堆

 如何将无序序列建成堆？

不超过 n/2的最大正整数，得到序号为3，以3号位置为根结点的树不满足大根堆的性质

这里我们将8和12换位置，12>8,12>10,经过调整这棵子树满足大根堆的性质

 同样调整左边的子树，交换60和70

最后将整个子树的根节点与其左右孩子比较，在满足大根堆性质的前提下交换

 至此就完成了将无序序列建成堆的过程。

堆的调整

如何在输出堆顶元素后调整，使之成为新堆？

        输出堆顶元素后，以堆中最后一个元素替代之

        将根结点与左、右子树根结点比较，并与大者交换

这里就不再给出图示过程，与上面堆的构建类似，也是不断递归比较，调整的过程。

下面是完整的c语言堆排序的代码：

#include <stdio.h>
#include <stdlib.h>// 交换两个整数的值
void swap(int *a, int *b) {int temp = *a;*a = *b;*b = temp;
}// 调整堆，使其满足最大堆的性质
void heapify(int arr[], int n, int i) {int largest = i; // 初始化最大值为当前节点int left = 2 * i + 1; // 左子节点的索引int right = 2 * i + 2; // 右子节点的索引// 如果左子节点存在且大于当前最大值，更新最大值索引if (left < n && arr[left] > arr[largest])largest = left;// 如果右子节点存在且大于当前最大值，更新最大值索引if (right < n && arr[right] > arr[largest])largest = right;// 如果最大值索引不是当前节点，交换并继续调整堆if (largest != i) {swap(&arr[i], &arr[largest]);heapify(arr, n, largest);}
}// 堆排序算法
void heapSort(int arr[], int n) {// 构建最大堆for (int i = n / 2 - 1; i >= 0; i--)heapify(arr, n, i);// 逐个提取最大元素并调整堆for (int i = n - 1; i >= 0; i--) {swap(&arr[0], &arr[i]); // 将当前最大元素放到数组末尾heapify(arr, i, 0); // 调整剩余部分为最大堆}
}int main() {int arr[] = {12, 11, 13, 5, 6, 7};int n = sizeof(arr) / sizeof(arr[0]);heapSort(arr, n); // 对数组进行堆排序printf("Sorted array is: ");for (int i = 0; i < n; ++i)printf("%d ", arr[i]); // 输出排序后的数组printf(" ");return 0;
}

堆排序的算法分析：

时间效率：O(nlog2n)

空间效率：O（1）

稳 定 性：不稳定

适用于n 较大的情况。

---

到此选择排序就结束了， 如果文章对你有用的话请点个赞支持一下吧！

下篇文章将更新归并排序的内容。