唐山网站建设选汉狮,如何新建自己的网站,网站备案年限,做电商网站用什么系统本节目标#xff1a;
1.排序的概念及其运用 2.常见排序算法的实现 3.排序算法复杂度及稳定性分析
1.排序的概念及其应用
1.1排序的概念
排序就是按照某个我们设定的关键字#xff0c;或者关键词#xff0c;递增或者递减#xff0c;完成这样的操作就是排序。
1.2排…本节目标
1.排序的概念及其运用 2.常见排序算法的实现 3.排序算法复杂度及稳定性分析
1.排序的概念及其应用
1.1排序的概念
排序就是按照某个我们设定的关键字或者关键词递增或者递减完成这样的操作就是排序。
1.2排序的应用
排序在日常生活中很常见的想前几天刚出的软科高校排名就用到了排序的思想关键词就是软科按照递增的顺序排列。如下图所示 以及我们上淘宝的时候也会用到排序的思想我们想买个手机筛选条件按照个人选择不同给出的答案不同用的人注重品牌有的人注重价格有的女孩更注重像素如下图所示 1.3常见的排序算法 2.常见的排序算法实现
2.1插入排序
2.1.1基本思想
其实插入排序的思想几乎我们每个人都会插入排序就像我们打的扑克从未知的一副牌中我们开始往手里揭牌拿起第一张放在手中再次拿起一张牌的时候就要和手里的牌对比如果比手里的牌大就往后排如果比手里的牌小的话就排在这张牌之前以此类推。一副牌拿完之后我们手里的牌也就按照递增的顺序排好了。 2.1.2直接插入排序 当插入第i(i1)个元素时前面的array[0],array[1],…,array[i-1]已经排好序此时用array[i]的排序码与array[i-1],array[i-2],…的排序码顺序进行比较找到插入位置即将array[i]插入原来位置上的元素顺序后移。图解如下
当插入的数比前一个数字还大时 当插入的数字比数组中所有的数都要小的时候 动态图解如下 插入排序代码实现
void InsertSort(int* a, int n)
{//遍历数组中所有元素for (int i 1; i n; i){//单趟排序int end i - 1;int temp a[i];//temp存储的是元素数值while (end 0)//一直比较到 数组第一个元素完成{if (temp a[end]){a[end 1] a[end];--end;}else // 包含两种情况一种temp比所有元素都大另一种temp比所有元素都小{break;}}a[end 1] temp;}
} 结果对比
在主程序中我们调用插入排序函数并查看最终是否实现 有序排序。
void TestInsertSort()
{int a[] { 3,5,1,6,2,3,7,9,0,8 };PrintArray(a, sizeof(a) / sizeof(int));InsertSort(a, sizeof(a) / sizeof(int));PrintArray(a, sizeof(a) / sizeof(int));
}int main()
{TestInsertSort();return 0;
} 分析总结
直接插入排序时间复杂度最坏情况下逆序有序每个元素都要一个个比较最终形成等差数列 1 2 3 ........N 时间复杂度为 ON^2 最好的情况下有序1 1 1 .......1时间复杂度为ON 总结来看 对于插入排序元素集合越接近有序算法时间效率越高。
2.1.3希尔排序缩小增量排序 希尔排序也是插入排序的一种它又称缩小增量排序法他其实是在插入排序上的一种优化通过上面的分析我们知道插入排序时间复杂度最好的情况也就是接近有序的时候他的时间复杂度为 ON最坏的情况下 无序的时候 为 ON^2。如果我们能先让数组接近有序之后在对他进行排序会大大减小算法时间复杂度。所以希尔大佬就研究出了希尔排序。
它的实现主要通过两步骤第一步预排序让数组接近有序第二步插入排序。
分组预排 将无序的数组按照间隙gap进行分组将数组分成n/gap组然后分组进行插入排序因为有了gap所以时间复杂度会减小如下图所示 分组直接插入排序 gap为3排序实现结果 当gap依次减小数组慢慢接近有序最后gap为1时候数组已经近似有序再插入排序依次数组就会实现有序的同时算法时间复杂度最低。
代码实现
void ShellSort(int* a, int n)
{int gap 3;for (int j 0; j gap; j){for (int i j; i n- gap; i gap){//单趟排序int end i;int temp a[i gap];//temp存储的是元素数值 i gap 要在数组之内 不可以越界while (end 0)//一直比较到 数组第一个元素完成{if (temp a[end]){a[end gap] a[end];end end - gap;}else // 包含两种情况一种temp比所有元素都大另一种temp比所有元素都小{break;}}a[end gap] temp;}}} 改进一下
void ShellSort(int* a, int n)
{int gap 3;for (int i 0; i n- gap; i ){//单趟排序int end i;int temp a[i gap];//temp存储的是元素数值 i gap 要在数组之内 不可以越界while (end 0)//一直比较到 数组第一个元素完成{if (temp a[end]){a[end gap] a[end];end end - gap;}else // 包含两种情况一种temp比所有元素都大另一种temp比所有元素都小{break;}}a[end gap] temp;}
} 我们发现gap越大虽然跑的很快但是不接近有序gap越小跑的慢但是接近有序所以需要设计合适的gap减少复杂度的同时保证最后一次排序 gap为1通常 我们设计的gap为n / 2或者 n/3 - 1。
具体代码如下
void ShellSort(int* a, int n)
{int gap n ;while (gap 1){gap / 2;//gap gap/3 - 1;for (int i 0; i n- gap; i ){//单趟排序int end i;int temp a[i gap];//temp存储的是元素数值 i gap 要在数组之内 不可以越界while (end 0)//一直比较到 数组第一个元素完成{if (temp a[end]){a[end gap] a[end];end end - gap;}else // 包含两种情况一种temp比所有元素都大另一种temp比所有元素都小{break;}}a[end gap] temp;}}
} 结果 分析总结 希尔排序的时间复杂度分析 对于外层是我们熟悉的二分或者三分 复杂度 最后为logN 对于内部两层当gap很大时候可以看成N当gap很小时经过多次预排序接近有序 复杂度也是N,我们在以gap/3分析中间的变化:图解分析如下 所以 我们可以说 希尔排序时间复杂度近似 N*logN 但是每次预排都会有增益他分组之后复杂度应该近似下图 所以虽然希尔的时间复杂度近似在N*logN这个等级但是要比其大一点查阅相关资料对于希尔时间复杂度通常是这么说的 2.2选择排序
2.2.1基本思想 每一次从待排序的数据元素中选出最小或最大的一个元素存放在序列的起始位置直到全部待排序的数据元素排完 。
2.2.2直接选择排序
在元素集合array[i]--array[n-1]中选择关键码最大(小)的数据元素 若它不是这组元素中的最后一个(第一个)元素则将它与这组元素中的最后一个第一个元素交换在剩余的array[i]--array[n-2]array[i1]--array[n-1]集合中重复上述步骤直到集合剩余1个元素 直接选择排序单趟寻找到最大的或最小的实现升序的话就与最左边的交换降序就与最右边交换我们可以用代码实现左右共同查找的方式。如下所示
void SelectSort(int* a, int n)
{//初试状态int left 0;int right n - 1;while (left right){//取最小值最大值下标为最左边的 位置int min left, max left;for (int i left 1; i right; i){if (a[i] a[min]){min i;}else if (a[i] a[max]){max i;}}swap(a[left], a[min]);if (left max) //防止出现 left位置上放的是最大值{max min;}swap(a[right], a[max]);left;right--;}
}
结果分析
选择排序的时间复杂度还是比较low的不管怎么选都是ON^2 。
2.2.3堆排序
堆排序是我们的老朋友了堆排序(Heapsort)是指利用堆积树堆这种数据结构所设计的一种排序算法它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆排降序建小堆。
代码如下
//向下调整
void AjustDown(int* a, int n, int parent)
{int child parent * 2 1; //孩子和父亲的关系while (child n) // 遍历条件{if (child 1 n a[child 1] a[child]) //左右孩子 选择最大的那个同时兼顾 右孩子也要小于边界{child;}if (a[child] a[parent]) // 建大堆{swap(a[child], a[parent]);parent child;child parent * 2 1;}else{break;}}}
void HeapSort(int* a, int n)
{for (int i (n - 1 - 1) / 2; i 0; i--) // 从最后一个节点的父亲 开始向下调整 保证父亲比孩子大{AjustDown(a, n, i);}int end n - 1;while (end 0){swap(a[end], a[0]); // 交换 根节点 和最后一个位置的数值AjustDown(a, end, 0);--end;}
}
总结
堆排的时间复杂度 我们在堆排序那个章节推过这里我直接说结论o(N * logN)。
