设顺序表L中存放着要排序的int类型的若干个元素,编写函数实现顺序表存储结构的直接插入排序、冒泡排序和直接选择排序。
时间: 2024-03-27 11:36:00 浏览: 62
以下是三种排序算法的实现,基于顺序表存储结构:
1. 直接插入排序
```c
void InsertSort(SqList &L) {
int i, j, temp;
for (i = 1; i < L.length; i++) {
if (L.data[i] < L.data[i - 1]) {
temp = L.data[i];
for (j = i - 1; j >= 0 && L.data[j] > temp; j--) {
L.data[j + 1] = L.data[j];
}
L.data[j + 1] = temp;
}
}
}
```
2. 冒泡排序
```c
void BubbleSort(SqList &L) {
int i, j, temp;
for (i = 0; i < L.length - 1; i++) {
for (j = 0; j < L.length - 1 - i; j++) {
if (L.data[j] > L.data[j + 1]) {
temp = L.data[j];
L.data[j] = L.data[j + 1];
L.data[j + 1] = temp;
}
}
}
}
```
3. 直接选择排序
```c
void SelectSort(SqList &L) {
int i, j, min;
for (i = 0; i < L.length - 1; i++) {
min = i;
for (j = i + 1; j < L.length; j++) {
if (L.data[j] < L.data[min]) {
min = j;
}
}
if (min != i) {
swap(L.data[min], L.data[i]);
}
}
}
```
这三种算法分别是直接插入排序、冒泡排序和直接选择排序,其中直接插入排序和冒泡排序的时间复杂度为O(n^2),直接选择排序的时间复杂度也为O(n^2),但其常数因子较小,因此效率较高。
阅读全文