C语言实现对关键字序列为(49,38,5,30,97, 76,13,27,58)的线性表分别进行简单插入排序、简单选择排序和冒泡排序实现,并分析比较它们的性能
时间: 2024-04-29 18:25:57 浏览: 8
好的,针对您的问题,我可以回答。对于给定的关键字序列(49,38,5,30,97, 76,13,27,58),使用简单插入排序,简单选择排序和冒泡排序三种算法进行排序实现,实现代码如下:
简单插入排序
```
void InsertSort(int a[], int n)
{
int i, j, k;
for (i = 1; i < n; i++)
{
if (a[i] < a[i - 1])
{
k = a[i];
for (j = i - 1; j >= 0 && a[j] > k; j--)
a[j + 1] = a[j];
a[j + 1] = k;
}
}
}
```
简单选择排序
```
void SelectSort(int a[], int n)
{
int i, j, min, t;
for (i = 0; i < n - 1; i++)
{
min = i;
for (j = i + 1; j < n; j++)
if (a[j] < a[min])
min = j;
if (min != i)
{
t = a[i];
a[i] = a[min];
a[min] = t;
}
}
}
```
冒泡排序
```
void BubbleSort(int a[], int n)
{
int i, j, t;
for (i = 0; i < n - 1; i++)
{
for (j = n - 1; j > i; j--)
if (a[j] < a[j - 1])
{
t = a[j];
a[j] = a[j - 1];
a[j - 1] = t;
}
}
}
```
比较三种算法的性能,需要分别统计它们的时间复杂度和空间复杂度:
时间复杂度:
- 简单插入排序:最好情况下O(n),最坏情况下O(n^2),平均情况下O(n^2)
- 简单选择排序:最好情况下O(n^2),最坏情况下O(n^2),平均情况下O(n^2)
- 冒泡排序:最好情况下O(n),最坏情况下O(n^2),平均情况下O(n^2)
空间复杂度:
- 简单插入排序:O(1)
- 简单选择排序:O(1)
- 冒泡排序:O(1)
综上所述,简单插入排序在最好的情况下比较快,而冒泡排序和简单选择排序在最坏情况下比较慢。在空间复杂度方面,三种算法相差不大。