网站怎么做响应,苗木网站怎么做,商城网站建设公司电话,北京优质网站制作目录 插入排序插入排序的思想代码实现 冒泡排序冒泡排序的思想代码实现 堆排序堆排序的基本思想代码实现 希尔排序希尔排序基本思想代码实现 选择排序选择排序基本思想代码展示 总结 插入排序
插入排序的思想
简单来说#xff0c;插入排序就时将一个数插入一个数插入一个有序… 目录 插入排序插入排序的思想代码实现 冒泡排序冒泡排序的思想代码实现 堆排序堆排序的基本思想代码实现 希尔排序希尔排序基本思想代码实现 选择排序选择排序基本思想代码展示 总结 插入排序
插入排序的思想
简单来说插入排序就时将一个数插入一个数插入一个有序的数组使之仍然有序我们可以用一张动图来展示其基本原理 从上图不难发现我们可以将第一个数看成一个有序的数因为只有一个数所以不存在有序与无序所以我们可以从第二个数开始插入使前两个数有序然后接着开始从第三个数开始插入直到最后一个数。
代码实现
//插入排序
//时间复杂度:O(N^^2)
void InsertSort(int* a, int n)
{////[0,end] end1//循环n-1次//时间复杂度:O(N^2)//最坏情况是逆序 最好情况是顺序或者接近有序for (int i 0;i n-1;i)//最后一个数是用来插入进去的所以只能遍历到n-2最后一个数直接插入进去{int end i;int tmp a[end 1];//1 2 3 4 5 .....n-1(n^2)while (end 0){if (tmp a[end]){a[end 1] a[end];end--;}else{break;}}a[end 1] tmp;}}注意不管是进入if还是进入else最后都要将tmp插入到end1中所以我们可以把这个语句放在外面
冒泡排序
冒泡排序的思想
假设排升序 冒泡排序的基本思想大致是先将 数组中前两个数进行比较然后如果前一个数大于后一个数则交换然后再将后一个数与其后一个再进行比较然后如果前一个数大于后一个数则前后两个数交换则经过一轮排序之后最大的数则会被冒到最后一个位置以此类推我们不难发现如果是十个数的话我们只需要冒泡九轮所以最后冒泡的次数是数组的元素个数减一。 动图展示
代码实现
根据上面的描述我们可以很容易得写出相应的代码
void Swap(int* ps, int* pa)
{int tmp *ps;*ps *pa;*pa tmp;
}
//冒泡排序
void BubbleSort(int* a, int n)
{for (int i 0;i n;i){for (int j 0;j n - 1 - i;j){if (a[j] a[j 1]){Swap(a[j], a[j 1]);}}}
}注意冒泡排序的时间复杂度是O(N^2) 为此我们还可以对冒泡排序进行优化我们知道冒泡排序不管这个数组有没有序都会将数组遍历一遍所以我们可以定义一个标记是否进行交换的变量exchange如果在一轮循环中exchange没有发生变化则证明在这次循环中根本没有交换所以我们可以直接终止这次循环 改进后的代码如下
void NewBubbleSort(int* a, int n)
{for (int i 0;i n - 1;i){int exchange 0;//标志---一个轮回都没有交换for (int j 1;j n - j;j){if (a[j - 1] a[j]){Swap(a[j], a[j 1]);exchange 1;//交换了就令exchange为1}}//一轮之后判断exchange是否改变if (exchange 0){break;}}
}堆排序
堆排序的基本思想
堆排序是一种基于二叉堆数据结构的排序算法。其基本思想可以总结如下 建立堆 将待排序的数据构建成一个最大堆或最小堆即满足堆的性质父节点的值总是大于等于最大堆或小于等于最小堆其子节点的值。建立堆的过程一般从最后一个非叶子节点开始依次向前调整使得每个节点都满足堆的性质。 堆调整 将堆顶元素最大值或最小值与堆的最后一个元素交换并将堆的大小减一然后对堆顶元素进行调整使得剩余元素重新构成一个最大堆或最小堆。 重复步骤2 不断重复进行堆调整的过程直到堆的大小减为1即所有元素都被排序完成。 堆排序的关键在于建立堆和堆调整的过程。通过构建最大堆堆顶元素就是整个序列中的最大值在每一轮的堆调整中将最大值移动到序列的末尾从而完成排序。同样如果需要按照从小到大的顺序排序可以构建最小堆并将堆顶元素移动到序列的末尾。 动图展示
注意假设我们要排升序则应该建大堆这里解释一下为什么如果我们建小堆的话我们只能取到堆顶元素是最小的取完堆顶元素之后又要对剩下的元素重新建堆这样的消耗是很大的但是如果我们建大堆的话我们可以知道最大的元素时堆顶然后将堆顶的元素交换到最后一层的最后一个元素然后再对剩下的元素进行一次向下调整再选出次大的这样根本不用重新建堆不管是对空间还是对时间的消耗都是最小所以我们排升序选择建大堆。 堆排序 第一步建堆 第二部交换堆顶和堆底的元素然后再向下调整。
代码实现
//堆排序
void AdjustDown(int* a, int n, int root)
{int parent root;int child root * 2 1;while (child n){if (a[child] a[child] child 1 n){child;}if (a[child] a[parent]){Swap(a[child], a[parent]);child parent;parent (child - 1) / 2;}else{break;}}
}
void HeapSort(int* a, int n)
{//建堆for (int i (n - 1 - 1) / 2;i 0;i--){AdjustDown(a, n, i);}int end n - 1;while (end 0){Swap(a[0], a[end]);AdjustDown(a, end, 0);end--;}
}希尔排序
希尔排序基本思想
希尔排序Shell Sort是一种改进的插入排序算法也被称为缩小增量排序。其基本思想是通过比较相距一定间隔称为增量的元素使得每一轮比较的元素距离越来越近最终使得整个序列基本有序然后再进行最后一轮插入排序。
希尔排序的具体步骤如下 选择增量序列 选择一个增量序列用于指定待排序序列中相邻元素之间的间隔。通常的增量序列选择包括Hibbard序列、Sedgewick序列等。增量序列的选择会影响希尔排序的性能。 根据增量序列进行分组 将待排序序列分成若干个子序列每个子序列包含间隔为增量的元素。对每个子序列分别进行插入排序。 逐步缩小增量 不断减小增量重复步骤2直到增量为1。这样最后一轮排序将是一次插入排序但是由于之前的步骤已经使得序列基本有序因此插入排序的时间开销会大大减少。
希尔排序之所以有效是因为它在一开始通过较大的增量将元素分成较少的子序列对这些子序列进行插入排序可以使得元素移动的距离减少从而减少了插入排序的时间复杂度。随着增量的逐步减小最终一轮的插入排序对于基本有序的序列而言时间开销较小。
希尔排序的时间复杂度与增量序列的选择有关最好的情况下可以达到O(n log n)最坏情况下为O(n^2)。希尔排序是一种不稳定的排序算法但由于其简单且在某些情况下表现良好仍然被广泛使用。
注意我们接下来展示的是将希尔排序的间隔定义为2的情况下展开的 先用动图展示
代码实现
//gap越大数据跳到越快
void ShellSort(int* a, int n)
{//分组预排插入目标:大的数更快的跳到后面小的数更快的跳到前面int gap n;while (gap 1){gap / 2;for (int i 0;i n - gap;i gap){int end i;int tmp a[end gap];while (end 0){if (tmp a[end]){a[end gap] a[end];end - gap;}else{break;}}a[end gap] tmp;}}}注意上面代码随着gap的减小逐渐接近有序直到最后gap等于1的时候就是我们前面讲到的插入排序。
选择排序
选择排序基本思想
讨论升序的情况 选择排序的基本思想遍历整个数组选出最大的元素然后插入到最后一个位置然后从剩下的数组中选出次大的然后插入到倒数第二个位置以此类推 动图展示
代码展示
void SelectSort(int* a, int n)
{int begin 0, end n - 1;//选出最小值和最大值的位置int mini begin, maxi begin;while (begin end){for (int i begin;i end;i){if (a[i] a[mini]){mini i;}if (a[i] a[maxi]){maxi i;}}if (maxi begin){maxi mini;}Swap(a[begin], a[mini]);Swap(a[end], a[maxi]);begin;end--;}
}注意这里我们我们可以利用两个指针一个指向头一个指向尾然后将最小的元素插入到数列的首位置将最大的元素插入到数组尾的位置然后依次向中间遍历这样优化可以将以前的执行次数减少一半因为我同时选出了最大和最小的元素。
总结
当然可以。以下是一个关于排序算法的总结
总的来说排序算法是计算机科学中一个重要而基础的主题它们在日常生活和各种应用中都扮演着重要的角色。通过对各种排序算法的了解和研究我们可以更好地理解数据的组织和处理方式从而提高算法的效率和性能。
在本文中我们介绍了几种常见的排序算法包括冒泡排序、选择排序、插入排序、归并排序、快速排序、堆排序和希尔排序。每种算法都有其独特的思想和实现方式并且在不同的应用场景下具有不同的优缺点。
冒泡排序和选择排序是最简单的排序算法之一虽然它们的时间复杂度较高但对于小规模数据集合仍然是一种有效的选择。插入排序通过构建已排序部分来不断插入新元素具有较好的性能表现特别适用于部分有序的数据。归并排序和快速排序是两种基于分治思想的高效排序算法它们具有较好的平均时间复杂度并且可以在大规模数据集合下快速排序。堆排序利用堆数据结构实现了一种高效的排序算法尤其适用于需要原地排序的情况。希尔排序则是一种改进的插入排序算法通过逐步缩小增量实现了对基本有序序列的高效排序。
除了这些算法外还有许多其他排序算法每种都有其特定的应用场景和优劣势。在选择排序算法时需要考虑数据规模、数据特征、时间复杂度和空间复杂度等因素并根据实际情况选择最合适的算法。
总的来说排序算法是计算机科学中一个基础而重要的研究领域通过不断地学习和研究排序算法我们可以更好地理解和应用算法提高程序的效率和性能为解决实际问题提供更好的解决方案。
