直接插入排序#

算法思路#

将第一个记录看成有序的子序列
从第二个记录起逐个进行插入，从而得到一个新的有序子序列，直到整个数列有序

设计思维#

因为正序和倒序只有比较方式不同，其他操作均相同，所以可以加入一个mode参数表示升序还是降序
当找到插入位置时，需要把插入位置后面的元素全部向后移动，再插入相应位置
当没找到插入位置时，要把全部元素向后移动，再插入第一位

算法实现#

1
// 判断
2
int sort_judgeWithMode(int* arr, int i, int j, int mode)
3
{
4
    return mode? arr[j]<arr[i]:arr[j]>arr[i];
5
}
6

7
// 直接插入排序
8
/*
9
mode: 非0：升序， 0：降序
10
*/
11
void sort_straightInsertionSort(int* arr, int len, int mode)
12
{
13
    int tmp;
14
    for(int i = 1; i < len; i ++)
15
    {
16
        for(int j = i-1; j >= -1; j --)
17
        {
18
            /*
19
            如果有匹配成功的数，插入即可
20
            如果没有匹配成功的数，那这个数就需要插入在最前面，此时j=-1
21
            并且插入方法与匹配成功一致
22
            */
23
            if(j == -1 || sort_judgeWithMode(arr, i, j, mode))
24
            {
25
                tmp = arr[i];
26
                // 移动需要移动的元素
27
                for(int k = i; k > j; k--)
28
                {
29
                    arr[k] = arr[k-1];
30
                }
31
                arr[j+1] = tmp;
32
                break;
33
            }
34
        }
35
    }
36
}

运行结果#

测试代码

1
#define N 10
2

3
int main()
4
{
5
    int arr[N] = {1,3,543,234,65,23,4,23,234,87};
6

7
    printf("\n降序排列结果:");
8
    sort_straightInsertionSort(arr, N, 0);
9
    for(int i = 0; i < N; i ++) printf("%3d ", arr[i]);
10

11
    printf("\n\n升序排列结果:");
12
    sort_straightInsertionSort(arr, N, 1);
13
    for(int i = 0; i < N; i ++) printf("%3d ", arr[i]);
14

15
    return 0;
16
}

运行结果

原文链接：CSDN