排序

1、基本概念

　　1、稳定排序：a == b,a本来在b前面，排序结束a仍然在b前面

　　2、非稳定排序：a==b，a原本在b前面，排序结束b在a前面

　　3、原地排序：排序过程中不申请新的空间

　　4、非原地排序：需要利用额外的数组来辅助排序

2、排序算法

　　1、选择排序

void Selectsort(int a[],int n)
{
    int i;
    int j;
    int k;
    int min;
    int temp;
    for(i = 0;i < n;i++)
    {
        min = i;
        for(j = i + 1;j < n;j++)
        {
            if(a[min] > a[j])
            {
                min = j;
            }
        }
        if(i != min)
        {
            temp = a[i];
            a[i] = a[min];
            a[min] = temp;
        }
    }
}
//时间复杂度：O（n的平方）
//空间复杂度：O(1)
//非稳定排序
//原地排序

　　2、插入排序

void Insertsort(int a[],int n)
{
    int i;
    int j;
    int temp;
    int k;
    if(a == NULL || n < 2)
    {
        return ;
    }
    for(i = 0;i < n;i++)
    {
        temp = a[i];
        k = i-1;//挨个往前找
        //找到插入位置
        while(k >= 0 && a[k] > temp)
        {
            k--;
        }
        //腾出位置插进去，要插的位置是k+1；
        for(j = i;j > k+1; j--)
        {
            a[j] = a[j-1];
        }
        a[k+1] = temp;
    }
}
//时间复杂度O(n的平方)
//空间复杂度：O（1）
//稳定排序
//原地排序

　　3、冒泡排序

void Bubblesort(int a[],int n)
{
    int i;
    int j;
    int temp;
    for(i = 0;i < n;i++)
    {
        for(j = 0;j < n-i-1;j++)
        {
            if(a[j+1] < a[j])
            {
                temp = a[j+1];
                a[j+1] = a[j];
                a[j] = temp;
            }
        }
    }
}
//时间复杂度O(n的平方)
//空间复杂度O(1)
//稳定排序
//原地排序

//优化，如果一次循环下来一次交换操作都没有，说明此时数组有序
void highBubblesort(int a[],int n)
{
    int i;
    int j;
    int temp;
    int flag = 1;
    for(i = 0;i < n;i++)
    {
        for(j = 0;j < n-i-1;j++)
        {
            if(a[j+1] < a[j])
            {
                flag = 0;
                temp = a[j+1];
                a[j+1] = a[j];
                a[j] = temp;
            }
        }
        if(flag)
        {
            break;
        }
    }
}