选择法与插入法排序比较C++报告书

C语⾔数组的五种简单排序，选择法排序，冒泡法排序、交换法排序、插⼊法排序、折半法排序⽂章⽬录1、选择法排序选择法排序是指每次选择索要排序的数组中的最⼩值（这⾥是由⼩到⼤排序，如果是由⼤到⼩排序则需要选择最⼤值）的数组元素，将这些数组元素的值与前⾯没有进⾏排序的数组元素值进⾏互换代码实现需要注意的是：声明⼀个数组和两个整形变量，数组⽤于存储输⼊的数字，⽽整形变量⽤于存储最⼩的数组元素的数值与该元素的位置，在我的代码中实现为a[] temp position。

代码具体如下#include<stdio.h>int main(){int m,n,k;printf("please input the length of the array:");scanf("%d",&k);int a[k];int temp;int position;printf("please input the number of the array:\n");for(m=0;m<k;m++){printf("a[%d]=",m+1);scanf("%d",&a[m]);}/*从⼩到⼤排序*/for(m=0;m<k-1;m++){temp=a[m]; //设置当前的值为最⼩值position=m; //记录当前的位置for(n=m+1;n<k;n++){if(a[n]<temp){temp=a[n]; //如果找到⽐当前的还要⼩的数值，则更换最⼩的数值与位置position=n;}}a[position]=a[m];a[m]=temp;}for(m=0;m<k;m++){printf("%d\t",a[m]);}return 0;}结果如下2、冒泡法排序冒泡法排序就是值在排序时，每次⽐较数组中相邻的两个数组元素的值，将⽐较⼩的（从⼩到⼤排序算法，如果是从⼤到⼩排序算法就是将较⼤的数排在较⼩的数前⾯）排在⽐较⼤的前⾯在代码实现的过程中：声明⼀个数组与⼀个整型变量，数组⽤于存放数据元素，整型变量⽤于交换时作为中间变量。

常用排序算法分析比较排序算法是计算机科学中的基本概念之一，它主要用于对一组元素进行排序，使得这些元素按照某种规则有序排列。

常见的排序算法包括冒泡排序、插入排序、选择排序、快速排序、归并排序等等，这些算法都有自己的特点和适用场景，下面针对这些排序算法进行分析比较。

1.冒泡排序冒泡排序是一种简单的排序算法，它的主要思想是依次比较相邻的两个元素，如果它们的顺序不对就交换它们的位置，可以保证每次循环后最后一个元素是已经排序好的。

冒泡排序的时间复杂度为O(n^2)，空间复杂度为O(1)。

2.插入排序插入排序是一种稳定的排序算法，它的基本思想是将待排序的数据分为两个区间，已排序区间和未排序区间，在未排序区间内遍历，将每个元素插入到已排序区间的合适位置。

插入排序的时间复杂度为O(n^2)，空间复杂度为O(1)。

3.选择排序选择排序是一种比较简单的排序算法，它的主要思想是通过不断选择未排序区间内的最小值，然后和未排序区间的第一个元素交换位置，以此类推，直到排序完毕。

选择排序的时间复杂度为O(n^2)，空间复杂度为O(1)。

4.快速排序快速排序是一种经典的排序算法，它的思想是采用分治的思想，将序列分为左右两个子序列，通过递归的方式对左右两个子序列进行快速排序，最后合并两个排好序的子序列。

快速排序的时间复杂度为O(nlogn)，空间复杂度为O(logn)。

5.归并排序归并排序是一种稳定的排序算法，它的基本思想是采用分治的思想，将序列分为左右两个子序列，通过递归的方式对左右两个子序列进行排序，最后将两个排好序的子序列合并成一个有序序列。

归并排序的时间复杂度为O(nlogn)，空间复杂度为O(n)。

通过比较以上五种排序算法，可以发现每种算法都有自己的特点和适用场景，对于元素数量较少的情况下，可以选择冒泡排序、插入排序或选择排序，这些算法思路简单易懂，实现也比较容易；对于大规模数据排序，可以选择归并排序或快速排序，因为它们的时间复杂度比较优秀。

各种内排序算法的实验心得
1. 冒泡排序
冒泡排序是一种简单的排序算法，但它的时间复杂度为O(n^2)，在处理大量数据时效率很低。

在实验过程中，我发现当数据量较小时，冒泡排序的效率其实还是不错的，但一旦数据量增加，它的效率就明显下降了。

2. 插入排序
插入排序的时间复杂度也是O(n^2)，类似于冒泡排序。

但是插入排序比冒泡排序更快，因为它每次只需要比较一个元素。

在实验中，我发现当数据量比较小且有序时，插入排序的效率非常高，但如果数据量较大且随机分布，效率就会明显下降。

3. 选择排序
选择排序同样是时间复杂度为O(n^2)的算法，但是它比冒泡排序和插入排序都要快。

在实验中，我发现当数据量很大时，选择排序的效率比较稳定，但是当数据量比较小时，它的效率反而不如插入排序。

4. 快速排序
快速排序是一种常用的排序算法，它的时间复杂度为O(nlogn)，比冒泡、插入和选择排序都要快。

在实验中，我发现当数据量比较大时，快速排序的效率非常高，但是当数据量比较小时，它的效率反而不如插入排序和选择排序。

5. 归并排序
归并排序与快速排序的时间复杂度相同，都是O(nlogn)。

但是归并排序比快速排序更稳定，因为它的最坏时间复杂度是O(nlogn)。

在实验中，我发现当数据量比较大时，归并排序的效率非常高，而且在处理大量数据时表现优异。

6. 基数排序
基数排序是一种特殊的排序算法，它适用于数据量较大且每个元素长度相同的情况。

在实验中，我发现基数排序的效率非常高，尤其是对于大量数据的排序。

但需要注意的是，基数排序无法处理字符串等非数字类型的数据。

总结4种常⽤排序（快排、选择排序、冒泡排序、插⼊排序）⼀、选择排序1. 概念理解:最⼩的数值与第⼀个元素交换；在⼀个长度为3的数组中，在第⼀趟遍历3个数据，找出其中最⼩的数值与第⼀个元素交换最⼩的元素与第⼀个数交换(注意:这⾥的第⼀个数是指遍历的第⼀个数,实质上是数组的第⼆个数)第⼆趟遍历2个数据，找出其中最⼩的元素与第⼀个数交换⽽第三趟则是和⾃⼰⽐较,位置还是原来的位置2. 复杂度:平均时间复杂度：O（n^2）3. 例⼦://选择排序function selectionSortFn(arr){console.log('原数组:['+ arr + ']')for (var i = 0; i < arr.length; i++) {for (var j = i+1; j < arr.length; j++) {if (arr[i] > arr[j]) {var temp = arr[i];arr[i] = arr[j];arr[j] = temp;}}console.log(arr);}return arr;}var initArr = [10, 4, 8, 3];selectionSortFn(initArr);我们看⼀下打印的结果:![选择排序]原数组:[10,4,8,3][3, 10, 8, 4][3, 4, 10, 8][3, 4, 8, 10][3, 4, 8, 10]结合概念就很好理解了。

⼆、冒泡排序1. 概念理解:依次⽐较相邻的两个数，将⼩数放在前⾯，⼤数放在后⾯。

第⼀趟：⾸先⽐较第⼀个和第⼆个数，将⼩数放前，⼤数放后，然后⽐较第⼆个数和第三个数将⼩数放前，⼤数放后，如此继续，直⾄⽐较最后两个数，将⼩数放前，⼤数放后,⾄此第⼀趟结束。

在第⼆趟：仍从第⼀对数开始⽐较（因为可能由于第2个数和第3个数的交换，使得第1个数不再⼩于第2个数），将⼩数放前中，⼤数放后，⼀直⽐较到倒数第⼆个数（倒数第⼀的位置上已经是最⼤的），第⼆趟结束。

C#冒泡排序法、插⼊排序法、选择排序法是数组等线性排列的数字从⼤到⼩或从⼩到⼤排序。

以从⼩到⼤排序为例。

数据 11, 35, 39, 30, 7, 36, 22, 13, 1, 38, 26, 18, 12, 5, 45, 32, 6, 21, 42, 23使⽤数组 int [] array 存储数字。

过程 (数组从⼩到⼤排序)思路循环都把最⼤的数放在最后⼀位，⽆序数字个数减1。

i 为当前任务位置，n 剩下的⽆序数字个数从第 0位开始，⽐较前后两位数字⼤⼤⼩，当 array[i] > array[i+1] 时，数值互换。

⼀个循环后，数值最⼤的已经存到数组最后⼀位。

⽆序数字个数 n-1 for (int j = array.Length - 1; j > 0; j--) //每排⼀次，剩下的⽆序数减⼀{for (int i = 0; i < j; i++) //⼀个for循环获得⼀个最⼤的数{if (array[i] > array[i + 1]) //数值互换{var sap = array[i];array[i] = array[i + 1];array[i + 1] = sap;}}}排序结果动图如下插⼊排序法插⼊排序算法是把⼀个数插⼊⼀个已经排序好的数组中。

例如把 22 插⼊到 [1,5,10,17,28,39,42] 中，结果 [1,5,10,17,22,28,39,42] 。

对数组使⽤插⼊排序法数组 int [] array = [11, 39, 35, 30, 7, 36, 22, 13, 1, 38, 26, 18, 12, 5, 45, 32, 6, 21, 42, 23];数组元素是⽆序，设定⼀个从⼤到⼩或从⼩到⼤的⽅向，第⼀位就是有序的[ 11 ]，第⼀次插⼊： [11, 39, 35, 30, 7, 36, 22, 13, 1, 38, 26, 18, 12, 5, 45, 32, 6, 21, 42, 23]。

一、实验目的1. 理解选择排序法的原理和步骤。

2. 通过编程实现选择排序法。

3. 分析选择排序法的时间复杂度和空间复杂度。

4. 比较选择排序法与其他排序算法的性能。

二、实验环境1. 操作系统：Windows 102. 编程语言：Python3.83. 开发工具：PyCharm三、实验原理选择排序法是一种简单直观的排序算法。

它的工作原理如下：1. 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。

2. 然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。

3. 重复步骤1和2，直到所有元素均排序完毕。

选择排序法的时间复杂度为O(n^2)，空间复杂度为O(1)。

四、实验步骤1. 定义一个待排序的数组。

2. 使用两层循环遍历数组，外层循环控制排序的趟数，内层循环用于查找每一趟的最小（大）元素。

3. 将找到的最小（大）元素与未排序序列的第一个元素交换。

4. 重复步骤2和3，直到数组排序完成。

五、实验代码```pythondef selection_sort(arr):n = len(arr)for i in range(n):min_index = ifor j in range(i+1, n):if arr[j] < arr[min_index]:min_index = jarr[i], arr[min_index] = arr[min_index], arr[i]return arr# 测试数据test_arr = [64, 25, 12, 22, 11]sorted_arr = selection_sort(test_arr)print("Sorted array:", sorted_arr)```六、实验结果与分析1. 运行实验代码，得到排序后的数组：[11, 12, 22, 25, 64]。

2. 分析时间复杂度：选择排序法的时间复杂度为O(n^2)，在处理大量数据时，效率较低。

三种排序对比：选择法，插入法，冒泡法2008年05月21日星期三 09:22三种排序对比：选择法，插入法，冒泡法三种排序都是最基本的，时间复杂度最大为O(n*n)的排序方法。

这里给出的是采用数组形式的简单序列排序（从小到大）。

/*选择法*//*选择法的基本思路：第一次，从第一个记录后面待排序的的记录中，选出最小的，和第一个交换。

然后，循环做n次，这样排完后成序*//*选择法排序是不稳定的:因为两个相同的记录恰恰要反序放置*/#include<stdio.h>int main(){int a[10]={4,6,8,2,0,1,5,7,3,9};/*定义数组*/int i,j,k;for(j=0;j<9;j++)for(i=j+1;i<9;i++) /* i=j+1; 表示每次排好后的记录就不需要再判断了。

*/if(a[i]<a[j]){k=a[i];a[i]=a[j];;a[j]=k;}/*用中间变量k做交换*/for(j=0;j<=9;j++)printf("%d\n",a[j]);system("pause");}/*冒泡法*//*冒泡法的基本思路和选择法不同，如下程序，第一次，通过记录的“两两”比较将所有记录中最大的记录放到最后去。

然后循环9次即可*//*冒泡法排序是稳定的:冒泡的过程中相同的记录位置不会变*/#include<stdio.h>int main(){int a[10]={4,6,8,2,0,1,5,7,3,9};int i,j,k;for(j=0;j<9;j++)for(i=0;i<9-j;i++) /*很显然，已经放到后面的无需再参加冒泡了。

i<9-j;的意思就是*/if(a[i]>a[i+1]){k=a[i];a[i]=a[i+1];a[i+1]=k;}for(j=0;j<=9;j++)printf("%d\n",a[j]);system("pause");}/*插入法*//*插入法的的意思就和我们抓牌一样，把记录分为有序和无序两区。

c语言中冒泡排序、插入排序、选择排序算法比较c语言中冒泡排序、插入排序、选择排序算法比较掌握好常用的排序算法，在实际的项目开发中可以节省很多的时间。

每一种排序算法在执行的效率上是存在差别的，这些微小的时间差，也许在平常的联系当中感觉不到，但是涉及到数据量比较大或者是在资源比较紧张的系统中就显得尤其的重要，比如嵌入式系统。

下面简要介绍三种常用的排序算法以及他们的执行效率的比较。

以下仅供参考！冒泡排序思路：将相邻的两个数比较，将较小的数调到前头；有n个数就要进行n-1趟比较，第一次比较中要进行n-1次两两比较，在第j趟比较中，要进行n-j次两两比较。

实现代码：void BublleSort (int arr [], int count){int i, j, temp;for(j=0; j<count-1; j ) /* 冒泡法要排序n-1次*/for(i=0; i<count-j-1; i )/* 值比较大的元素沉下去后，只把剩下的元素中的最大值再沉下去就可以啦 */{if(arr[i]>arr[i 1])/* 把值比较大的.元素沉到底 */{temp=arr[i 1];arr[i 1]=arr[i];arr[i]=temp;}}}插入排序思路：在得到要排序的数组以后，讲数组分为两个部分，数组的第一个元素为一个部分，剩下的元素为一部分，然后从数组的第二个元素开始，和该元素以前的所有元素比较，如果之前的元素没有比该元素大的，那么该元素的位置不变，如果有元素的值比该元素大，那么记录相爱他所在的位置；例如I，该元素的位置为k，则将从i到k位置上的所有元素往后移动一位，然后将k位置上的值移动到i位置上。

这样就找到了K所在的位置。

每一个元素都这样进行，最终就会得到排好顺序的数组。

实现代码：void InsertSort ( int arr[],int count){int i,j,temp;for(i=1; i<count; i )//数组分两个部分，从第二个数组元素开始{temp = arr[i];//操作当前元素，先保存在其它变量中for(j=i-1; j>-1&&arr[j]>temp;j--)//从当前元素的上一个元素开始查找合适的位置，一直查找到首元素{arr[i] = arr[j];arr[j] = temp;}}}选择排序思路：首先以一个元素为基准，从一个方向开始扫描，比如从左到右扫描，以A[0]为基准，接下来从A[0]….A[9]中找出最小的元素，将其与A[0]交换。

简述插入,选择,冒泡排序实现原理插入排序，选择排序和冒泡排序是三种常见的排序算法，本文将逐步介绍它们的实现原理。

一、插入排序的实现原理插入排序是一种简单而有效的排序算法，它的实现原理可以分为以下几个步骤：1. 将待排序的数组分为已排序区和未排序区。

一开始，已排序区只有第一个元素，其余元素都在未排序区。

2. 从未排序区依次选择一个元素，将其插入到已排序区中的正确位置，使得已排序区仍然有序。

3. 重复步骤2，直到未排序区为空，整个数组有序。

具体的实现过程如下：1. 遍历未排序区的每一个元素，从第二个元素开始。

假设当前元素为key。

2. 将key与已排序区的最后一个元素进行比较，如果key小于该元素，则将该元素后移一位，直到找到key应该插入的位置。

3. 在key应该插入的位置插入key。

4. 重复步骤1-3，直到未排序区为空。

例如，对于数组[5, 2, 4, 6, 1, 3]，初始时已排序区为[5]，未排序区为[2, 4, 6, 1, 3]。

第一步，选择2作为key，将其插入到已排序区中，得到[2, 5]，此时已排序区为[2, 5]，未排序区为[4, 6, 1, 3]。

第二步，选择4作为key，将其插入到已排序区中，得到[2, 4, 5]，此时已排序区为[2, 4, 5]，未排序区为[6, 1, 3]。

以此类推，最终得到有序数组[1, 2, 3, 4, 5, 6]。

二、选择排序的实现原理选择排序是一种简单但效率不高的排序算法，其实现原理可以分为以下几个步骤：1. 将待排序的数组分为已排序区和未排序区。

初始时，已排序区为空，未排序区包含所有元素。

2. 从未排序区中选择最小（或最大）的元素，将其与未排序区的第一个元素交换位置，使得已排序区的范围扩展一个元素。

3. 重复步骤2，直到未排序区为空，整个数组有序。

具体的实现过程如下：1. 遍历未排序区的每一个元素，从第一个元素开始。

假设当前元素为key。

2. 在未排序区中找到最小（或最大）的元素，与key交换位置，使得已排序区的范围扩展一个元素。