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

排序算法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]max){ max = arr[j]; index_max = j; } } // 判断最大值的位置是否为所选位置 if(index_max != size-i-1){ arr[index_max] = arr[size-i-1]; //index_min == size-i-1 arr[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; } }}

堆排序：

        利用大根堆或者小根堆进行序列的升序或者降序排序，先建立堆，时间复杂度为堆的排序以及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+1arr[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 次）

多（每次堆调整都有交换）

好了，本期的内容分享就到这里结束了，谢谢大家的点赞和收藏！