手把手教你排序算法怎么写

手把手教你排序算法怎么写

本文将通过一个具体的例子，手把手教你如何实现插入排序算法。从算法介绍到代码实现，再到错误排查和代码修正，一步步引导你理解插入排序的实现过程。

在添加新的记录时，使用顺序查找的方式找到其要插入的位置，然后将新记录插入。
以{3,0,9,8,2}无序表按升序排列为例,有序表是一个虚拟的顺序表：

1. 插入排序刚开始，有序表中没有数据，因此直接插入3即可。{3}
2. 插入0的时候要和有序表中记录3进行比较，0 <3,插入到3的左侧。{0,3}
3. 插入9的时候，要和有序表中的记录3进行比较，9 > 3 插入到3的右侧{0,3,9}
4. 插入8的时候，要和有序表中的9进行比较，9 > 8 8>3因此添加到 9和3之间{0,3,8,9}
5. 插入2的时候，要和有序表中的 9 8 3 0依次比较，确定2位于0和3之间{0,2,3,8,9}

分析：1、先写框架2、实现排序逻辑3、验证调整代码

2.1 先写框架-我的预期

这是一段整理思路的过程。

int a[] = {3,0,9,8,2};
int size = sizeof(a) / sizeof(int);
int i;
for(i=0;i<size;i++)
{
    printf("%d ",a[i]);
}
printf("\n");
// 传递整型数据和长度进去，对数据进行排序
insertSort(a,size);
for(i=0;i<size;i++)
{
    printf("%d ",a[i]);
}

预期效果：

// 3 0 9 8 2
// 0 2 3 8 9

2.2 函数声明

函数三要素：

• insertSort函数功能：实现对传入数组的排序
• 形参：数组，数组长度
• 返回值：直接在原有数组中进行排序即可，无需返回值。

先写函数声明

void insertSort(int a[],int size)
{
    //......
}

2.3 实现排序逻辑

1. 寻找突破口
   按照直接插入排序的规则，需要对下标为1以后的每一个数据进行插入排序，先获取到下标为1之后的每一个数据。

void insertSort(int a[],int size)
{
    int i;
    int j;
    for(i=1;i<size;i++)
    {
        // a[i] 从下标为1开始，每循环一次向后获取到一个数据。
    }
}

2. 寻找排序规律
   // 使用当前a[i]值和i下标前面的每一个数值进行比较
   // 如果 a[i-1] > a[i] a[i] = a[i-1] -- a[i]这个数据空间值可能被覆盖掉，
   // 下面可能还要多次使用到该数据，
   // 因此可以将这个数据保存下来。
   // 继续如果 a[i-2] > a[i] a[i-1] = a[i-2]
   //.....
   // 如果 a[i-j] < a[i] a[i-j+1] = a[i] --结束本次比较 ，a[i]已经找到它所在的位置了

// 考虑边界
// i-j最小值为0，下标不能越界

3. 伪代码描述
   先将a[i]的值存起来到变量val里面
   开始循环比较 j,1<=j<=i(满足i-j最小值为0),每次增加1，保证下标连续
   比较a[i-j]和val的值
   如果a[i-j] > val,a[i-j]需要向后移动，即a[i-j-1] = a[i-j]
   如果a[i-j] <= val;val可以直接放在a[i-j+1]的位置，即a[i-j-1] = val;
   结束本次循环，进入下一个数的插入排序。

4. 代码实现

void insertSort(int a[],int size)
{
    int i;
    int j;
    for(i=1;i<size;i++)
    {
        int val = a[i];
        for(j=1;j<=i;j++)
        {
            if(a[i-j] <= val)
            {
                // 找到val坐在的位置了
                a[i-j+1] = val;
                break;
            }
            else
            {
                a[i-j+1] = a[i-j];
            }
        }
    }
}

5. 验证代码
   出错：没有达到预期，即逻辑存在缺陷

6. 排查错误

排查错误的时候，可以将比较的次数和每次比较后数组中的结果打印出来，进行排查。
因为数组打印要遍历，为了不影响其他循环变量的值，可以在声明一个变量。
从结果上看，第一次的0没有插入成功，按照逻辑走一遍，发现i=1,j=1,0<3因此3向后移动一步，然后j=2,循环结束了。
也就是意味着，如果当前这个数是数组中的最小的数，应该放在下标为0的这一步操作没有做。

7. 修正代码

void insertSort(int a[],int size)
{
    int i;
    int j;
    for(i=1;i<size;i++)
    {
        int val = a[i];
        for(j=1;j<=i;j++)
        {
            if(a[i-j] <= val)
            {
                // 找到val坐在的位置了
                a[i-j+1] = val;
                break;
            }
            else
            {
                a[i-j+1] = a[i-j];
                // 如果当前a[i]是这个数组中最小的元素，
                // 交换位置后，只剩下0下标的位置了,需要将数据插入到0的位置上。
                if(i-j == 0)
                {
                    a[i-j] = val;
                }
            }
        }
    }
}

本篇内容旨在帮助初学者整理写算法代码思路。