(1)建立100个以上元素的线性表; (2)分别利用选择类排序、插入类排序、交换类排序、归并排序等各种排序方法对他们进行排序,并输出各自的比较和移动次数。 (3)分别在排序前的表中实现顺序查找,在排序后的表中实现二分查找,统计各自的比较次数。
时间: 2023-03-19 20:29:09 浏览: 188
(1) 建立100个以上元素的线性表可以使用数组或链表等数据结构来实现。
(2) 对于选择类排序,比较次数为n(n-1)/2,移动次数为n-1;对于插入类排序,比较次数为n(n-1)/2,移动次数为n(n-1)/2;对于交换类排序,比较次数为n(n-1)/2,移动次数为3(n-1);对于归并排序,比较次数为nlogn,移动次数为2nlogn。
(3) 在排序前的表中实现顺序查找,比较次数为n;在排序后的表中实现二分查找,比较次数为log2n。
相关问题
分别采用直接插入排序,简单选择排序,冒泡排序,快速排序,归并排序的算法对给 定的线性表进行排序。
直接插入排序:
直接插入排序的基本思想是将一个记录插入到已排好序的有序表中,从而得到一个新的、记录数增加1的有序表。
具体步骤如下:
1.将第一个元素看作是一个有序的子序列,然后从第二个元素开始,依次将每个元素插入到已经排好序的子序列中。
2.将未排序的第一个元素,即a[1]与a[0]比较大小,如果a[1] < a[0],则将a[1]插入到a[0]前面,否则a[1]已经是有序的了。
3.将未排序的第二个元素,即a[2]与已经排好序的子序列比较大小,找到合适的位置插入,依次类推。
简单选择排序:
简单选择排序的基本思想是在未排序的序列中找到最小元素,然后将其放到已排序序列的末尾。
具体步骤如下:
1.将序列分为已排序和未排序两部分,初始时已排序部分为空,未排序部分包括所有元素。
2.在未排序部分中找到最小的元素,将其放到已排序部分的末尾。
3.重复步骤2,直到未排序部分为空。
冒泡排序:
冒泡排序的基本思想是比较相邻的两个元素,如果前一个元素比后一个元素大,则交换这两个元素的位置,从而使较大的元素逐渐往后移动。
具体步骤如下:
1.从序列的第一个元素开始,依次比较相邻的两个元素,如果前一个元素比后一个元素大,则交换这两个元素的位置。
2.重复步骤1,直到序列中所有相邻的元素都被比较过一次。
3.重复步骤1和步骤2,直到序列中的所有元素都排好序。
快速排序:
快速排序的基本思想是通过一趟排序将待排序序列分割成独立的两部分,其中一部分的所有元素都比另一部分的所有元素小,然后再按照此方法依次对两部分继续进行排序,直到整个序列有序。
具体步骤如下:
1.选取一个基准元素,一般选择第一个元素或者最后一个元素。
2.将序列中所有小于基准元素的元素放在基准元素的左边,所有大于基准元素的元素放在基准元素的右边。
3.对左右两个子序列分别进行快速排序,直到整个序列有序。
归并排序:
归并排序的基本思想是将两个有序的子序列合并成一个有序的序列。
具体步骤如下:
1.将序列分成两个子序列,分别进行归并排序。
2.将两个有序的子序列合并成一个有序的序列。
3.重复步骤1和步骤2,直到序列有序。
分别采用直接插入排序,简单选择排序,冒泡排序,快速排序,归并排序的算法对给 定的线性表进行排序。C语言代码
好的,我可以给你介绍一下这些排序算法的C语言实现代码。以下是各个算法对线性表进行排序的代码示例:
1. 直接插入排序:
```c
void InsertSort(int a[], int n) {
int i, j, temp;
for (i = 1; i < n; i++) {
temp = a[i];
for (j = i - 1; j >= 0 && a[j] > temp; j--)
a[j + 1] = a[j];
a[j + 1] = temp;
}
}
```
2. 简单选择排序:
```c
void SelectSort(int a[], int n) {
int i, j, min, temp;
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) {
temp = a[i];
a[i] = a[min];
a[min] = temp;
}
}
}
```
3. 冒泡排序:
```c
void BubbleSort(int a[], int n) {
int i, j, temp;
for (i = 0; i < n - 1; i++)
for (j = 0; j < n - i - 1; j++)
if (a[j] > a[j + 1]) {
temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
}
}
```
4. 快速排序:
```c
void QuickSort(int a[], int left, int right) {
int i, j, temp, pivot;
if (left < right) {
i = left;
j = right + 1;
pivot = a[left];
do {
do i++; while (a[i] < pivot);
do j--; while (a[j] > pivot);
if (i < j) {
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
} while (i < j);
temp = a[left];
a[left] = a[j];
a[j] = temp;
QuickSort(a, left, j - 1);
QuickSort(a, j + 1, right);
}
}
```
5. 归并排序:
```c
void Merge(int a[], int low, int mid, int high, int temp[]) {
int i = low, j = mid + 1, k = 0;
while (i <= mid && j <= high) {
if (a[i] < a[j]) temp[k++] = a[i++];
else temp[k++] = a[j++];
}
while (i <= mid) temp[k++] = a[i++];
while (j <= high) temp[k++] = a[j++];
for (i = 0; i < k; i++) a[low + i] = temp[i];
}
void MergeSort(int a[], int low, int high, int temp[]) {
if (low < high) {
int mid = (low + high) / 2;
MergeSort(a, low, mid, temp);
MergeSort(a, mid + 1, high, temp);
Merge(a, low, mid, high, temp);
}
}
void MergeSort(int a[], int n) {
int* temp = (int*)malloc(sizeof(int) * n);
MergeSort(a, 0, n - 1, temp);
free(temp);
}
```
希望这些代码能够对你有所帮助。
相关推荐
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![ppt](https://img-home.csdnimg.cn/images/20210720083527.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)