1g内存的服务器可以建设几个网站,域名邮箱企业邮箱,高级室内设计网站,各地平台网站全文目录引言选择排序思路实现堆排序思路实现总结引言
从这篇文章开始#xff0c;将介绍几大排序算法#xff1a;选择排序、堆排序、直接插入排序、希尔排序、冒泡排序、快速排序、归并排序以及计数排序。
在本篇文章中要介绍的是选择排序与堆排序#xff0c;它们都属于选…
全文目录引言选择排序思路实现堆排序思路实现总结引言
从这篇文章开始将介绍几大排序算法选择排序、堆排序、直接插入排序、希尔排序、冒泡排序、快速排序、归并排序以及计数排序。
在本篇文章中要介绍的是选择排序与堆排序它们都属于选择排序。 这两种排序算法的思想都是从待排序的数据元素中选出最大或最小的元素放在序列的起始位置或末尾位置以此来使整个序列有序
选择排序
思路
选择排序就很符合上面的描述从数组中选出最小的元素放在数组的起始位置。然后就相当于起始位置的元素就是正确的位置也就相当于需要排序的部分减少了一个元素。由此循环就可以实现排序整个数组
实现
这样的思路很明显是需要两层循环的 内层循环需要确定出当前待排序部分中最小的元素并将其下标记录下来。每次内层循环后将最小元素与待排徐部分的起始元素交换 外层循环需要缩小待排序部分的大小。从数组的大小开始直到待排序部分为0即整个数组排序完毕 void Swap(int* a, int m, int n)//交换
{int temp a[n];a[n] a[m];a[m] temp;
}
//选择排序
void SelectSort(int* a, int n)
{for (int i 0; i n - 1; i){int min a[i];int mini i;for (int j i 1; j n; j){if (a[j] min){min a[j];mini j;}}Swap(a, i, mini);}
}堆排序
思路
堆排序是建立在二叉树上的一种排序方法在前面我们详细介绍了二叉树与堆这种数据结构。 对于大堆而言堆顶的元素是该堆中最大的元素。我们只需要通过不断建堆不断将堆顶的元素放到当前待排序的部分的末尾。就相当于末尾元素就在其正确的位置。逐渐缩小堆的大小就可以实现排序整个数组。
实现
在这个思路下我们需要两次循环
第一次循环实现将当前数组所有元素建大堆。 建堆时有两种方式向上调整建堆与向下调整建堆 向上调整建堆时类似于二叉树的尾插然后将这个尾插的数向上调整放到合适的位置 向下调整建堆时即将每一个根结点向下调整放在其合适的位置。这要求该根的子树都是正确的大堆所以我们需要从倒数第二层的根结点开始向下调整 向下调整建堆的时间复杂度是比向上调整少的在这里不做证明在本篇文章中也只实现向下调整建堆 第二次循环需要实现不断将堆顶的元素与当前待排序部分所建堆的末尾元素交换使该元素完成排序。然后待排序的部分缩小待排序部分再次建大堆。直到排序结束
关于向下调整的AdjustDown函数在堆中有详细讲解这里就不赘述戳我看堆及其实现详解
void Swap(int* a, int m, int n)//交换
{int temp a[n];a[n] a[m];a[m] temp;
}
void AdjustDwon(int* a, int n, int root)//向下调整建堆
{int parent root;int child parent * 2 1;while (child n){if (child 1 n a[child 1] a[child]){child;}if (a[child] a[parent]){Swap(a, child, parent);parent child;child parent * 2 1;}else{break;}}
}
//堆排序
void HeapSort(int* a, int n)
{for (int i (n - 2) / 2; i 0; i--)//建堆{AdjustDwon(a, n, i);}for (int i 1; i n ; i)//排序{Swap(a, 0, n-i);AdjustDwon(a, n - i, 0);}
}总结
到此关于选择排序与堆排序的内容就介绍完了 接下来会继续介绍其他的排序欢迎持续关注哦
如果大家认为我对某一部分没有介绍清楚或者某一部分出了问题欢迎大家在评论区提出
如果本文对你有帮助希望一键三连哦
希望与大家共同进步哦
