排序

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;
}

比较冒泡排序与选择排序：冒泡排序是每次判断交换一次位置，而选择排序是判断一个回合交换一次，选择排序的时间复杂度低。

未完待续...

5. 归并排序

6. 堆排序