一. 排序的概念及其运用
1. 排序的概念
所谓排序 就是给你一堆数据 让你按照一个或多个关键字 让这一堆数据递增或者递减
2. 排序的运用
这个就很常见了 就拿我们买东西举例
我们最近想要去买个手机
那么应该怎么选呢？
最多人买的应该没错吧
于是我们想看看 哪个手机买的人最多 这个时候我们只需要点一下按照销量排序 我们就可以拿到我们需要的数据了
3. 常见的排序算法
我这里使用xmind整理了一份思维导图给大家
我们这篇博客主要需要学习的是插入排序和选择排序
二. 直接插入排序
1. 基础概念
插入排序其实就像我们拿到一副扑克牌
我们肯定是习惯将整个一副牌按照从小到大的顺序排好是吧
这个就是插入排序在我们现实生活中的运用
2. 代码表示
（我们这里的所有数据以小序为例）
我们这里先假设插入一个数字
首先插入排序我们是默认前面的数据是有序的
所以说我们插入一个元素需要三个数据才可以完成
第一个当然是指向我们数组的指针
第二个是目前数组内元素的个数 我们用这个来确定最后面的元素是哪个
第三个是我们需要插入的值
我们用它来插入
代码表示如下
// arr表示数组 size是元素的个数 x是插入的值的值 void Insertsort1(int* arr, int size, int x) { // assert assert(arr); // 因为插入排序的要 求是默认前面的有序的 // 所以说我们这里也默认传入的数组是有序的 int end = size - 1; // x就是我们要插入的值 while (end >= 0) { // 比较大小 if (arr[end] > x) { // end往后挪挪 腾位置 arr[end + 1] = arr[end]; end--; } else { break; } } // 这里画图注意下end的位置 arr[end + 1] = x; }
我们来写一段代码测试下 这个插入排序到底对不对
我们可以发现 这段代码没有问题
之后我们开始写整体的数组排序
这个时候我们只需要进行两次循环
（第一次循环将最前面一个元素当成是一个有序数组
第二次循环将最前面两个元素当成是一个有序数组
… … …）
代码表示如下
void Insertsort(int* arr, int size) { // assert assert(arr); // 我们当这个数组是一个数的有序数组 // 依次进行插入排序 直到最后 int end = 0; int x = arr[end + 1]; // 两层循环 一层控制end的大小 一层控制插入排序 这里开始操作 int i = 0; for ( i = 0; i < size-1; i++) { // 这里赋值end进行迭代 end = i; x = arr[end + 1]; // 注意这里的边界条件 while (end>=0) { // 这里进行进行单个的插入排序 if (arr[end] > x) { arr[end + 1] = arr[end]; end--; } else { break; } } // 还是一样 画图注意end这个时候在哪里 数组是一个什么样子的 arr[end + 1] = x; } }
我们来看看最后结果是什么样子的
可以完美运行
三. 希尔排序（shellsort）
1. 基础概念
在了解希尔排序之前我们先了解下直接插入排序的时间复杂度
在完全有序时 直接插入排序的时间复杂度最高 此时为 O(N^2)
在完全有序时 直接插入排序的时间复杂度最低 此时为 O（N）
所以说 只要让我们要排序的数字尽量有序 就能很大程度上降低时间复杂度
我们将这一步称为 预排序
2. 预排序
这里我们要引入一个 gap变量 我们将之称为间隔
从零起始位置开始 我们利用它们之间的间隔作为依据
建立N个不同的数组
并且这个时候我们将这个数组进行插入排序
之后我们不断缩小间隔 继续进行预排序
最后当gap等于1的时候再进行一次插入排序
3. 希尔排序代码
void Shellsort(int* arr, int size) { // assert assert(arr); // set gap int gap = size; // 这个时候我们就要利用到间隔 来进行快排 // 当gap=1的时候就进行插入排序了 while (gap > 1) { // 这个时候我们开始进行预排序 gap = gap / 2; int end = 0; int x = arr[end + gap]; // gap = gap / 3 + 1; 这样子也可以 int i = 0; for ( i = 0; i < size-gap; i++) { end = i; x = arr[end + gap]; while (end>=0) { if (arr[end] > x) { arr[end + gap] = arr[end]; end -= gap; } else { break; } } // 注意end位置 arr[end + gap] = x; } } }
整体代码表示如上
以上就是本篇博客的全部内容啦 由于博主才疏学浅 所以难免会出现纰漏 希望大佬们看到错误之后能够
不吝赐教 在评论区或者私信指正 博主一定及时修正
那么大家下期再见咯
