本文介绍了几种常见的排序算法的实现,包括冒泡排序、选择排序、插入排序、希尔排序、归并排序和快速排序。冒泡排序通过多次遍历数组,比较并交换相邻元素,逐步将较小元素“浮”到数组顶端,时间复杂度为O(n^2)
。选择排序通过选择未排序部分的最小元素进行交换,逐步完成整个数组排序,同样具有O(n^2)
的时间复杂度。插入排序将数组分为已排序和未排序部分,逐个插入未排序元素到已排序部分的合适位置,时间复杂度为O(n^2)
。希尔排序是插入排序的改进版本,通过分组插入排序,最终得到有序数组,时间复杂度在O(n log n)
到O(n^2)
之间。归并排序采用分治策略,递归拆分和合并数组,时间复杂度始终为O(n log n)
,但需要额外空间。最后,快速排序通过选择基准值划分数组,并递归排序子数组,平均时间复杂度为O(n log n)
,但最坏情况下为O(n^2)
。这些算法各有特点,适用于不同场景。
冒泡排序算法
冒泡排序(Bubble Sort)算法,冒泡排序是一种简单的排序算法,它多次遍历待排序的元素,依次比较相邻的两个元素,若顺序不对则交换它们,直到整个序列有序。算法的名字源于越小的元素会经过交换“浮”到数组的顶端。
这里的BubbleSort
函数接受一个整数数组 Array
和数组的大小 ArraySize
作为参数,然后对该数组进行升序排序。排序过程采用嵌套的两个循环,外层循环(x 循环)控制每一轮的遍历,内层循环(y 循环)用于比较相邻元素并进行交换。
具体实现步骤:
- 外层循环(x 循环)遍历数组,从数组的第一个元素到倒数第二个元素。
- 内层循环(y 循环)从数组的最后一个元素向前遍历到当前外层循环位置。
- 比较相邻的两个元素,若前一个元素大于后一个元素,则交换它们的位置,确保较小的元素“浮”到数组的顶端。
- 重复进行步骤 1-3,直到整个数组有序。
这种排序算法的时间复杂度为 O(n^2)
,其中 n 是数组的大小。虽然冒泡排序不是最有效的排序算法,但它简单易懂,适用于小型数据集或部分有序的数据。在实际应用中,对于大型数据集,通常会选择更高效的排序算法,如快速排序或归并排序。
#include <stdio.h>
void BubbleSort(int Array[], int ArraySize) { int x, y, temporary;
for (x = 0; x < ArraySize - 1; x++) { for (y = ArraySize - 1; y > x; y--) { if (Array[y-1] > Array[y]) { temporary = Array[y-1]; Array[y-1] = Array[y]; Array[y] = temporary; } } } }
int main(int argc, char* argv[]) { int a[10] = { 2, 5, 6, 8, 2, 3, 9, 1, 8, 0 };
BubbleSort(a, 10);
for (int i = 0; i < 10; i++) { printf("%d ", a[i]); }
system("pause"); return 0; }
|
选择排序算法
选择排序(Selection Sort)算法,选择排序是一种简单直观的排序算法。它的基本思想是通过不断选择数组中未排序部分的最小元素,并将其与未排序部分的第一个元素交换位置,从而逐步完成整个数组的排序。
具体步骤如下:
- 初始化: 遍历整个数组,假设当前位置为最小值的位置(minimum)为起始位置。
- 查找最小值: 在未排序的部分中,从当前位置的下一个元素开始,找到比当前最小值更小的元素的位置。
- 更新最小值位置: 如果找到了比当前最小值更小的元素,更新最小值位置(minimum)。
- 交换操作: 在一次遍历结束后,将最小值位置的元素与当前位置的元素进行交换。
- 迭代: 重复以上步骤,缩小未排序部分的范围,直到整个数组排序完成。
选择排序的主要特点是不涉及大量的数据移动,但由于其时间复杂度为O(n^2)
,在大规模数据集上性能较差。
#include <stdio.h>
void SelectSort(int Array[], int ArraySize) { int x, y, minimum, temporary;
for (x = 0; x < ArraySize - 1; x++) { minimum = x; for (y = x + 1; y < ArraySize; y++) { if (Array[y] < Array[minimum]) minimum = y; } if (minimum != x) { temporary = Array[minimum]; Array[minimum] = Array[x]; Array[x] = temporary; } } }
int main(int argc, char* argv[]) { int a[10] = { 2, 5, 6, 8, 2, 3, 9, 1, 8, 0 };
SelectSort(a, 10);
for (int i = 0; i < 10; i++) { printf("%d ", a[i]); }
system("pause"); return 0; }
|
直接插入排序
插入排序(Insertion Sort)算法,插入排序是一种简单直观的排序算法,其基本思想是将数组分为已排序和未排序两部分,逐个将未排序部分的元素插入到已排序部分的合适位置。
具体步骤如下:
- 初始化: 数组的第一个元素被认为是已排序部分,从数组的第二个元素开始,将其视为未排序部分。
- 逐个插入: 遍历未排序部分的元素,逐个将其插入到已排序部分的合适位置。
- 如果当前元素小于前一个已排序元素,将其与前一个元素交换,并继续向前比较,直到找到合适的位置。
- 插入完成后,已排序部分的元素增加一个,未排序部分的元素减少一个。
- 重复: 重复以上步骤,直到未排序部分为空,整个数组排序完成。
插入排序是一种稳定的排序算法,对于小型数据集或已经基本有序的数据集,性能较好。插入排序的平均时间复杂度为O(n^2)
,适用于小规模数据排序。
#include <stdio.h>
void InsertSort(int Array[], int ArraySize) { int x, y, temporary;
for (x = 1; x < ArraySize; x++) { if (Array[x] < Array[x - 1]) { temporary = Array[x]; for (y = x - 1; Array[y] > temporary; y--) { Array[y + 1] = Array[y]; } Array[y + 1] = temporary; } } }
int main(int argc, char* argv[]) { int a[10] = { 2, 5, 6, 8, 2, 3, 9, 1, 8, 0 };
InsertSort(a, 10);
for (int i = 0; i < 10; i++) { printf("%d ", a[i]); }
system("pause"); return 0; }
|
希尔分组排序
希尔排序(Shell Sort)算法,希尔排序是一种改进的插入排序算法,其基本思想是通过将数组分成若干个子序列进行插入排序,逐渐缩小子序列的间隔,最终使整个数组成为一个有序序列。
具体步骤如下:
- 确定间隔序列: 选择一个初始间隔,通常为数组长度的一半,然后逐步减小间隔。在这个实现中,间隔的更新规则是 interval = interval / 3 + 1。
- 按间隔进行插入排序: 对每个间隔进行插入排序,即将间隔作为新的数组的步长,对每个子序列进行插入排序。
- 重复直到排序完成: 重复以上步骤,不断缩小间隔,直到间隔为1,完成最后一次插入排序,使得整个数组有序。
希尔排序的时间复杂度受到间隔序列的选择影响,通常平均时间复杂度在O(n log n)
到O(n^2)
之间。希尔排序相对于插入排序来说,在处理中等规模数据时性能较好。
#include <stdio.h>
void ShellSort(int Array[], int ArraySize) { int x, y, temporary; int interval = ArraySize;
do { interval = interval / 3 + 1; for (x = interval; x < ArraySize; x++) { if (Array[x] < Array[x - interval]) { temporary = Array[x]; for (y = x - interval; Array[y] > temporary; y -= interval) { Array[y + interval] = Array[y]; } Array[y + interval] = temporary; } } } while (interval > 1); }
int main(int argc, char* argv[]) { int a[10] = { 2, 5, 6, 8, 2, 3, 9, 1, 8, 0 };
ShellSort(a, 10);
for (int i = 0; i < 10; i++) { printf("%d ", a[i]); }
system("pause"); return 0; }
|
归并排序算法
归并排序(Merge Sort)算法,归并排序是一种分治算法,其基本思想是将数组分成两个部分,对每个部分进行递归排序,然后将两个有序的子数组合并成一个有序数组。
具体步骤如下:
- 拆分数组: 将待排序的数组分成两个子数组,分别对左右两个子数组进行递归排序。这一步骤递归执行,直到每个子数组的大小为1。
- 归并操作: 将两个有序的子数组合并成一个有序数组。合并过程中,比较两个子数组的元素,将较小的元素放入临时数组中,直到其中一个子数组的元素全部放入临时数组中。然后将另一个未空的子数组的剩余元素直接放入临时数组。
- 存储结果: 最后将归并得到的有序数组存储回原始数组中。
归并排序的时间复杂度始终为O(n log n)
,并且具有稳定性,但相对于其他排序算法,归并排序需要额外的空间来存储临时数组。
#include <stdio.h> #define MAXSIZE 10
void merging(int *list1,int list1_size,int *list2,int list2_size) { int list1_sub = 0, list2_sub = 0, k = 0; int temporary[MAXSIZE];
while (list1_sub < list1_size && list2_sub < list2_size) { if (list1[list1_sub] < list2[list2_sub]) temporary[k++] = list1[list1_sub++]; else temporary[k++] = list2[list2_sub++]; } while (list1_sub < list1_size) temporary[k++] = list1[list1_sub++]; while (list2_sub < list2_size) temporary[k++] = list2[list2_sub++];
for (int m = 0; m < (list1_size + list2_size); m++) list1[m] = temporary[m]; }
void MergeSort(int Array[], int ArraySize) { if (ArraySize > 1) { int *list1 = Array; int list1_size = ArraySize / 2;
int *list2 = Array + ArraySize / 2; int list2_size = ArraySize - list1_size;
MergeSort(list1, list1_size); MergeSort(list2, list2_size); merging(list1, list1_size, list2, list2_size); } }
int main(int argc, char* argv[]) { int a[10] = { 2, 5, 6, 8, 2, 3, 9, 1, 8, 0 };
MergeSort(a, 10); for (int i = 0; i < 10; i++) printf("%d ", a[i]);
system("pause"); return 0; }
|
快速排序算法
快速排序(Quick Sort)算法,快速排序是一种分治算法,其基本思想是选择数组中的一个元素作为基准值,然后将数组划分为两个子数组,一个子数组中的元素都小于基准值,另一个子数组中的元素都大于基准值。对这两个子数组进行递归排序,最终得到有序数组。
具体步骤如下:
- 选择基准值: 从数组中选择一个元素作为基准值(这里选择第一个元素s[0])。
- 划分数组: 设定两个指针i和j,i指向数组的起始位置,j指向数组的结束位置。通过移动指针i和j,将数组划分为两个部分,保证左边的元素小于等于基准值,右边的元素大于等于基准值。
- 递归排序: 对划分出的两个部分分别递归进行快速排序。
- 合并结果: 递归过程中,每个部分都会被排序,最终得到完整的有序数组。
快速排序是一种高效的排序算法,平均时间复杂度为O(n log n)
,但最坏情况下可能达到O(n^2)
。在实际应用中,通常表现优秀。
#include <stdio.h>
void QuckSort(int s[], int start, int end) { int i, j; i = start; j = end; s[0] = s[start]; while (i<j) { while (i<j&&s[0]<s[j]) j--; if (i<j) { s[i] = s[j]; i++; } while (i<j&&s[i] <= s[0]) i++; if (i<j) { s[j] = s[i]; j--; } } s[i] = s[0]; if (start<i) QuckSort(s, start, j - 1); if (i<end) QuckSort(s, j + 1, end); }
int main(int argc, char *argv[]) { int Array[11] = { 4, 6, 7, 8, 2, 1, 4, 5, 5, 0 };
QuckSort(Array, 0, 10);
for (int x = 0; x < 10; x++) { printf("%d ", Array[x]); }
getchar(); return 0; }
|