数据结构：常见排序算法详解

一、排序概念及运用

排序在数据结构中是非常重要的一部分，所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。

在生活中也有很多的应用，比如当我们搜索一款产品时，我们可以选择按销量多少的顺序来给我们推荐产品，也可以按照价格高低来给我们推荐产品，所以排序在生活中也是很常见的。

1.1 插入排序

（1）直接插入排序

插入排序又分为直接插入排序和希尔排序。直接插入排序是比较好理解的，比如我们日常生活中的扑克牌游戏，当我们拿到牌的时候我们会习惯性的直接将牌按我们想要的顺序排列。

那么希尔排序又是怎么回事呢？我用一张清晰的思路图来向大家展示：

void InitSort(int* arr, int n) {
    for (int i = 0; i < n - 1; i++) {
        int end = i;
        int tmp = arr[end + 1];
        while (end >= 0) {
            if (arr[end] > tmp) {
                arr[end + 1] = arr[end];
                end--;
            } else {
                break;
            }
        }
        arr[end + 1] = tmp;
    }
}