排序-插入排序与选择排序

插入排序

基本思想

把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列 。

打扑克牌整理手牌用的就是插入排序的思想

代码实现

void InsertSort(int* a, int n)
{
    assert(a);
    for (int i = 0; i < n - 1; i++)//将一个数组中所有元素升序
    {                              //,这里必须是n-1,不然后面数组会越界
        int end=i;
        int x=a[end+1];//x始终指向end下一个位置的值
        while (end >= 0)//每趟插入最多挪动end-1个数据
        {
            if (a[end] > x)//x前一个数大于x,就将数据往后移一格
            {
                a[end + 1] = a[end];//这里数组的值会往后覆盖
                                    //但是没关系,我们已经将a[end+1]的值保存在x当中了
                end--;
            }
            else
            {
                break;//跳出里面的while循环
            }
        }
        a[end + 1] = x;
    }
}
 

特性总结

1. 元素集合越接近有序，直接插入排序算法的时间效率越高
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)，它是一种稳定的排序算法
4. 稳定性：稳定

选择排序

基本思想

每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完 。

就像小学生排队一样，让最矮的那个站到第一排，然后让第二矮的占到第二排，以此类推

代码实现

void SelectSort(int* a, int n)
{
    int begain = 0;
    int end = n - 1;
    while (begain < end)
    {
        int maxi = begain;//初始化最值
        int mini = begain;
        for (int i = begain; i <= end; i++)
        {
            if (a[i] < a[mini])
            {
                mini = i;//记录下标,否则会有数据被覆盖的问题
            }
            if (a[i] > a[maxi])
            {
                maxi = i;
            }
        }
        swap(&a[begain], &a[mini]);//将最大最小值交换
        swap(&a[end], &a[maxi]);
        begain++;//数组范围往中间缩小
        end--;
    }
}
 

代码优化

上述思想是单向的，我们可以让最高的和最矮的同时排序，就可以优化一下，实现双向排序

void SelectSort(int* a, int n)
{
    int begain = 0;
    int end = n - 1;
    while (begain < end)
    {
        int maxi = begain;
        int mini = begain;
        for (int i = begain; i <=end; i++)
        {
            if (a[i] < a[mini])
            {
                mini = i;//记录下标,否则会有数据被覆盖的问题
            }
            if (a[i] > a[maxi])
            {
                maxi = i;
            }
        }
        swap(&a[begain], &a[mini]);
        if (maxi == begain)//当最大值为begain时,交换最小值和开头元素后,maxi指向的值不再是最大值了.
        {
            maxi = mini;
        }
        swap(&a[end], &a[maxi]);
        begain++;
        end--;
    }
}
 

特性总结

1. 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)
4. 稳定性：不稳定