当前位置：首页 > news >正文

数据结构自学Day12-- 排序算法2

news 2025/7/23 9:43:12

排序算法2

之前我们已经了解过简单的冒泡排序算法，以及插入排序，以及插入排序的优化（希尔排序）相关内容可以参考：排序算法1。

本期内容我们将着重介绍：选择排序的思想

选择排序：

选择排序（Selection Sort） 是一种简单直观的排序算法，其基本思想是：

每一轮从待排序元素中选出最小（或最大）元素，放到已排序序列的末尾（或开头），直到全部有序。

思维导图：

代码实现：

void Select_Sort(int* arr,int size){assert(arr);int min = 0;int index = 0;for(int i =0;i<size;i++){min = arr[i];for(int j = i;j<size;j++){if(arr[j]<min){min = arr[j];index = j;}}arr[index] = arr[0];arr[0] = min;}}

选择排序的优化：

双向选择-->同时选择最大值和最小值进行排序。

思维导图：

代码实现：

void Select_Sort(int* arr,int size){assert(arr);int min = 0;int max = 0;int index_min =0; int index_max = 0;for(int i = 0;i<size/2;i++){min = arr[i];max = arr[size-i-1];index_min = i;index_max = size-i-1;for(int j= i;j<size-i;j++){if(arr[j]<min){min = arr[j];index_min = j;}if(arr[j]>max){max = arr[j];index_max = j;}}// 判断最大值的位置是否为所选位置if(index_max != size-i-1){arr[index_max] = arr[size-i-1]; //index_min == size-i-1arr[size-i-1] = max;//防止交换最大值时，把最小的值位置换走了if(index_min == size-i-1){index_min = index_max;}}if(index_min!=i){arr[index_min] = arr[i];arr[i] = min;}}
}

堆排序：

利用大根堆或者小根堆进行序列的升序或者降序排序，先建立堆，时间复杂度为 $O(NlogN)$ 堆的排序以及TopK元素问题.

阶段	说明
建堆	从 (n-2)/2 开始往前，对每个节点做 AdjustDown
排序	每次将堆顶（最大）与最后元素交换，再对前 n-1 元素做 AdjustDown

//向下调整
void AdjustDown(int* arr,int n,int root){assert(arr);int parent = root;int child = 2*parent+1;int tmp = 0;while (child<n){if(child+1<n && arr[child+1]>arr[child]){child++;}if(arr[child]>arr[parent]){tmp = arr[child];arr[child] = arr[parent];arr[parent] = tmp;parent = child;child = 2*parent+1;}else{break;}}return;
}//堆排序 --> 升序排大根堆，降序排小根堆
void Heap_sort(int* arr,int size){assert(arr);for(int i = (size-1-1)/2;i>=0;i--){AdjustDown(arr,size,i);}int end = size;while (end>1){int tmp = arr[0];arr[0] =arr[end-1];arr[end-1] = tmp;AdjustDown(arr,end-1,0);}}

堆排序 vs 选择排序对比总结

特性	选择排序	堆排序
时间复杂度	O(n²)	O(n log n)
空间复杂度	O(1)	O(1)
稳定性	不稳定	不稳定
实现难度	简单	略复杂
是否原地排序	是	是
适用场景	小数据量、教学演示	大数据量、工程实践
交换次数	较少（至多 n 次）	多（每次堆调整都有交换）