孝感织云网站建设,哈尔滨网站建设方案,网站开发资费,wordpress和hexo八大排序详解 目录#xff1a;一、排序的概念1.1 排序的概念1.2 排序的应用 二、直接插入排序三、希尔排序四、排序算法复杂度及稳定性分析 目录#xff1a;
八大排序算法#xff1a; #mermaid-svg-7qCaGEYz0Jyj9dYw {font-family:trebuchet ms,verdana,arial,… 八大排序详解 目录一、排序的概念1.1 排序的概念1.2 排序的应用 二、直接插入排序三、希尔排序四、排序算法复杂度及稳定性分析 目录
八大排序算法 #mermaid-svg-7qCaGEYz0Jyj9dYw {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-7qCaGEYz0Jyj9dYw .error-icon{fill:#552222;}#mermaid-svg-7qCaGEYz0Jyj9dYw .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-7qCaGEYz0Jyj9dYw .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-7qCaGEYz0Jyj9dYw .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-7qCaGEYz0Jyj9dYw .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-7qCaGEYz0Jyj9dYw .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-7qCaGEYz0Jyj9dYw .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-7qCaGEYz0Jyj9dYw .marker{fill:#333333;stroke:#333333;}#mermaid-svg-7qCaGEYz0Jyj9dYw .marker.cross{stroke:#333333;}#mermaid-svg-7qCaGEYz0Jyj9dYw svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-7qCaGEYz0Jyj9dYw .label{font-family:"trebuchet ms",verdana,arial,sans-serif;color:#333;}#mermaid-svg-7qCaGEYz0Jyj9dYw .cluster-label text{fill:#333;}#mermaid-svg-7qCaGEYz0Jyj9dYw .cluster-label span{color:#333;}#mermaid-svg-7qCaGEYz0Jyj9dYw .label text,#mermaid-svg-7qCaGEYz0Jyj9dYw span{fill:#333;color:#333;}#mermaid-svg-7qCaGEYz0Jyj9dYw .node rect,#mermaid-svg-7qCaGEYz0Jyj9dYw .node circle,#mermaid-svg-7qCaGEYz0Jyj9dYw .node ellipse,#mermaid-svg-7qCaGEYz0Jyj9dYw .node polygon,#mermaid-svg-7qCaGEYz0Jyj9dYw .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-7qCaGEYz0Jyj9dYw .node .label{text-align:center;}#mermaid-svg-7qCaGEYz0Jyj9dYw .node.clickable{cursor:pointer;}#mermaid-svg-7qCaGEYz0Jyj9dYw .arrowheadPath{fill:#333333;}#mermaid-svg-7qCaGEYz0Jyj9dYw .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-7qCaGEYz0Jyj9dYw .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-7qCaGEYz0Jyj9dYw .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-7qCaGEYz0Jyj9dYw .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-7qCaGEYz0Jyj9dYw .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-7qCaGEYz0Jyj9dYw .cluster text{fill:#333;}#mermaid-svg-7qCaGEYz0Jyj9dYw .cluster span{color:#333;}#mermaid-svg-7qCaGEYz0Jyj9dYw div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-7qCaGEYz0Jyj9dYw :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;} 八大排序算法 插入排序 选择排序 交换排序 归并排序 非比较排序 直接插入排序 希尔排序 选择排序 堆排序 冒泡排序 快速排序 归并排序 计数排序 超链接 插入排序 选择排序 交换排序 归并排序 非比较排序
一、排序的概念
1.1 排序的概念
排序:所谓排序就是使一串记录 按照其中的某个或某些关键字的大小递增或递减的排列起来的操作。稳定性:假定在待排序的记录序列中存在多个具有相同的关键字的记录若经过排序这些记录的相对次序保持不变即在原序列中r[i]r[j] 且r[i]在r[j]之前而在排序后的序列中r[i]仍在r[j]之前则称这种排序算法是稳定的;否则称为不稳定的。 内部排序:数据元素全部放在内存中的排序。 外部排序:数据元素太多不能同时放在内存中根据排序过程的要求不能在内外存之间移动数据的排序。
1.2 排序的应用
排序的目的通常是为了方便查找或者统计最多或者最少的重复次数。 1.游戏竞赛。 游戏规则是随机一组30张图片要求参加比赛的10人在30秒之内把图片按照从小到大顺序排序时间最少的获胜。 2.调查问卷。 在110000中随机生成N个数对于重复的数只保留一个不同的数对应着不同学生的学号再把这些数从小到大排序按顺序找同学调查。 3.颁发特等奖学金。 某个大学有n名学生每个人都有m门课按照综合成绩排名需要挑出最优秀的k位学生颁发特等奖学金。
二、直接插入排序
直接插入排序的基本思想 把待排序的内容记录并逐一与排序好的有序序列比较插入到有序序列中直到待排序列的记录全部插入完毕得到一个新的有序序列这就是直接插入排序 代码如下
#define _CRT_SECURE_NO_WARNINGS 1
#include stdio.h
#include time.h
#include windows.h
#define m 1000
void IsertSort(int* arr, int n)
{int i;for (i 1; i n; i)//i为待排序的第一个数下标{int end i - 1;//end 为已排好序列的尾下标int tmp arr[i];//把待排序的第一个数存起来//遍历已排序列进行比较然后插入这里我进行从小到大排序while (end 0){if (arr[end] tmp)//如果前面的数大就把他往后移动一个{arr[end 1] arr[end];end--;}//否则就跳出elsebreak;arr[end 1] tmp;}}//打印排序后的数据for (i 0; i n; i){printf(%d , arr[i]);}
}
int main()
{int head, end,arr[m];//srand(初始化时间)time(直接返回时间戳)srand((unsigned)time(NULL));head clock();for (int i 0; i m; i)arr[i] rand();//时间不停的变化每次产生不同的随机值IsertSort(arr,sizeof(arr)/sizeof(arr[0]));end clock();//排序需要花费的时间printf(\n%d\n , end - head);return 0;
}直接插入排序的性能总结 1.元素集合越接近有序直接插入排序算法的时间效率越高。 2.时间复杂度O(N^2) 3.空间复杂度为O(1),它是一种稳定的排序算法 4.稳定性:稳定
三、希尔排序
希尔排序又叫缩小增量法。 希尔排序的基本思想 先选定一个整数然后把待排序的记录分成这个整数的组所有距离为这个整数的记录被分在同一个组并对每一个组内的记录进行排序。先预排序然后在插入排序。 代码如下
#define _CRT_SECURE_NO_WARNINGS 1
#include stdio.h
#include time.h
#include stdlib.h
#include Windows.h
#define m 10000
SheelSort(int* arr, int n)
{int gap 3;//多趟for(int j0;jgap; j)//每组进行插入排序for (int i j; i n - gap; i gap){//单趟int end i;int tmp arr[end gap];while (end 0){if (arr[end] tmp)//从大到小排序{arr[end gap] arr[end];end - gap;}elsebreak; }arr[end gap] tmp;}
}
int main()
{int head, tail, i;int arr[m] {0};srand((unsigned)time(NULL));for (i 0; i m; i)arr[i] rand()%1000;head clock();SheelSort(arr, sizeof(arr) / sizeof(arr[0]));tail clock();printf(%d , tail - head);return 0;
}效率如下 我们可以优化一下(减少一个循环但是效率还是差不多得而且代码更简洁)
#define _CRT_SECURE_NO_WARNINGS 1
#include stdio.h
#include time.h
#include stdlib.h
#include Windows.h
#define m 10000
SheelSort_1(int* arr, int n)
{int gap 3;//按顺序一组一组排序for (int i 0; i n - gap; i ){//单趟int end i;int tmp arr[end gap];while (end 0){if (arr[end] tmp)//从大到小排序{arr[end gap] arr[end];end - gap;}elsebreak;}arr[end gap] tmp;}
}
int main()
{int head, tail, i;int arr[m] {0};srand((unsigned)time(NULL));for (i 0; i m; i)arr[i] rand()%1000;head clock();SheelSort_1(arr, sizeof(arr) / sizeof(arr[0]));tail clock();printf(%d , tail - head);return 0;
}我们可以得知预排序的意义 1.gap越大大的数可以更快的到后面小的数可以更快到前面gap越大跳的越快越不接近有序。 2.gap越小大的小的数挪动越慢越接近有序。 3.gap 1就是直接插入排序。 但是我们不知道gap取什么值最好 我们在把代码变一变让gap无论是多少最后都等于gap 1.gap 1为预排序
#define _CRT_SECURE_NO_WARNINGS 1
#include stdio.h
#include time.h
#include stdlib.h
#include Windows.h
#define m 10000
SheelSort_3(int* arr, int n)
{int gap n;while(gap 1)//先预排序预排序结束后直接插入排序{gapgap/31;//gapgap/2;//按顺序一组一组排序for (int i 0; i n - gap; i ){//单趟int end i;int tmp arr[end gap];while (end 0){if (arr[end] tmp)//从大到小排序{arr[end gap] arr[end];end - gap;}elsebreak;}arr[end gap] tmp;}}
}
int main()
{int head, tail, i;int arr[m] {0};srand((unsigned)time(NULL));for (i 0; i m; i)arr[i] rand()%1000;head clock();SheelSort_3(arr, sizeof(arr) / sizeof(arr[0]));tail clock();printf(%d , tail - head);return 0;
}计算它的时间复杂度 1.gap很大时gapn / 31,可分为n/3组数据每组3个元素每组最坏的比较次数为3次所以一共n / 3 * 3次。 2.gap很小时gap1每组1个元素很接近有序间距为gap的这些数据数据往后挪动的次数n。 3.gap很大时n / 9个组9个元素每组最坏比较36次。12……8间距为gap的这些数据。合计挪动数据n / 9* 364n次 4.外面那个循环运算了log3^N次 总结合计n / gap组每组gap个每组插入123……gap。合计1gap) * gap / 2 时间复杂度O(N^1.3)最好情况 稳定性不稳定
四、排序算法复杂度及稳定性分析
如图 表格
