外贸网站建设推广,做spa的网站怎么推广,现代营销手段有哪些,怎么注册企业视频号创作不易#xff0c;感谢三连支持#xff01;#xff01;
一、排序的概念及运用
1.1 排序的概念
排序#xff1a;所谓排序#xff0c;就是使一串记录#xff0c;按照其中的某个或某些关键字的大小#xff0c;递增或递减的排列起 来的操作。稳定性感谢三连支持
一、排序的概念及运用
1.1 排序的概念
排序所谓排序就是使一串记录按照其中的某个或某些关键字的大小递增或递减的排列起 来的操作。稳定性假定在待排序的记录序列中存在多个具有相同的关键字的记录若经过排序这些记 录的相对次序保持不变即在原序列中r[i]r[j]且r[i]在r[j]之前而在排序后的序列 r[i]仍在r[j]之前则称这种排序算法是稳定的否则称为不稳定的。 内部排序数据元素全部放在内存中的排序。 外部排序数据元素太多不能同时放在内存中根据排序过程的要求不能在内外存之间移动数据 的排序。
关于这些基础概念我会在后面慢慢介绍
1.2 排序的运用 我们在淘宝购买商品的时候可以选择让商品根据销量、信用、价格、综合程度进行排序 还有高校排名以及考试的排名都是通过排序来完成的
排序存在的意义帮助我们筛选出最优的选择
1.3 常见的排序算法 二、直接插入排序
2.1 思路 直接插入排序的思想把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中直到所有的记录插入完为止得到一个新的有序序列 。 这就和我们小时候玩扑克牌摸牌整理的一样一次与前面的排比较找到合适的位置插入 2.2 直接插入排序的实现 当插入第i(i1)个元素时前面的array[0],array[1],…,array[i-1]已经排好序此时用array[i]的排序码与array[i-1],array[i-2],…的排序码顺序进行比较找到插入位置即将array[i]插入原来位置上的元素顺序后移 我们先按照上面的思路先模拟摸一张牌的过程假设目前手上的牌是2 4 9 然后摸到了1张3,我们设置最后一张牌9的下标位置为end(2)然后让新摸的牌为temp(a[3])开始慢慢往前比较发现较大的就交换位置。 int end2;int tempa[3];while (end 0){if (a[end] temp)//如果前面的数比后面的数大就前面元素插入到后面的位置{ a[end 1] a[end];--end;}elsebreak;}a[end1] temp;//不写在循环里面是避免end减成-1此时说明新加入的牌是最小的正好放在一开始的位置上述过程可以实现插入一张牌那么整体的实现就在外面加个for循序即可
void InsertSort(int* a, int n)
{for (int i 0; i n - 1; i){int end i;int temp a[i1];while (end 0){if (a[end] temp)//如果前面的数比后面的数大就前面元素插入到后面的位置a[end 1] a[end];elsebreak;--end;}a[end 1] temp;//不写在循环里面是避免end减成-1此时说明新加入的牌是最小的正好放在一开始的位置}
} 但要注意的是外面的for循环的判断条件i n - 1 也就是说i最多走到n - 2的位置即倒数第二个元素,原因是tmp是每次要插入的元素而tmp a[end 1]是end的下一个位置如果让end到最后一个元素的位置即n-1处那tmp a[end1]就会越界所以i只能到倒数第二个元素的位置 2.3 复杂度分析 时间复杂度O(N^2) --- 单趟是O(N),最坏情况N个元素都要走一次单趟基本上逆序 空间复杂度O(1) --- 额外使用空间的个数是常数个 当要排序的序列接近有序时性能最好O(N)接近有序 三、希尔排序
3.1 思路 希尔排序其实是直接插入排序的一种变形我们知道对于直接插入排序来说最坏的情况就是逆序此时的时间复杂度就是ON^2,最好的情况是接近有序此时时间复杂度为ON这个时候希尔有了一个想法有没有一种方法可以让一组无序的数据经过处理后使他接近有序然后再最后实现一次直接插入排序呢 最后希尔发明出来了希尔排序
3.2 希尔排序的实现 具体思路 1、对无序的数组进行预排序使其接近有序。 2、最后再来一次直接插入排序 这里的预排指的是间隔gap的元素为一组总计gap组我们先假设gap为3然后我们画个图来理解一下 根据我们之前写的直接插入排序算法我们可以先实现将红色的一组进行排序的算法
int gap 3;
for (int i 0; i n - gap; igap)
{int end i;int temp a[i gap];while (end 0){if (a[end] temp)//如果前面的数比后面的数大就前面元素插入到后面的位置a[end gap] a[end];elsebreak;end - gap;}a[end gap] temp;
} 我们发现如果我们一开始让i1就可以实现蓝色组的排序让i2的话就可以实现绿色组的排序所以为了让三组都完成排序我们再外面再嵌套一层循环
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];while (end 0){if (a[end] temp)//如果前面的数比后面的数大就前面元素插入到后面的位置a[end gap] a[end];elsebreak;end - gap;}a[end gap] temp;}
}
这样我们就实现了三组的预排序了
但其实上面的代码还可以优化成两层循环
int gap 3;for (int i 0; i n - gap; i ){int end i;int temp a[i gap];while (end 0){if (a[end] temp)//如果前面的数比后面的数大就前面元素插入到后面的位置a[end gap] a[end];elsebreak;end - gap;}a[end gap] temp;}
刚刚那种写法是一组一组去完成预排而现在这种写法是实现多组并排效果是一样的
这样的预排序有什么意义呢
1、 gap越大大的数可以更快到后面小的数可以更快到前面但是越不接近有序
2、gap越小大的小的就挪动的越慢但是也越接近有序
3、gap1时就是直接插入排序我们可以发现当gap等于1时这个预排序算法与直接插入排序算法的写法是一样的
现在来分析gap该取多少合适 首先gap是不能随便取的因为比如说有100万个数据gap取3显然是不合适的所以我们的gap一定要跟数据个数n建立联系gap具体取多少是最合适的没有得到很好的证明所以我们使用Knuth的思路来将我们的希尔排序完善好 void ShellSort(int* a, int n)
{//gap1 预排序//gap1 直接插入排序int gap n;while (gap 1){gap gap / 3 1;//这是为了保证gap最后一定为0for (int i 0; i n - gap; i){int end i;int temp a[i gap];while (end 0){if (a[end] temp)//如果前面的数比后面的数大就前面元素插入到后面的位置a[end gap] a[end];elsebreak;end - gap;}a[end gap] temp;}}
}
需要注意的是gap gap / 3 1是为了保证gap最后一定会等于1也就是一定会在最后进行一次直接插入排序保证有序而前面gap1的过程都是在进行预排序
3.3 复杂度分析
因为预排是一个逐渐转好的过程所以我们还按照最坏情况去考虑是不合理的因此这边是难以计算的我们看看书上的讲解 《数据结构(C语言版)》--- 严蔚敏
《数据结构-用面相对象方法与C描述》--- 殷人昆
因为咋们的gap是按照Knuth提出的方式取值的而且Knuth进行了大量的试验统计我们暂时就按oN^1.25到o1.6N^1.25到来算
四、选择排序
4.1 思路 选择排序的思想每一次从待排序的数据元素中选出最小或最大的一个元素存放在序列的起始位置直到全部待排序的数据元素排完 。 这个其实也跟摸扑克牌有关但是这次跟直接插入排序不一样的是直接插入排序是一次摸一张牌然后插入调整而选择排序是一次性拿了所有牌再逐个把小的数往前放
4.2 选择排序的实现 1、在元素集合array[i]--array[n-1]中选择关键码最大(小)的数据元素 2、若它不是这组元素中的最后一个(第一个)元素则将它与这组元素中的最后一个第一个元素交换 3、在剩余的array[i]--array[n-2]array[i1]--array[n-1]集合中重复上述步骤直到集合剩余1个元素 我们拿到所有的牌后每次都把最小的牌往前放
void SelectSort(int* a, int n)
{for (int begin 0; begin n; begin){int min begin;//记录最小元素的下标for (int i begin1; i n; i){if (a[min] a[i])min i;//记录最小的牌的下标}Swap(a[begin], a[min]);}
} 但是每次遍历就记一张最小的牌效率太低下了所以我们改造一下该算法使得该算法每遍历一次就记住最小的牌和最大的牌然后分别放在两边
void SelectSort(int* a, int n)
{int left 0; int right n - 1;while (left right){int min left;int max left;for (int i left1; i right; i){if (a[min] a[i])min i;if (a[max] a[i])max i;}//这里要考虑一种情况就是如果最大的数恰好就在最左端那么就会导致第二次swap换到后面的就不是最大的数而是最小的数了Swap(a[min], a[left]);//如果max和begin重叠修正一下if (max left)max min;Swap(a[max], a[right]);left;right--;}
}
易错点1min和max要从他们后面的第一张牌开始去一张一张比较
易错点2交换的时候如果最大的元素恰好在最左边那么就有可能被最小的元素给交换过去了所以这个时候要注意及时地修正
4.3 复杂度分析 时间复杂度O(N^2) 单趟无论选择一个还是选择两个都得遍历一遍复杂度为O(N),整体还得遍历一遍O(N) 空间复杂度O(1)
