【数据结构入门】排序算法之插入排序与选择排序

2024-08-29 02:04
文章标签 算法 入门 选择 数据结构 排序 插入排序

本文主要是介绍【数据结构入门】排序算法之插入排序与选择排序，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

目录

前言

一、排序的概念及运用

1.排序的概念

2.排序的运用

3.常见排序算法

二、插入排序与选择排序

2.1插入排序

2.1.1直接插入排序

1）基本思想

2）具体步骤

3）算法特性

4）算法实现

2.1.2希尔排序

1)  基本思想

2）具体步骤

3）算法特性

4）算法实现

2.2选择排序

2.2.1直接选择排序

1)  基本思想

2）具体步骤

3）算法特性

4）算法实现

 2.2.2 堆排序

1)  基本思想

2）具体步骤

3）算法特性

4）算法实现

三、算法复杂度及稳定性分析

总结

前言

在数据结构中，排序是指将一组数据按照特定的规则重新排序的过程。排序可以使数据按照升序或者降序排列，从而方便后续的操作和查找。

一、排序的概念及运用

1.排序的概念

排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。

稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。

例如：

内部排序：数据元素全部放在内存中的排序。

外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。

2.排序的运用

排序在生活中的使用无处不在，成绩排名、商品排名、电影榜单等等数不胜数。

 

3.常见排序算法

 

二、插入排序与选择排序

2.1插入排序

2.1.1直接插入排序

1）基本思想

直接插入排序是一种简单的排序算法，它的基本思想是将待排序的数据分成已排序和未排序两部分，每次从未排序部分中取出一个元素，然后将其有序地插入到已排序部分的合适位置。

当插入第i(i>=1)个元素时，前面的array[0],array[1],…,array[i-1]已经排好序，此时用array[i]的排序码与array[i-1],array[i-2],…的排序码顺序进行比较，找到插入位置即将array[i]插入，原来位置上的元素顺序后移

动画演示：

2）具体步骤

  1. 将第一个元素视为已排序部分，将剩余的元素视为未排序部分。

  2. 从未排序部分取出第一个元素，将其插入到已排序部分的合适位置。插入时，从后往前逐个比较已排序部分的元素，将大于待插入元素的元素依次后移，直到找到一个小于或等于待插入元素的位置。

  3. 重复步骤2，直到未排序部分中的所有元素都插入到已排序部分。

3）算法特性

  1. 元素集合越接近有序，直接插入排序算法的时间效率越高

  2. 时间复杂度：直接插入排序的时间复杂度是O(n^2)，其中n是待排序数据的个数。当输入数据已经基本有序时，直接插入排序的性能较好，时间复杂度可以降低到O(n)。但当输入数据完全逆序时，直接插入排序的性能较差，时间复杂度会达到最大值O(n^2)。

  3. 空间复杂度：O(1)，它是一种稳定的排序算法

  4. 稳定性：稳定

4）算法实现
void InsertSort(int* a, int n)
{for (int i = 0; i < n; i++){int end = i-1;int tmp = a[i];//将tmp插入到[0, end]区间中，保持有序while (end >= 0){if (tmp < a[end]){a[end + 1] = a[end];--end;}else{break;}}a[end + 1] = tmp;}	
}

2.1.2希尔排序

希尔排序法又称缩小增量法。

1)  基本思想

将待排序的数据按照一定的增量分组，对每组数据进行插入排序，然后逐渐减小增量，重复上述步骤，直至增量为1，完成最后一轮的插入排序。

图示：

2）具体步骤

  1. 选择一个增量序列，常用的增量序列是希尔增量（N/2, N/4, N/8...，直到增量为1）。

  2. 对于每个增量，以增量作为间隔将待排序的数据分成多个组，分别对每个组进行插入排序。

  3. 逐渐减小增量，重复上述步骤，直至增量为1。

3）算法特性

  1. 希尔排序是对直接插入排序的优化。

  2. 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。

  3. 希尔排序的时间复杂度较为复杂，最好情况下为O(n log^2 n)，最坏情况下为O(n^2)，平均情况下为O(n log n)。希尔排序的性能优于直接插入排序，尤其是对于数据量较大的情况，其性能优势更加明显。这里一般可以认为时间复杂度为O(N^1.3)左右。

  4. 稳定性：不稳定

4）算法实现

多组同时排法：

void ShellSort(int* a, int n)
{//预处理int gap = n;while (gap > 1){//这里必须保证gap最后一次是1//gap /= 2;gap = gap / 3 + 1;for (int i = gap; i < n; i++){int end = i - gap;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;}}	
}

 排完一组再排下一组：

void ShellSort(int* a, int n)
{//预处理int gap = n;while (gap > 1){//这里必须保证gap最后一次是1//gap /= 2;gap = gap / 3 + 1;for (int j = 0; j < gap; j++){for (int i = gap+j; i < n; i += gap){int end = i - gap;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;}}}	
}

2.2选择排序

2.2.1直接选择排序

1)  基本思想

每一次从待排序的数据中选择最小（或最大）的元素，放到已排序序列的末尾，直到全部待排序的数据元素排完 。

动画演示：

2）具体步骤

  1. 找到待排序序列中最小（或最大）的元素，记为A。

  2. 将A与待排序序列的第一个元素交换位置。

  3. 然后在剩余的待排序序列中找到最小（或最大）的元素，再与待排序序列的第二个元素交换位置。

  4. 重复上述步骤，直到待排序序列变为空。

3）算法特性

  1. 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用

  2. 时间复杂度：直接选择排序的时间复杂度是O(n^2)，无论输入数据的情况如何，都需要进行n-1次的比较和若干次元素交换。虽然直接选择排序的时间复杂度较高，但是它的优点是原地排序，不需要额外的空间。

  3. 空间复杂度：O(1)

  4. 稳定性：不稳定

4）算法实现
void Swap(int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}void SelectSort(int* a, int n)
{int left = 0, right = n - 1;while (left < right){int mini = left, maxi = left;for (int i = left + 1; i <= right; i++){if (a[i] < a[mini]){mini = i;}if (a[i] > a[maxi]){maxi = i;}}Swap(&a[left], &a[mini]);//如果left和maxi重叠，交换后修正一下，否则这里会出问题，换两次换回去了if (maxi == left){maxi = mini;}Swap(&a[right], &a[maxi]);left++;right--;}
}

 2.2.2 堆排序

堆排序是一种利用堆的数据结构进行排序的算法。堆是一种特殊的二叉树，满足堆性质：任意节点的值都大于等于（或小于等于）其子节点的值。需要注意的是排升序要建大堆，排降序建小堆。

1)  基本思想

将待排序的数据构造成一个堆，然后将堆顶元素与末尾元素交换，再对剩余的元素重新构造堆，以此类推，最终得到有序的序列。

2）具体步骤

  1. 构建最大堆（或最小堆），将待排序的数据转换为堆。

  2. 将堆顶元素（即最大值或最小值）与堆的最后一个叶子节点交换位置。

  3. 重新调整堆，将堆顶元素下沉，使得堆仍然满足堆性质。

  4. 重复上述步骤，直到堆只剩一个元素或为空。

3）算法特性

  1. 堆排序使用堆来选数，效率就高了很多。

  2. 时间复杂度：堆排序的时间复杂度是O(nlogn)，堆的构建需要O(n)的时间，每次调整堆的时间为O(logn)。堆排序是一种原地排序算法，不需要额外的空间。由于堆排序具有良好的局部性，适合用于大规模数据的排序。

  3. 空间复杂度：O(1)

  4. 稳定性：堆排序是一种不稳定的排序算法，相同元素的相对位置可能会改变。

4）算法实现
void ADjustDown(int* a, int sz, int parent)
{int child = parent * 2 + 1;while (child < sz){//选出左右孩子中大的一个//这里child+1的判断在前，不要先访问再判断//这里a[child + 1] > a[child] 建大堆用>， 建小堆用<if (child + 1 < sz && a[child + 1] > a[child]){//这地方可能会越界++child;}//这里a[child] > a[parent] 建大堆用>， 建小堆用<if (a[child] > a[parent]){Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}void HeapSort(int* a, int sz)
{//1.建堆 -- 向上调整建堆   NlogN//左右子树必须是大堆/小堆/*for (int i = 1; i < sz; i++){ADjustUp(a, i);}*///2.向下调整建堆  N//左右子树必须是大堆/小堆for (int i = (sz - 1 - 1) / 2; i >= 0; i--){ADjustDown(a, sz, i);}int end = sz - 1;while (end > 0){Swap(&a[end], &a[0]);ADjustDown(a, end, 0);--end;}
}

堆排序在前文中已经详细介绍了，具体见： 

【数据结构入门】二叉树之堆排序及链式二叉树

三、算法复杂度及稳定性分析

 

总结

        排序算法的选择可以根据数据的特点、数据量以及排序的要求来确定。不同的排序算法具有不同的时间复杂度和空间复杂度，因此在实际应用中需要根据具体情况选择合适的排序算法。

直接插入排序：

  • 直接插入排序是一种简单直观的排序算法，其思想是将待排序的序列分为已排序和未排序两部分，每次从未排序部分选择一个元素插入到已排序部分的合适位置，直到所有元素都插入到已排序部分为止。
  • 直接插入排序的时间复杂度为O(n^2)，是稳定的排序算法。

希尔排序：

  • 希尔排序是直接插入排序的一种改进算法，其核心思想是通过多次分组插入排序，每次对间隔较远的元素进行插入排序，逐步缩小间隔直到间隔为1，最后进行一次完整的插入排序。
  • 希尔排序的时间复杂度取决于间隔序列的选择，一般为O(nlogn)，是不稳定的排序算法。

直接选择排序：

  • 直接选择排序是一种简单直观的排序算法，其思想是每次从未排序的序列中选择最小（或最大）的元素，将其与未排序部分的第一个元素交换位置，直到所有元素都排序完成。
  • 直接选择排序的时间复杂度为O(n^2)，是不稳定的排序算法。

堆排序：

  • 堆排序利用二叉堆这种数据结构进行排序，将待排序的元素依次插入到堆中，然后从堆顶依次取出最大（或最小）的元素，直到所有元素都取出为止。
  • 堆排序的时间复杂度为O(nlogn)，是不稳定的排序算法。

 

这篇关于【数据结构入门】排序算法之插入排序与选择排序的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1116529。

相关文章

Python中的随机森林算法与实战

Python中的随机森林算法与实战

《Python中的随机森林算法与实战》本文详细介绍了随机森林算法,包括其原理、实现步骤、分类和回归案例,并讨论了其优点和缺点,通过面向对象编程实现了一个简单的随机森林模型,并应用于鸢尾花分类和波士顿房... 目录1、随机森林算法概述2、随机森林的原理3、实现步骤4、分类案例：使用随机森林预测鸢尾花品种4.1
阅读更多...
Python 中 requests 与 aiohttp 在实际项目中的选择策略详解

Python 中 requests 与 aiohttp 在实际项目中的选择策略详解

《Python中requests与aiohttp在实际项目中的选择策略详解》本文主要介绍了Python爬虫开发中常用的两个库requests和aiohttp的使用方法及其区别,通过实际项目案... 目录一、requests 库二、aiohttp 库三、requests 和 aiohttp 的比较四、requ
阅读更多...
Python中lambda排序的六种方法

Python中lambda排序的六种方法

《Python中lambda排序的六种方法》本文主要介绍了Python中使用lambda函数进行排序的六种方法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们... 目录1.对单个变量进行排序2. 对多个变量进行排序3. 降序排列4. 单独降序1.对单个变量进行排序
阅读更多...
el-select下拉选择缓存的实现

el-select下拉选择缓存的实现

《el-select下拉选择缓存的实现》本文主要介绍了在使用el-select实现下拉选择缓存时遇到的问题及解决方案,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的... 目录项目场景：问题描述解决方案：项目场景：从左侧列表中选取字段填入右侧下拉多选框，用户可以对右侧
阅读更多...
关于Java内存访问重排序的研究

关于Java内存访问重排序的研究

《关于Java内存访问重排序的研究》文章主要介绍了重排序现象及其在多线程编程中的影响,包括内存可见性问题和Java内存模型中对重排序的规则... 目录什么是重排序重排序图解重排序实验as-if-serial语义内存访问重排序与内存可见性内存访问重排序与Java内存模型重排序示意表内存屏障内存屏障示意表Int
阅读更多...
Spring Security 从入门到进阶系列教程

Spring Security 从入门到进阶系列教程

Spring Security 入门系列 《保护 Web 应用的安全》 《Spring-Security-入门（一）：登录与退出》 《Spring-Security-入门（二）：基于数据库验证》 《Spring-Security-入门（三）：密码加密》 《Spring-Security-入门（四）：自定义-Filter》 《Spring-Security-入门（五）：在 Sprin
阅读更多...
不懂推荐算法也能设计推荐系统

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例，告诉我们不懂推荐算法的产品，也能从产品侧出发， 设计出一款不错的推荐系统。 相信很多新手产品，看到算法二字，多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法（注：传统是指科班出身的产品都会接触过）。但对于推荐算法，多数产品对着网上搜到的资源，都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后，更是加大了理解的难度。 但，不了解推荐算法，就无法做推荐系
阅读更多...
如何选择适合孤独症兄妹的学校？

如何选择适合孤独症兄妹的学校？

在探索适合孤独症儿童教育的道路上，每一位家长都面临着前所未有的挑战与抉择。当这份责任落在拥有孤独症兄妹的家庭肩上时，选择一所能够同时满足两个孩子特殊需求的学校，更显得尤为关键。本文将探讨如何为这样的家庭做出明智的选择，并介绍星贝育园自闭症儿童寄宿制学校作为一个值得考虑的选项。 理解孤独症儿童的独特性 孤独症，这一复杂的神经发育障碍，影响着儿童的社交互动、沟通能力以及行为模式。对于拥有孤独症兄
阅读更多...
康拓展开（hash算法中会用到）

康拓展开（hash算法中会用到）

康拓展开是一个全排列到一个自然数的双射（也就是某个全排列与某个自然数一一对应） 公式： X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。（a[i]在不同应用中的含义不同）； 典型应用： 计算当前排列在所有由小到大全排列中的顺序，也就是说求当前排列是第
阅读更多...
csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

这是一道扩展欧几里得算法的简单应用题，这题是在湖南多校训练赛中队友ac的一道题，在比赛之后请教了队友，然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意：把题意转变下就变成了：求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点：求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2