数据结构排序算法详解（1）——介绍及插入排序（附动图）

星轨初途

发布于 2026-01-09 14:39:40

1420

文章被收录于专栏：星轨初途星轨初途

个人主页：星轨初途个人专栏：C语言，数据结构

前言

嗨ヾ(@▽@)ノ，今天我们就来到了排序相关的知识点啦，排序不管是数据结构还是算法都是极其重要的，内容也是相当多的，今天我们来初步了解排序吧！

一、排序的概念及应用

1、概念

排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。

2、应用

比如商品排序筛选，我们在买东西时通常通过销量，价格等等来确定合适的商品如下图：就是电脑显示屏

再如编程语言的排名

这些都体现了排序的应用

二、常见的排序算法

常见的排序算法类型如图：

我们接下来会依次讲解每一种排序，并在最后比较每种排序函数的性能

三、插入排序

在介绍之前我们先写一个打印函数，因为后续验证要反复用打印数组元素

#include<stdio.h>
#include<string.h>
void PrintArray(int* a, int n)
{
    for (int i = 0; i < n; i++)
    {
        printf("%d ", a[i]);
    }
    printf("\n");
}

1、直接插入排序

（1）概念及实现

直接插入排序是一种简单的插入排序法，其基本思想是：把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列。比如我们平常玩扑克牌时，就用到了插入排序的思想

我们也可以通过下面这个动图来更清晰的看出来

是不是更加清晰啦，下面我们通过代码来实现（我们这里升序实现，代码中注释了改变为降序要改动的地方）

void InsertSort(int* a, int n)
 {
 	//  [0, n-1]
 	for (int i = 0; i < n - 1; i++)
 	{
 		// [0, n-2]是最后一组
 		// [0,end]有序 end+1位置的值插入[0,end]，保持有序
 		int end = i;
 		int tmp = a[end + 1];
 		while (end >= 0)
 		{
 		//升序大于>,降序小于
 			if (tmp <= a[end])
 			{
 				a[end + 1] = a[end];
 				--end;
 			}
 			else
 			{
 				break;
 			}
 		}
 		a[end + 1] = tmp;
 	}
 }

就是将第一个数当成有序，再插入第二个数，先进行保存第2个数，比较与前一个数的大小，前一个数据大，把前一个数据向后移动一个，end–,再比较前一个，否则退出循环将空出来的那个地方给它插入我们来测试一下

#include<stdio.h>
#include<string.h>
void InsertSort(int* a, int n)
{
    //  [0, n-1]
    for (int i = 0; i < n - 1; i++)
    {
        // [0, n-2]是最后一组
        // [0,end]有序 end+1位置的值插入[0,end]，保持有序
        int end = i;
        int tmp = a[end + 1];
        while (end >= 0)
        {
            //升序大于>,降序小于
            if (tmp < a[end])
            {
                a[end + 1] = a[end];
                --end;
            }
            else
            {
                break;
            }
        }
        a[end + 1] = tmp;
    }
}
void PrintArray(int* a, int n)
{
    for (int i = 0; i < n; i++)
    {
        printf("%d ", a[i]);
    }
    printf("\n");
}
int main()
{
    int arr[] = { 2,5,3,76,9,10,32,11,2 };
    PrintArray(arr, sizeof(arr) / sizeof(int));//排序前
    InsertSort(arr, sizeof(arr) / sizeof(int));
    PrintArray(arr, sizeof(arr) / sizeof(int));//排序后
    return 0;
}

结果，第一行是排序前，第二行是排序后，升序，符合要求

（2）时间复杂度

O(n2)

（3）特性

我们通过上面的分析可以看出直接插入排序的特性

1、元素集合越接近有序，直接插入排序算法的时间效率越高； 2、时间复杂度：O(N2) ； 3、空间复杂度：O(1)。

虽然有时间复杂度为O(n)的情况，但触发概率太小时间复杂度为O(n2)太大了，很容易超时，我们怎么来优化它呢？这时轮到我们希尔排序登场啦

2、希尔排序

(1)概念及实现

希尔排序法又称缩小增量法，是一种改进的插入排序希尔排序法的基本思想是：先选定一个整数gap（通常是gap=(n/3+1），把待排序文件中所有记录分成gap组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工作。当到达gap=1时，所有记录在统一组内排好序。原理：

分组预排序（核心优化）
- 先设定一个间隔（gap），把数组按此间隔分成若干组（如gap=5时，下标0、5、10…为一组，1、6、11…为另一组），对每组分别进行插入排序。
- 目的：让数组中“远距离”的元素先移动到大致正确的位置，减少后续插入排序的工作量。
逐步缩小间隔
- 不断减小gap（如gap=5→2→1）（通常是gap=gap/3+1），重复分组排序的过程。
- 特性：gap越大，元素移动步长越大，能快速把乱序的大/小元素“归位”；gap越小，数组越接近有序(这也是通常把设gap=gap/3+1的原因（相对最优点））。
最终插入排序
- 当gap=1时，数组已基本有序，此时执行普通插入排序。因数组接近有序，插入排序效率极高（时间复杂度接近O(n)）。可以通过这个图片理解一下
在这里插入图片描述
动图如下：
请添加图片描述

我们用代码来实现一下

// O(N ^ 1.3)
//希尔排序
void ShellSort(int* a, int n)
{
    int gap = n;
    while (gap > 1)
    {
      
        // gap > 1时是预排序
        // gap == 1时是插入排序
        gap = gap / 3 + 1;// +1保证最后一个gap一定是1

        for (size_t i = 0; i < n - gap; ++i)
        {
            int end = i;
            int tmp = a[end + gap];
            while (end >= 0)
            {
                if (tmp < a[end])
                {
                    a[end + gap] = a[end];
                    end -= gap;
                }
                else
                {
                    break;
                }
            }
            a[end + gap] = tmp;
        }
    }
}

验证

int main()
{
    int arr[] = { 2,5,3,76,9,10,32,11,2 };
    PrintArray(arr, sizeof(arr) / sizeof(int));//排序前
    ShellSort(arr, sizeof(arr) / sizeof(int));
    PrintArray(arr, sizeof(arr) / sizeof(int));//排序后
    return 0;
}

结果，正确

(2）时间复杂度

O(n1.3)

外层循环很好计算（也就是gap变化的循环）由于gap取值不确定，可以取2,3,所以外层为logn 而内层循环就很难计算了，因为当你假设第一次为最坏情况时，第1层为n 但是你无法确定后面为最差，因为已经进行预排序一次但是最后一次gap=1，一定遍历全部所以我们通过分析，可以大概画出这样的曲线图

所以，希尔排序在最初和最后的排序的次数都为n，即前一阶段排序次数是逐渐上升的状态，当到达某一顶点时，排序次数逐渐下降至n。就是因为gap的取值不同和内部循环过程难计算，所以很多书中希尔排序的时间复杂度都不固定在《数据结构(C语言版)》— 严蔚敏，中说过

《数据结构-用面相对象方法与C++描述》— 殷人昆

这里我们把时间复杂度记为O(n1.3)

(3)特性

1、希尔排序是对直接插入排序的优化； 2、当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。

3、希尔排序与直接插入排序对比

光讲希尔排序比直接插入排序的优势可能有些不明显，下面我们通过程序来对比

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include <time.h>
//测试排序的性能对比  
void TestOP()
{
	srand(time(0));
	const int N = 100000;
	int* a1 = (int*)malloc(sizeof(int) * N);
	int* a2 = (int*)malloc(sizeof(int) * N);
	for (int i = 0; i < N; ++i)
	{
		a1[i] = rand()+i;//加i减少重复
		a2[i] = a1[i];
	}
	//begin和end的时间差就是开始到结束时间差
	int begin1 = clock();
	InsertSort(a1, N);
	int end1 = clock();
 
	int begin2 = clock();
	ShellSort(a2, N);
	int end2 = clock();
	
	printf("InsertSort:%d\n", end1 - begin1);
	printf("ShellSort:%d\n", end2 - begin2);
	free(a1);
	free(a2);
}
int main()
{
   /* int arr[] = { 2,5,3,76,9,10,32,11,2 };
    PrintArray(arr, sizeof(arr) / sizeof(int));
    ShellSort(arr, sizeof(arr) / sizeof(int));
    PrintArray(arr, sizeof(arr) / sizeof(int));*/
    TestOP();
    return 0;
}

单位是毫秒（ms），1000 ms = 1s。

我们这里先看10万个随机数，排序对比

运行结果相差50倍

我们再把数据扩大10倍

const int N = 1000000;

可以看出希尔排序运行时间增加的不多，而直接排序直接增加10倍可以看出差距很大，这里我们不用小数据比较，因为小数据比较看不出什么差别现在通过比较我们可以看出用哪个最好了吧！

4、代码总和

Sort.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include <time.h>
//直接插入排序
void InsertSort(int* a, int n);
// O(N ^ 1.3)
//希尔排序
void ShellSort(int* a, int n);
//打印
void PrintArray(int* a, int n);

Sort.c

#include"Sort.h"
//直接插入排序
void InsertSort(int* a, int n)
{
    //  [0, n-1]
    for (int i = 0; i < n - 1; i++)
    {
        // [0, n-2]是最后一组
        // [0,end]有序 end+1位置的值插入[0,end]，保持有序
        int end = i;
        int tmp = a[end + 1];
        while (end >= 0)
        {
            //升序大于>=,降序小于=
            if (tmp <= a[end])
            {
                a[end + 1] = a[end];
                --end;
            }
            else
            {
                break;
            }
        }
        a[end + 1] = tmp;
    }
}
// O(N ^ 1.3)
//希尔排序
void ShellSort(int* a, int n)
{
    int gap = n;
    while (gap > 1)
    {
        // +1保证最后一个gap一定是1
        // gap > 1时是预排序
        // gap == 1时是插入排序
        gap = gap / 3 + 1;

        for (size_t i = 0; i < n - gap; ++i)
        {
            int end = i;
            int tmp = a[end + gap];
            while (end >= 0)
            {
                if (tmp < a[end])
                {
                    a[end + gap] = a[end];
                    end -= gap;
                }
                else
                {
                    break;
                }
            }
            a[end + gap] = tmp;
        }
    }
}
//打印
void PrintArray(int* a, int n)
{
    for (int i = 0; i < n; i++)
    {
        printf("%d ", a[i]);
    }
    printf("\n");
}

test.c

#include"Sort.h"
void TestOP()
{
    srand(time(0));
    const int N = 1000000;
    int* a1 = (int*)malloc(sizeof(int) * N);
    int* a2 = (int*)malloc(sizeof(int) * N);
    for (int i = 0; i < N; ++i)
    {
        a1[i] = rand() + i;
        a2[i] = a1[i];
    }
    //begin和end的时间差就是开始到结束时间差
    int begin1 = clock();
    InsertSort(a1, N);
    int end1 = clock();

    int begin2 = clock();
    ShellSort(a2, N);
    int end2 = clock();

    printf("InsertSort:%d\n", end1 - begin1);
    printf("ShellSort:%d\n", end2 - begin2);
    free(a1);
    free(a2);
}
int main()
{
   /* int arr[] = { 2,5,3,76,9,10,32,11,2 };
    PrintArray(arr, sizeof(arr) / sizeof(int));
    ShellSort(arr, sizeof(arr) / sizeof(int));
    PrintArray(arr, sizeof(arr) / sizeof(int));*/
    TestOP();
    return 0;
}