网站搭建北京,做网站要注意什么,请人做网站交易平台,网站排名不可有利就前排序目录 1.前言2. 排序的概念及其运用2.1 排序的概念2.2 排序的运用2.3 常见的排序算法 3. 插入排序3.1 基本思想3.2 直接插入排序3.2.1 直接插入排序实现3.2.1.1 分析3.2.1.2 代码实现 3.3 希尔排序3.3.1 希尔排序实现3.3.1.1 分析3.3.1.2 代码实现 4. 附代码4.1 sort.h4.2 s… 排序目录 1.前言2. 排序的概念及其运用2.1 排序的概念2.2 排序的运用2.3 常见的排序算法 3. 插入排序3.1 基本思想3.2 直接插入排序3.2.1 直接插入排序实现3.2.1.1 分析3.2.1.2 代码实现 3.3 希尔排序3.3.1 希尔排序实现3.3.1.1 分析3.3.1.2 代码实现 4. 附代码4.1 sort.h4.2 sort.c4.3 test.c 1.前言
在生活中处处可见排序当我们打开京东或者其它购物平台时搜索物品它会有一定的排序。 这次就来分享的博客与排序有关。 正文开始。
2. 排序的概念及其运用
2.1 排序的概念 排序所谓排序就是使一串记录按照其中的某个或某些关键字的大小递增或递减的排列起来的操作。 稳定性假定在待排序的记录序列中存在多个具有相同的关键字的记录若经过排序这些记录的相对次序保持不变即在原序列中r[i]r[j]且r[i]在r[j]之前而在排序后的序列中r[i]仍在r[j]之前则称这种排序算法是稳定的否则称为不稳定的。
内部排序数据元素全部放在内存中的排序。 外部排序数据元素太多不能同时放在内存中根据排序过程的要求不能在内外存之间移动数据的排序。
2.2 排序的运用
举个例子 在京东上平板的统合排名 来看看高校的排名 可能每个人搜出来的不一样。
2.3 常见的排序算法 3. 插入排序
3.1 基本思想
直接插入排序是一种简单的插入排序法其基本思想是把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中直到所有的记录插入完为止得到一个新的有序序列 。 就像是在玩扑克牌时候对刚拿的牌来进行一个插入。
3.2 直接插入排序
当插入第i(i1)个元素时前面的array[0],array[1],…,array[i-1]已经排好序此时用array[i]的排序码与array[i-1],array[i-2],…的排序码顺序进行比较找到插入位置即将array[i]插入原来位置上的元素顺序后移。
直接看动图 直接插入排序的特性总结
元素集合越接近有序直接插入排序算法的时间效率越高时间复杂度O(N^2)空间复杂度O(1)它是一种稳定的排序算法稳定性稳定
3.2.1 直接插入排序实现
以升序为例子
3.2.1.1 分析
就是把没排好的数插入到已经排好的数中实现有序。 实现排序先实现单趟。 假设在一个已经排好序的区间[0,end]然后把end1位置的值插入进去那怎么插入呢 从后往前依次比较如果比end1大那就往后挪把位置空出来再把值放进去。为了记录插入的数据用一个临时变量tmp存储 end1的值避免被覆盖。 假设前面的已经[0,end]也就是349已经排好。这时要插入6先记录一下tmp6然后依次往前比较如果比tmp大那就往后挪。 还有一种情况 一直往走往后挪数据当end0时结束。 所以这里循环的条件就是while (end 0。 如果tmp a[end],就实现a[end 1] a[end]然后end1--。 循环结束就有两种情况一种是tmpend,tmp就得放在end后面。另一种是在while条件结束出现end0。 单趟的已经实现那怎么实现整体 在while循环外面再套一层循环。 第一个数据就是[0,0],再往下是[0,1],2位置的往前插入。那么它的结束位置就是n-1不能是n因为如果到n,那么tmp位置访问n1,已经越界了。
3.2.1.2 代码实现
void InsertSort(int* a, int n)
{// [0, end] end1for (int i 0; i n - 1; i){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;}
}来看看结果
3.3 希尔排序
希尔排序法又称缩小增量法。希尔排序法的基本思想是先选定一个整数把待排序文件中所有记录分成个组所有距离为的记录分在同一组内并对每一组内的记录进行排序。然后取重复上述分组和排序的工作。当到达1时所有记录在统一组内排好序。 希尔排序的特性总结
希尔排序是对直接插入排序的优化。当gap 1时都是预排序目的是让数组更接近于有序。当gap 1时数组已经接近有序的了这样就会很快。这样整体而言可以达到优化的效果。我们实现后可以进行性能测试的对比。希尔排序的时间复杂度不好计算因为gap的取值方法很多导致很难去计算因此在好些书中给出的希尔排序的时间复杂度都不固定稳定性不稳定
3.3.1 希尔排序实现
希尔排序分为两部分第一部分是预排序第二部分是直接插入排序。
3.3.1.1 分析
预排序的目的是让数组基本有序这样直接插入就很快。 举个例子gap3 将间隔为3的分为一组那么总的就分为了三组。红的一组蓝的一组绿的一组。 那么它的预排序怎么实现呢 就是将分的这三组分别进行插入排序。 首先将9当成已经排好的数据那么下一个不是8而是间隔为3的6,把6往前插入然后继续找下一个就是4继续往前面插入。 最后就是这样; 剩下的两组也是一样的最终排出来就是 这里只是接近有序。
就是把上面的直接插入排序的tmp换成end gap位置的就行。 假设先对红色这组经行排序那就是 注意循环的条件如果是in那么就会访问越界注意看图上发现结束的位置就是n-gap。 如果排实现的两组那么就直接再套一层循环gap3次就排完了。 这里套了三层排序也只是预排序j为0就是红色的一组j为1就是蓝色那组j为2就是绿色那一组。 优化一下实现多组并排之间是一组一组往后排现在是直接在gap组之间来回跳第一次排红色第二次排蓝色第三次排绿色。 少一层循环。 gap怎么选择 《数据结构(C语言版)》— 严蔚敏 《数据结构-用面相对象方法与C描述》— 殷人昆 所以这里实现希尔排序就是将gap不断变小, gap 1时是预排序目的让他接近有序,而gap 1是直接插入排序目的是让他有序。 那么这里gap怎么选择呢 如果gap gap / 2这里跳跃就比较小所以选择gap gap / 3 但为了保证最后一次为1这里就得加1也就是gap gap / 3 1。 来看看结果
3.3.1.2 代码实现
void ShellSort(int* a, int n)
{int gap n;// gap 1时是预排序目的让他接近有序// gap 1是直接插入排序目的是让他有序while (gap 1){//gap gap / 2;gap gap / 3 1;for (int 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;}}
}4. 附代码
4.1 sort.h
#pragma once
#includestdio.h
#includeassert.h
#includestdlib.h
#includestdbool.h
#includetime.hvoid PrintArray(int* a, int n);
void InsertSort(int* a, int n);
void ShellSort(int* a, int n);4.2 sort.c
#includeSort.hvoid PrintArray(int* a, int n)
{for (int i 0; i n; i){printf(%d , a[i]);}printf(\n);
}// 时间复杂度O(N^2) 逆序
// 最好的情况O(N) 顺序有序
void InsertSort(int* a, int n)
{// [0, end] end1for (int i 0; i n - 1; i){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;// gap 1时是预排序目的让他接近有序// gap 1是直接插入排序目的是让他有序while (gap 1){//gap gap / 2;gap gap / 3 1;for (int 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;}}/*for (int j 0; j gap; j){for (int i j; i n-gap; i gap){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;}}*/
}4.3 test.c
#includeSort.hvoid TestInsertSort()
{int a[] { 3, 2, 6, 8, 4, 6, 0, 9, 5, 7, 1 };InsertSort(a, sizeof(a) / sizeof(int));PrintArray(a, sizeof(a) / sizeof(int));
}void TestShellSort()
{int a[] { 3, 2, 6, 8, 4, 6, 0, 9, 5, 7, 1 };ShellSort(a, sizeof(a) / sizeof(int));PrintArray(a, sizeof(a) / sizeof(int));
}
int main()
{TestInsertSort(); TestShellSort();return 0;
}在之后的博客中会继续分享与排序有关的内容请多多关注。 有问题请指出大家一起进步
