随机生成100个正整数，分别用冒泡，选择，插入排序，用C语言写代码

#include "stdioh"
void main()
{
int a[9]={1,3,5,7,9,10,12,14};
int b,i,j;
scanf("%d",&b);

for(i=0;i<8;i++){
if(a[i]>=b){ /找到插入位置/
for(j=8;j>i;j--) /后面元素均后移一位/
a[j] = a[j-1];
a[i] = b; /插入/
break;
}
}
if(i==8) /若该数大于所有数/
a[8] = b;

在插入排序、冒泡排序、快速排序、归并排序等排序算法中，占用辅助空间最多的是归并排序。

对n个记录的文件进行快速排序，所需要的辅助存储空间大致为O(1og2n)。

1、所有的简单排序方法（包括：直接插入、起泡和简单选择）和堆排序的空间复杂度为O(1)；

2、快速排序为O(logn)，为栈所需的辅助空间；

3、归并排序所需辅助空间最多，其空间复杂度为O(n)；

4、链式基数排序需附设队列首尾指针，则空间复杂度为O(rd)。

扩展资料

计算机排序算法的特点

1、有穷性

一个算法应包含有限的 *** 作步骤，而不能是无限的。有穷性值在合理范围之内，如果让计算机执行一个历时1000年才结束的算法，这虽然是有穷的，但超过了合理的限度，人们不把他视为有效算法。

2、确定性

算法中的每一个步骤都应当是确定的，而不应当是含糊的，摩棱两可的。算法中的每一个步骤应当不致被解释成不同含义的，而应是十分明确的。也就是说，算法的含义应当是唯一的，而不应当产生歧义性。

3、有零个或多个输入

所谓输入，即在执行算法是需要从外界取得必要的信息。

4、有一个或多个输出

算法的目的是为了求解，没有输出的算法是没有意义的。

5、有效性

算法中的每一个步骤都应当能有效的执行，并得到确定的结果。

作为一名学生，我们要掌握做笔记的方法，这样才能让我们的学习事半功倍，接下来我来分享一下我做笔记的方法。

1、做标记：

最简单的读书笔记，就是在读书的时候，读到认为重要的地方的时候，采用自己的一套符号来画出重要内容，以便自己在复习的时候能够快速的找到重点，这种笔记的方法比较适合学生学习课本的时候。

2、做目录：

目录的主要内容就是书名作者重点内容。书名和作者就不必解释了，关键是重点内容，由于这是一个目录式的笔记，所以重点内容只要是几个字概括一下即可，一般适合泛读的时候使用。

3、摘抄：

摘抄也是一个比较简单的读书笔记，读书的时候读到精彩的地方，或者读到一些自己认为有用的地方，将这段文字抄下来，注明书名和作者，这么做是为了以后复习用，并且可以根据书名和作者快速的找到原著。

4、提要：

提要用简短的话来总结书中某一段落的内容，有时候会要求对每一段的内容写一个提要，只要一两句话即可概括其内容，不必写得很繁琐。

5、提纲：

提纲和提要有些类似，但是提纲是概括一篇文章的内容，而提要只是概括一个段落的内容，因此提纲比提要内容多且完整，而且提纲要能解释各个章节和段落之间的关系，所以提纲有时候是以图表的方式来呈现，不过提纲和提要都要求尽量简短明了，让人一看就明白。

6、心得：

有时候也叫读后感，心得和提纲有些相似的地方，都要对文章的内容进行概括，但是心得更多的是些自己的想法，具有主观性，而提纲写的都是文章中的内容，不要加入自己的想法，当读一些学术论文、有哲理的故事的时候可以写一些心得，记录下自己的想法以便日后用到。

7、札记：

札记是最复杂的可以看作是提纲和心得的综合，有时候还要插入一些摘抄，还可以对文章的写法进行评论，总之写札记不仅仅费笔墨而且费脑子，这已经不仅仅是一种笔记，应该是对学习到的内容的再创作。

(相邻元素交换顺序）
冒泡的过程只涉及相邻数据的交换 *** 作，只需要常量级的临时空间，所以它的空间复杂度为O(1)， 是一个原地排序算法。
第二，冒泡排序是稳定的排序算法吗 在冒泡排序中，只有交换才可以改变两个元素的前后顺序。为了保证冒泡排序算法的稳定性，当有 相邻的两个元素大小相等的时候，我们不做交换，相同大小的数据在排序前后不会改变顺序，所以 冒泡排序是稳定的排序算法。
第三，冒泡排序的时间复杂度是多少
最好情况下，要排序的数据已经是有序的了，我们只需要进行一次冒泡 *** 作，就可以结束了，所以 最好情况时间复杂度是O(n)。而最坏的情况是，要排序的数据刚好是倒序排列的，我们需要进行n 次冒泡 *** 作，所以最坏情况时间复杂度为O(n2)。

（第一个数是排序好的和后面是无序的数字，左边是排序好的，右边是没排序好的，从右边拿第一个数和左边倒叙循环判断插入到指定位置）
首先，我们将数组中的数据分为两个区间，已排序区间和未排序区间。初始已排序区间只有一个元 素，就是数组的第一个元素。插入算法的核心思想是取未排序区间中的元素，在已排序区间中找到 合适的插入位置将其插入，并保证已排序区间数据一直有序。重复这个过程，直到未排序区间中元 素为空，算法结束。
第一，插入排序是原地排序算法吗
从实现过程可以很明显地看出，插入排序算法的运行并不需要额外的存储空间，所以空间复杂度是 O(1)，也就是说，这是一个原地排序算法。
第二，插入排序是稳定的排序算法吗 在插入排序中，对于值相同的元素，我们可以选择将后面出现的元素，插入到前面出现元素的后 面，这样就可以保持原有的前后顺序不变，所以插入排序是稳定的排序算法。 第三，插入排序的时间复杂度是多少 如果要排序的数据已经是有序的，我们并不需要搬移任何数据。如果我们从尾到头在有序数据组里 面查找插入位置，每次只需要比较一个数据就能确定插入的位置。所以这种情况下，最好是时间复 杂度为O(n)。注意，这里是从尾到头遍历已经有序的数据。 如果数组是倒序的，每次插入都相当于在数组的第一个位置插入新的数据，所以需要移动大量的数
2
据，所以最坏情况时间复杂度为O(n2)。 还记得我们在数组中插入一个数据的平均时间复杂度是多少吗没错，是O(n)。所以，对于插入排 序来说，每次插入 *** 作都相当于在数组中插入一个数据，循环执行n次插入 *** 作，所以平均时间复 杂度为O(n2)。

选择排序算法的实现思路有点类似插入排序，也分已排序区间和未排序区间。但是选择排序每次会 从未排序区间中找到最小的元素，将其放到已排序区间的末尾。
选择排序是一种不稳定的排序算法。

冒泡排序，插入排序，归并排序，基数排序是稳定的排序。快速排序，选择排序，堆排序，希尔排序是不稳定的排序。
冒泡排序，插入排序，选择排序的时间复杂度是O(n^2)，归并排序，堆排序，快速排序的时间复杂度都是O(nlog(n))，空间复杂度冒泡排序，插入排序，选择排序都是O（1），归并排序为O（n）。

//选择排序
#include<stdioh>
void main()
{int i,n,j,k,temp,a[100];
 printf("Input n:\n");
 scanf("%d",&n); 
 printf("Input the arry:\n");
 for(i=0;i<n;i++) 
  scanf("%d",&a[i]);
 for(i=0;i<n;i++) 
 { k=i; /给记号赋值/ 
   for(j=i+1;j<n;j++) 
     if(a[k]>a[j]) k=j; /是k总是指向最小元素/ 
   if(i!=k)    /当k!=i是才交换，否则a[i]即为最小/
     { temp=a[i]; a[i]=a[k]; a[k]=temp;}
  }
 printf("After the arrangement:\n");
 for(i=0;i<n;i++) 
   printf("%d ",a[i]);
 printf("\n");
 }//冒泡排序
#include<stdioh>
void main()
{int n,i,j,temp,a[100];
 printf("Input n:\n");
 scanf("%d",&n); 
 printf("Input the arry:\n");
 for(i=0;i<n;i++) 
  scanf("%d",&a[i]);
 for(j=n-1;j>0;j--)  //依次判断当前最大值，冒泡地将其放在最后的位置
 for(i=0;i<j;i++)
    if(a[i]>a[i+1])   { temp=a[i]; a[i]=a[i+1]; a[i+1]=temp;}
 printf("After the arrangement:\n");
 for(i=0;i<n;i++) 
   printf("%d ",a[i]);
 printf("\n");
 }

---