1. **冒泡排序(Bubble Sort)**
冒泡排序是一种简单直观的排序方法，它重复地遍历待排序序列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。其时间复杂度为O(n^2)，空间复杂度为O(1)。尽管对于大规模数据效率较低，但因其实现原理简洁易懂，在教学与小型规模数组处理中有一定价值。
c
void bubbleSort(int arr[], int n){
for (int i = 0; i < n-1 ;i++)
for (int j = 0; j < n-i-1;j++){
if(arr[j] > arr[j+1]){
swap(&arr[j], &arr[j+1]);
}
}
}
2. **选择排序(Selection Sort)**
在每一轮迭代中，该算法都会找到剩余未排好序部分里的最小（或最大）值，然后放到已排序的部分结尾处。它的平均和最坏的时间复杂度都是O(n²)，并且同样具有稳定的特性以及线性空间需求。
c
void selectionSort(int arr[], int n){
int min_idx;
// One by one move boundary of unsorted subarray
for (int i = 0; i < n-1; i++) {
// Find the minimum element in unsorted array
min_idx = i;
for (int j = i+1; j < n; j++)
if (arr[min_idx] > arr[j])
min_idx = j;
// Swap the found minimum element with the first element
swap(&arr[min_idx], &arr[i]);
}
}
3. **插入排序(Insertion Sort)**
插入排序的工作方式如同打扑克牌一样：每次从未排序区间取出一个数，将其插到已排序区间的正确位置上。当输入的数据近乎有序时，表现最好；但对于大型无序列表，则可能较为低效，最佳、最差和平均情况下的时间复杂度均为O(n²), 空间复杂度也是O(1)。
c
void insertionSort(int arr[], int n)
{
int key, j;
/* Insert each individual element to the sorted sublist */
for (int i=1; i<n; ++i)
{
key = arr[i];
/* Move elements of already sorted sublist that are greater than key,
to one position ahead of their current place */
j = i - 1;
while (j >=0 && arr[j]>key)
{
arr[j + 1] = arr[j];
j--;
}
arr[j + 1]= key;
}
}
4. **快速排序(Queue Sort)**
快速排序采用分治策略，通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。通常情况下，快速排序的平均时间为O(n logn)，但在极端条件下可能会退化至O(n²)，而空间复杂度一般认为是O(log n)但由于使用了栈或者递归来完成，所以实际上的空间消耗取决于具体的实现在堆栈深度方面的控制能力。
c
void quicksort(int *a,int low,int high){
int pivot,i,j,temp;
if(low<high){
pivot=a[low];
i=low;
j=high;
while(i<j){
while(a[++i]<=pivot);
while(j>0&&a[--j]>=pivot);
if(i<j){
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
a[low]=a[j];//把基准放在中间的位置
a[j]=pivot;//原基准赋给新的下标
quicksort(a,low,j-1);//继续分解左边子序列
quicksort(a,j+1,high);//继续分解右边子序列
}
}
5. 归并排序(Merge Sort)
归并排序也是一种基于分治思想的排序算法，首先会不断划分待排序列直到每个子序列仅包含一个元素为止，随后再合并这些已经有序的小段直至整体有序。无论原始序列如何分布，都能保持稳定性和始终如一的 O(nlogn) 时间复杂度，但是由于需要额外存储空间用于临时存放结果，故空间复杂度较高，通常是O(n)。
void merge_sort(int* A, size_t count) {
if(count <= 1) return;
const auto mid_index = count / 2;
int L[mid_index], R[count-mid_index];
memcpy(L, A, sizeof(A[0]) * mid_index);
memcpy(R, A + mid_index, sizeof(A[0]) *(count-mid_index));
merge_sort(L,mid_index);
merge_sort(R,count-mid_index);
merge(A,L,R,mid_index,(count-mid_index));
}
// 合并函数merge()
void merge(int*A,const int*L,size_t lsize,const int*R,size_t rsize){
...
}
```
总结：
以上各类排序算法各有优劣适用场景不同：
- 当面对少量或是近似有序的数据集时，插入排序和冒泡排序往往能展现出较好的效果。
- 对于大量随机排列的数据，快速排序因为拥有优秀的平均时间复杂度成为首选；
- 而当考虑稳定性要求高，同时不特别在意内存开销的情况下，归并排序则是更好的选项；
- 如果是在资源极其有限的环境中，例如嵌入式系统等场合，简单的选择排序也有可能派上用场。
理解多种不同的排序算法及其内部工作机制有助于我们针对具体的应用环境做出合适的选择，优化代码执行效能。
