排序——选择排序

大家好，欢迎来到IT知识分享网。

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

排序的概念及插入排序           

交换排序

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

一，简单选择排序

基本思想：

        每一趟在后面 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 较大的情况。

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

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