C语言实现选择排序、直接插入排序、冒泡排序的示例
选择排序
选择排序是一种简单直观的排序算法，其核心思想是：遍历数组，从未排序的序列中找到最小元素，将其放到已排序序列的末尾。
时间复杂度：O(n^2)
稳定性：不稳定
/*
*@briefselectionsort
*/
void
selection_sort(inta[],intn)
{
inti,j,min,tmp;
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){
tmp=a[min];
a[min]=a[i];
a[i]=tmp;
}
}
}
直接插入排序
直接插入排序是一种比较容易理解的排序算法，其核心思想是遍历数组，将数组中的元素逐个插入到已排序序列中。
时间复杂度：O(n^2)
稳定性：稳定
实现：
/*@briefinsetionsort
*insertthenewelementtothesortedsubarray
*/
void
insertion_sort(inta[],intn)
{
inti,j,num;
for(i=1;i<n;++i){
num=a[i];
for(j=i-1;j>=0&&a[j]>num;--j)
a[j+1]=a[j];
a[j+1]=num;
}
}
冒泡排序
冒泡排序是最基本的排序算法之一，其核心思想是从后向前遍历数组，比较a[i]和a[i-1]，如果a[i]比a[i-1]小，则将两者交换。这样一次遍历之后，最小的元素位于数组最前，再对除最小元素外的子数组进行遍历。进行n次（n数组元素个数）遍历后即排好序。外层循环为n次，内层循环分别为n-1，n-2…1次。
时间复杂度：O(n^2)
稳定性：稳定
实现：
/*@briefbubblesort
*movethesmallestelementtothefrontineverysingleloop
*/
void
bubble_sort(inta[],intn)
{
inti,j,tmp;
for(i=0;i<n;++i){
for(j=n-1;j>i;--j){
if(a[j]<a[j-1]){
tmp=a[j];
a[j]=a[j-1];
a[j-1]=tmp;
}
}
}
}