选择排序是一种简单直观的排序算法,属于比较类排序
,内部是通过比较元素大小,决定每个位置应该存储哪个元素。
常见的算法如下:
- 简单选择排序(
SelectionSort
) - 堆排序(
HeapSort
)
简单选择排序
简单选择排序(SelectionSort
)原理比较简单,如下:
- 在未排序序列中找到最小(大)元素,存放到排序序列的起始位置。
- 再从剩余未排序元素中继续寻找最小(大)元素,放到已排序序列的末尾。
- 以此类推,直到所有元素均排序完毕。
代码实现
// objc 版本
- (void)selectionSort:(int[] )arr withLength:(int )length {
//循环 length 次
for (int i=0; i<length-1; i++) {
//查找每个位置的合适的元素
int findIndex = i;//默认第i个,即待排序列表 第一个元素 是最小(大)的元素
//循环待排序列表,找到 最小(大)的元素
for (int j=i+1; j<length-1; j++) {
if (arr[j]<arr[findIndex]) {
//找到更小的元素
findIndex = j;
}
}
//交换最小的元素,交换位置
if (findIndex != i) {
int tmp = arr[i];
arr[i] = arr[findIndex];
arr[findIndex] = tmp;
}
}
}
算法分析
最好时间复杂度:O(n²)
。
最坏时间复杂度:O(n²)
。
平均时间复杂度:O(n²)
。
空间复杂度:O(1)
稳定性:稳定。
堆排序
堆排序(HeapSort
)是一种树形选择排序方法,利用大顶堆、小顶堆(完全二叉树Complete Binary Tree
)结构的顺序存储结构特性,每次从树中选择出最大节点。
基本流程如下:
- 将无需序列构建成一个堆(
heap
,即完全二叉树),顶据升序降序需求选择大顶堆或小顶堆。 - 将堆顶元素与末尾元素交换,将最大元素”沉”到数组末端,重新调整结构,使其满足大顶堆、小顶堆特性。
- 然后继续交换堆顶元素与当前末尾元素,反复执行调整+交换步骤,直到整个序列有序。
那什么是完全二叉树?
完全二叉树
完全二叉树:(Complete Binary Tree)
,若设二叉树的深度为h
,除第h
层外,其它各层 (1~h-1
) 的结点数都达到最大个数,第 h
层所有的结点都连续集中在最左边。
例如序列 array[0,...,n-1]
,生成的完全二叉树有下面几个特性。
1.针对任意节点i
,节点之间索引规则:
父节点:(i-1)/2 ,i != 0
左孩子:2*i+1
右孩子:2*i+2
2.节点顺序规则:
小顶堆:array[i] <= array[2*i + 1] 且 array[i] <= array[2*i + 2]
大顶堆:array[i] >= array[2*i + 1] 且 array[i] >= array[2*i + 2]
这里我们看一下完全二叉树的大顶堆
版本。
大小顶堆
大顶堆
即任意节点都要比两个子节点要大,升序
的堆排序中会用到。小顶堆
即任意节点都要比两个子节点要大,降序
的堆排序中会用到。
例如一个序列:
int arr[] = {9,4,5,6,8,1};
对应二叉树和完全二叉树结构如下:
代码实现
/// 从 index 节点开始,调整二叉树,成为大(小)顶堆。调整之后,可能会使子节点不满足大(小)顶堆,会继续调整子节点。
void heapSortAdjustHandle(int* array, int length, int index) {
int parentIndex = index;
while (true) {
int parentValue = array[parentIndex];
int maxValue = parentValue;
int maxIndex = -1;
// 1.和左子节点比较大小
int leftChildIndex = 2*parentIndex + 1;
if (leftChildIndex > length-1) break;
int leftValue = array[leftChildIndex];
if (leftValue > maxValue) {
maxIndex = leftChildIndex;
maxValue = leftValue;
}
// 2.和右子节点比较大小
int rightChildIndex = 2*parentIndex + 2;
if (rightChildIndex <= length-1) {
int rightValue = array[rightChildIndex];
if (rightValue > maxValue) {
maxIndex = rightChildIndex;
maxValue = rightValue;
}
}
if (maxIndex <= -1) break;
// 3.交换最大值
array[parentIndex] = maxValue;
array[maxIndex] = parentValue;
// 4.继续调整子节点
parentIndex = maxIndex;
}
}
/// 堆排序
void heapSort(int* array, int length) {
// 1.从第一个非子节点开始,调整节点顺序,构造大(小)顶堆
for (int i=(length-1-1)/2.0; i>=0; i--) {
heapSortAdjustHandle(array, length, i);
}
// 2.循环列表,依次取出顶部元素(最大、最小元素),并继续调整剩下的元素,满足大(小)顶堆
for (int i=length-1; i>=0; i--) {
// 2.1交换首尾元素,剔除顶部元素,即选择最大或最小的元素,放在尾部
int lastValue = array[i];
array[i] = array[0];
array[0] = lastValue;
// 2.2首部元素改变,在剩下的元素(除length-1之后的元素)内,继续调整首节点,满足大(小)顶堆。
int rightBoundary = i-1;
heapSortAdjustHandle(array, rightBoundary, 0);
}
}
算法分析
最好时间复杂度:O(nlogn)
。
最坏时间复杂度:O(nlogn)
。
平均事件复杂度:O(nlogn)
。
空间复杂度:O(1)
。
稳定性:不稳定。
赏
使用支付宝打赏
使用微信打赏
若你觉得我的文章对你有帮助,欢迎点击上方按钮对我打赏
扫描二维码,分享此文章