对插入排序、选择排序、冒泡(双向冒泡)、堆排序、快速排序、归并排序等多种排序算法进行实现,输出排序中间过程、统计关键字的比较次数和记录的移动次数。
时间: 2023-09-10 17:12:10 浏览: 38
好的,我可以给你讲一下这些排序算法的实现方式,并输出排序过程中的比较次数和记录移动次数。
1. 插入排序
插入排序的实现方式是将待排序元素分为已排序和未排序两个部分,遍历未排序部分,将每个元素插入到已排序部分的正确位置。比较次数为n*(n-1)/2,移动次数最坏情况下为n*(n-1)/2。
2. 选择排序
选择排序的实现方式是每次从未排序的部分中找到最小元素,放到已排序部分的末尾。比较次数为n*(n-1)/2,移动次数为n-1。
3. 冒泡排序
冒泡排序的实现方式是遍历数组,将相邻的元素进行比较并交换位置,直到整个数组有序。比较次数为n*(n-1)/2,移动次数为最坏情况下为n*(n-1)/2。
4. 堆排序
堆排序的实现方式是将待排序元素构建成一个堆,然后将堆顶元素与最后一个元素交换位置,将堆的大小减一,重新构建堆,直到所有元素有序。比较次数为n*log2(n),移动次数为n*log2(n)。
5. 快速排序
快速排序的实现方式是选取一个基准元素,将数组分成两个部分,左边部分的元素都小于基准元素,右边部分的元素都大于基准元素。然后对左右两个部分进行递归排序。比较次数为n*log2(n),移动次数为n*log2(n)。
6. 归并排序
归并排序的实现方式是将数组分成两个部分,对每个部分进行递归排序,然后将两个有序数组合并成一个有序数组。比较次数为n*log2(n),移动次数为n*log2(n)。
以上是这些排序算法的实现方式和统计信息,希望能对你有所帮助。
相关问题
C语言,请写出对插入排序、选择排序、冒泡(双向冒泡)、堆排序、快速排序、归并排序等多种排序算法进行实现,输出排序中间过程、统计关键字的比较次数和记录的移动次数的完整代码
以下是C语言实现多种排序算法的代码,其中包括插入排序、选择排序、冒泡排序、堆排序、快速排序和归并排序,每种排序算法都输出了排序过程中的中间结果,并统计了关键字比较次数和记录移动次数。
1. 插入排序
```
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
void insertion_sort(int arr[], int n) {
int i, j, key, cmp = 0, mov = 0;
for (i = 1; i < n; i++) {
key = arr[i];
j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
cmp++;
mov++;
}
arr[j + 1] = key;
mov++;
printf("Pass %d: ", i);
for (int k = 0; k < n; k++) {
printf("%d ", arr[k]);
}
printf("\n");
}
printf("Total comparisons: %d\n", cmp);
printf("Total movements: %d\n", mov);
}
int main() {
srand(time(NULL));
int n = 10;
int arr[n];
for (int i = 0; i < n; i++) {
arr[i] = rand() % 100;
}
printf("Initial array: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
insertion_sort(arr, n);
return 0;
}
```
2. 选择排序
```
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
void selection_sort(int arr[], int n) {
int i, j, min, cmp = 0, mov = 0;
for (i = 0; i < n - 1; i++) {
min = i;
for (j = i + 1; j < n; j++) {
if (arr[j] < arr[min]) {
min = j;
}
cmp++;
}
int temp = arr[min];
arr[min] = arr[i];
arr[i] = temp;
mov += 3;
printf("Pass %d: ", i + 1);
for (int k = 0; k < n; k++) {
printf("%d ", arr[k]);
}
printf("\n");
}
printf("Total comparisons: %d\n", cmp);
printf("Total movements: %d\n", mov);
}
int main() {
srand(time(NULL));
int n = 10;
int arr[n];
for (int i = 0; i < n; i++) {
arr[i] = rand() % 100;
}
printf("Initial array: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
selection_sort(arr, n);
return 0;
}
```
3. 冒泡排序
```
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
void bubble_sort(int arr[], int n) {
int i, j, temp, cmp = 0, mov = 0;
for (i = 0; i < n - 1; i++) {
for (j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
mov += 3;
}
cmp++;
}
printf("Pass %d: ", i + 1);
for (int k = 0; k < n; k++) {
printf("%d ", arr[k]);
}
printf("\n");
}
printf("Total comparisons: %d\n", cmp);
printf("Total movements: %d\n", mov);
}
void bidirectional_bubble_sort(int arr[], int n) {
int left = 0, right = n - 1, last = right, i, temp, cmp = 0, mov = 0;
while (left < right) {
for (i = left; i < right; i++) {
if (arr[i] > arr[i + 1]) {
temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
mov += 3;
last = i;
}
cmp++;
}
right = last;
for (i = right; i > left; i--) {
if (arr[i] < arr[i - 1]) {
temp = arr[i];
arr[i] = arr[i - 1];
arr[i - 1] = temp;
mov += 3;
last = i;
}
cmp++;
}
left = last;
printf("Pass %d: ", n - (right + left) / 2);
for (int k = 0; k < n; k++) {
printf("%d ", arr[k]);
}
printf("\n");
}
printf("Total comparisons: %d\n", cmp);
printf("Total movements: %d\n", mov);
}
int main() {
srand(time(NULL));
int n = 10;
int arr[n];
for (int i = 0; i < n; i++) {
arr[i] = rand() % 100;
}
printf("Initial array: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
bubble_sort(arr, n);
printf("========================================\n");
bidirectional_bubble_sort(arr, n);
return 0;
}
```
4. 堆排序
```
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
void max_heapify(int arr[], int start, int end, int *cmp, int *mov) {
int dad = start;
int son = dad * 2 + 1;
while (son <= end) {
if (son + 1 <= end && arr[son] < arr[son + 1]) {
son++;
}
(*cmp)++;
if (arr[dad] > arr[son]) {
return;
} else {
int temp = arr[dad];
arr[dad] = arr[son];
arr[son] = temp;
(*mov) += 3;
dad = son;
son = dad * 2 + 1;
}
}
}
void heap_sort(int arr[], int n) {
int i, cmp = 0, mov = 0;
for (i = n / 2 - 1; i >= 0; i--) {
max_heapify(arr, i, n - 1, &cmp, &mov);
}
for (i = n - 1; i > 0; i--) {
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
mov += 3;
printf("Pass %d: ", n - i);
for (int k = 0; k < n; k++) {
printf("%d ", arr[k]);
}
printf("\n");
max_heapify(arr, 0, i - 1, &cmp, &mov);
}
printf("Total comparisons: %d\n", cmp);
printf("Total movements: %d\n", mov);
}
int main() {
srand(time(NULL));
int n = 10;
int arr[n];
for (int i = 0; i < n; i++) {
arr[i] = rand() % 100;
}
printf("Initial array: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
heap_sort(arr, n);
return 0;
}
```
5. 快速排序
```
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int partition(int arr[], int left, int right, int *cmp, int *mov) {
int pivot = arr[left], i = left, j = right, temp;
while (i < j) {
while (i < j && arr[j] >= pivot) {
j--;
(*cmp)++;
}
while (i < j && arr[i] <= pivot) {
i++;
(*cmp)++;
}
if (i < j) {
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
(*mov) += 3;
}
}
arr[left] = arr[i];
arr[i] = pivot;
(*mov) += 3;
printf("Pivot: %d, Pass %d: ", pivot, i - left + 1);
for (int k = 0; k < right - left + 1; k++) {
printf("%d ", arr[k + left]);
}
printf("\n");
return i;
}
void quick_sort(int arr[], int left, int right, int *cmp, int *mov) {
if (left < right) {
int pivot_index = partition(arr, left, right, cmp, mov);
quick_sort(arr, left, pivot_index - 1, cmp, mov);
quick_sort(arr, pivot_index + 1, right, cmp, mov);
}
}
int main() {
srand(time(NULL));
int n = 10;
int arr[n];
for (int i = 0; i < n; i++) {
arr[i] = rand() % 100;
}
printf("Initial array: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
int cmp = 0, mov = 0;
quick_sort(arr, 0, n - 1, &cmp, &mov);
printf("Total comparisons: %d\n", cmp);
printf("Total movements: %d\n", mov);
return 0;
}
```
6. 归并排序
```
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
void merge(int arr[], int left, int mid, int right, int *cmp, int *mov) {
int i = left, j = mid + 1, k = 0;
int *temp = (int *)malloc((right - left + 1) * sizeof(int));
while (i <= mid && j <= right) {
if (arr[i] <= arr[j]) {
temp[k++] = arr[i++];
} else {
temp[k++] = arr[j++];
}
(*cmp)++;
}
while (i <= mid) {
temp[k++] = arr[i++];
(*mov)++;
}
while (j <= right) {
temp[k++] = arr[j++];
(*mov)++;
}
for (k = 0, i = left; i <= right; k++, i++) {
arr[i] = temp[k];
(*mov)++;
}
printf("Pass: ");
for (int k = 0; k < right - left + 1; k++) {
printf("%d ", arr[k + left]);
}
printf("\n");
free(temp);
}
void merge_sort(int arr[], int left, int right, int *cmp, int *mov) {
if (left < right) {
int mid = (left + right) / 2;
merge_sort(arr, left, mid, cmp, mov);
merge_sort(arr, mid + 1, right, cmp, mov);
merge(arr, left, mid, right, cmp, mov);
}
}
int main() {
srand(time(NULL));
int n = 10;
int arr[n];
for (int i = 0; i < n; i++) {
arr[i] = rand() % 100;
}
printf("Initial array: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
int cmp = 0, mov = 0;
merge_sort(arr, 0, n - 1, &cmp, &mov);
printf("Total comparisons: %d\n", cmp);
printf("Total movements: %d\n", mov);
return 0;
}
```
冒泡排序、选择排序、插入排序、快速排序、归并排序、基数排序、堆排序对比
这些排序算法都有其优缺点,适用于不同的场景。
- 冒泡排序:最简单的排序算法之一,时间复杂度为O(n^2),稳定排序。适用于数据量小的情况。
- 选择排序:也是一种简单的排序算法,时间复杂度为O(n^2),不稳定排序。适用于数据量小的情况。
- 插入排序:对于大部分已经排序好的数据,时间复杂度为O(n),最坏情况下为O(n^2),稳定排序。适用于对于少量元素的排序。
- 快速排序:时间复杂度为O(nlogn),不稳定排序。适用于大数据量的排序。
- 归并排序:时间复杂度为O(nlogn),稳定排序。适用于大数据量的排序。
- 基数排序:时间复杂度为O(n*k),稳定排序。适用于数据量大且每个元素位数相同的情况。
- 堆排序:时间复杂度为O(nlogn),不稳定排序。适用于大数据量的排序。
综上所述,选择排序、插入排序、冒泡排序适用于数据量小的情况,而快速排序、归并排序、基数排序、堆排序适用于大数据量的情况。其中,如果需要稳定排序,则应该选择插入排序和归并排序,如果需要不稳定排序,则应该选择快速排序和堆排序。