用C语言的顺序表实现算法比较(包括直接插入排序、插入排序快、快速排序、希尔排序、冒泡排序、归并排序、堆排序算法)包括运行时间
时间: 2023-10-11 11:09:00 浏览: 48
由于算法比较需要对不同算法进行多次运行以得到平均时间,这里只是简单地给出各算法的时间复杂度和特点。
1. 直接插入排序
时间复杂度:O(n^2)
特点:稳定排序,适用于小规模数据。
2. 插入排序快
时间复杂度:O(n^2)
特点:较直接插入排序快,适用于小规模数据。
3. 快速排序
时间复杂度:平均情况O(nlogn),最坏情况O(n^2)
特点:适用于大规模数据,不稳定排序。
4. 希尔排序
时间复杂度:O(nlogn) ~ O(n^2)
特点:适用于大规模数据,相对于插入排序来说更快,不稳定排序。
5. 冒泡排序
时间复杂度:O(n^2)
特点:稳定排序,适用于小规模数据。
6. 归并排序
时间复杂度:O(nlogn)
特点:稳定排序,适用于大规模数据。
7. 堆排序
时间复杂度:O(nlogn)
特点:不稳定排序,适用于大规模数据,需要额外的空间来维护堆。
相关问题
用C语言的顺序表实现直接插入排序、插入排序快、快速排序、希尔排序、冒泡排序、归并排序、堆排序怕算法比较。包括运行时间
由于运行时间与数据规模、数据分布等因素有关,因此在此无法给出具体的运行时间。以下是用C语言实现的各种排序算法的代码:
1. 直接插入排序
```c
void InsertionSort(int arr[], int n) {
int i, j, tmp;
for (i = 1; i < n; i++) {
tmp = arr[i];
j = i - 1;
while (j >= 0 && arr[j] > tmp) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = tmp;
}
}
```
2. 插入排序快
```c
int BinarySearch(int arr[], int left, int right, int x) {
int mid;
while (left <= right) {
mid = (left + right) / 2;
if (arr[mid] > x) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return left;
}
void InsertionSortFast(int arr[], int n) {
int i, j, index, tmp;
for (i = 1; i < n; i++) {
tmp = arr[i];
j = i - 1;
index = BinarySearch(arr, 0, j, tmp);
while (j >= index) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = tmp;
}
}
```
3. 快速排序
```c
int Partition(int arr[], int left, int right) {
int pivot = arr[left];
while (left < right) {
while (left < right && arr[right] >= pivot) {
right--;
}
arr[left] = arr[right];
while (left < right && arr[left] <= pivot) {
left++;
}
arr[right] = arr[left];
}
arr[left] = pivot;
return left;
}
void QuickSort(int arr[], int left, int right) {
if (left < right) {
int pivotIndex = Partition(arr, left, right);
QuickSort(arr, left, pivotIndex - 1);
QuickSort(arr, pivotIndex + 1, right);
}
}
```
4. 希尔排序
```c
void ShellSort(int arr[], int n) {
int i, j, gap, tmp;
for (gap = n / 2; gap > 0; gap /= 2) {
for (i = gap; i < n; i++) {
tmp = arr[i];
for (j = i - gap; j >= 0 && arr[j] > tmp; j -= gap) {
arr[j + gap] = arr[j];
}
arr[j + gap] = tmp;
}
}
}
```
5. 冒泡排序
```c
void BubbleSort(int arr[], int n) {
int i, j, tmp;
for (i = 0; i < n - 1; i++) {
for (j = 0; j < n - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
}
}
}
}
```
6. 归并排序
```c
void Merge(int arr[], int left, int mid, int right) {
int i, j, k;
int n1 = mid - left + 1;
int n2 = right - mid;
int L[n1], R[n2];
for (i = 0; i < n1; i++) {
L[i] = arr[left + i];
}
for (j = 0; j < n2; j++) {
R[j] = arr[mid + 1 + j];
}
i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k++] = L[i++];
} else {
arr[k++] = R[j++];
}
}
while (i < n1) {
arr[k++] = L[i++];
}
while (j < n2) {
arr[k++] = R[j++];
}
}
void MergeSort(int arr[], int left, int right) {
if (left < right) {
int mid = (left + right) / 2;
MergeSort(arr, left, mid);
MergeSort(arr, mid + 1, right);
Merge(arr, left, mid, right);
}
}
```
7. 堆排序
```c
void Heapify(int arr[], int n, int i) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && arr[left] > arr[largest]) {
largest = left;
}
if (right < n && arr[right] > arr[largest]) {
largest = right;
}
if (largest != i) {
int tmp = arr[i];
arr[i] = arr[largest];
arr[largest] = tmp;
Heapify(arr, n, largest);
}
}
void HeapSort(int arr[], int n) {
int i;
for (i = n / 2 - 1; i >= 0; i--) {
Heapify(arr, n, i);
}
for (i = n - 1; i >= 0; i--) {
int tmp = arr[0];
arr[0] = arr[i];
arr[i] = tmp;
Heapify(arr, i, 0);
}
}
```
c语言实现直接插入排序,希尔排序,冒泡排序,快速排序,简单选择排序,堆排序,归并排序算法。
好的,以下是这些排序算法的C语言实现:
1. 直接插入排序
```c
void insertion_sort(int arr[], int n) {
int i, j, key;
for (i = 1; i < n; i++) {
key = arr[i];
j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}
```
2. 希尔排序
```c
void shell_sort(int arr[], int n) {
int gap, i, j, temp;
for (gap = n / 2; gap > 0; gap /= 2) {
for (i = gap; i < n; i++) {
temp = arr[i];
for (j = i; j >= gap && arr[j - gap] > temp; j -= gap)
arr[j] = arr[j - gap];
arr[j] = temp;
}
}
}
```
3. 冒泡排序
```c
void bubble_sort(int arr[], int n) {
int i, j, temp;
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;
}
}
}
}
```
4. 快速排序
```c
void quick_sort(int arr[], int left, int right) {
if (left < right) {
int pivot = partition(arr, left, right);
quick_sort(arr, left, pivot - 1);
quick_sort(arr, pivot + 1, right);
}
}
int partition(int arr[], int left, int right) {
int pivot = arr[right];
int i = left - 1;
for (int j = left; j < right; j++) {
if (arr[j] <= pivot) {
i++;
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[right]);
return i + 1;
}
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
```
5. 简单选择排序
```c
void selection_sort(int arr[], int n) {
int i, j, min_index;
for (i = 0; i < n - 1; i++) {
min_index = i;
for (j = i + 1; j < n; j++) {
if (arr[j] < arr[min_index])
min_index = j;
}
swap(&arr[min_index], &arr[i]);
}
}
```
6. 堆排序
```c
void heap_sort(int arr[], int n) {
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
for (int i = n - 1; i >= 0; i--) {
swap(&arr[0], &arr[i]);
heapify(arr, i, 0);
}
}
void heapify(int arr[], int n, int i) {
int largest = i;
int l = 2 * i + 1;
int r = 2 * i + 2;
if (l < n && arr[l] > arr[largest])
largest = l;
if (r < n && arr[r] > arr[largest])
largest = r;
if (largest != i) {
swap(&arr[i], &arr[largest]);
heapify(arr, n, largest);
}
}
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
```
7. 归并排序
```c
void merge_sort(int arr[], int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
merge_sort(arr, left, mid);
merge_sort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
}
void merge(int arr[], int left, int mid, int right) {
int i, j, k;
int n1 = mid - left + 1;
int n2 = right - mid;
int L[n1], R[n2];
for (i = 0; i < n1; i++)
L[i] = arr[left + i];
for (j = 0; j < n2; j++)
R[j] = arr[mid + 1 + j];
i = 0;
j = 0;
k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
```