1. 冒泡排序（从小到大）
自己的理解：有多少数就有多少轮，第一轮将最大的数放在最后（使用当前数和后一位数的比较），第二轮将第二大的数放在倒数第二，依次排好。
#include<stdio.h>
void BubbleSort(int a[],int len)
{
int i, j, temp;
for(i = 0; i < len; i++) //表示输入数组的所有数
for(j = 0; j < len-1-i; j++) //从数组第一个元素开始遍历
if(a[j] > a[j+1]) //与或后一个元素比较
{
temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
}//交换
}
int main()
{
int i, len;
int a[len];
scanf("%d", &len);
for(i = 0; i < len; i++)
scanf("%d",&a[i]);
BubbleSort(a, len);
for(i = 0; i < len; i++)
printf("%d ",a[i]);
return 0;
}
2. 选择排序
自己的理解：将数组第一个下标赋给index，然后对数组中index下标后的数进行遍历并进行判断大小，若比a[index]小，则将该数下标赋给index，若相等或比a[index]大，则继续使用下一个数进行比较，比较完所有的数，得到的index指向后面的数中最小的数。
#include<stdio.h>
void SelectionSort(int a[], int len)
{
for (int i = 0; i < len; i++)
{
int index = i;
for (int j = i+1; j < len; j++)
{
if (a[j] < a[index])
{
index = j;
}
}
if (index == i)
continue;
else
{
int temp;
temp = a[index];
a[index] = a[i];
a[i] = temp;
}
}
}
int main()
{
int i, len;
int a[len];
scanf("%d", &len);
for(i = 0; i < len; i++)
scanf("%d",&a[i]);
SelectionSort(a, len);
for(i = 0; i < len; i++)
printf("%d ", a[i]);
return 0;
}
3. 插入排序
自己的理解：遍历数组 ，从第二个数开始，向前检索，若小于前面的数则将其后移，直到比前面的数大，比后面的数小，则该数插在小的数后。像扑克牌排序一样。
#include<stdio.h>
void InsertSort(int a[], int len)
{
int i, j, temp;
for (int i = 1; i < len; i++)
{
if (a[i] < a[i - 1])
{
temp = a[i]; //插入的值
for (j = i - 1; j >= 0 && temp < a[j]; j--) //被插入的下标不能小于0
{
a[j + 1] = a[j];
}
a[j + 1] = temp;
}
}
}
int main()
{
int i, len;
int a[len];
scanf("%d", &len);
for(i = 0; i < len; i++)
scanf("%d",&a[i]);
InsertSort(a, len);
for(i = 0; i < len; i++)
printf("%d ", a[i]);
return 0;
}
4. 快速排序
自己的理解：先找一个基准值（一般是数组第一位），将比基准值小的数放在其左边，大的数放在右边。利用递归分别将基准值左右两组数进行相同操作。
#include<stdio.h>
void QuickSort(int a[], int start, int end)
{
if (start >= end)//当开始下标大于结束下表或者相等时，函数结束
return;
int i = start;
int j = end;
int base = a[start]; //基准数用base存起来
while (i < j)
{
// 从右向左找比基准数小的数
while (i < j && a[j] >= base)
{
j--;
}
if (i < j)
{
a[i] = a[j] //赋值后a[j]为无用的值
i++;
}
// 从左向右找比基准数大的数
while (i < j && a[i] < base)
{
i++;
}
if (i < j)
{
a[j] = a[i];
j--;
}
}
// 把基准数放到i的位置
a[i] = base; //无用值用基准值填充
//跳出循环后，比基准值小的数在左边，比其大的在右边
QuickSort(a, start, i - 1);// 基准值左边的数进行递归
QuickSort(a, i + 1, end);//基准值右边的数进行递归
}
int main()
{
int i, len;
int a[len];
scanf("%d", &len);
for(i = 0; i < len; i++)
scanf("%d",&a[i]);
QuickSort(a, 0, len);
for(i = 0; i < len; i++)
printf("%d ", a[i]);
return 0;
}
比较冒泡排序与选择排序：冒泡排序是每次判断交换一次位置，而选择排序是判断一个回合交换一次，选择排序的时间复杂度低。
未完待续...
