排序所谓排序就是使一串记录按照其中的某个或某些关键字的大小递增或递减地排列起来的操作。关于数组排序的问题我们有很多种解决办法如冒泡排序、堆排序等。接下来我们将系统地了解并掌握几大排序算法的实现思路插入、选择、交换、归并排序有些排序算法我们会讲好几种实现方法。这些都是比较排序我们还将学习一种简单的非比较排序——计数排序。接下来让我们先进入插入排序的学习。插入排序直接插入排序直接插入排序是一种简单的插入排序法其基本思想是把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中直到所有的记录插入完毕为止得到一个新的有序序列。就像我们玩扑克牌一样每次抽到一张牌都会插入到我们当前的手牌中按顺序排列。思路我们以下面这个数组为例来讲解排序思路我们将3看作是一个有序数组然后1是待排序数据将1插入这个有序数组中。因为1比3小所以需要交换位置有序数组变为{1,3}我们再获取待排序数据2插入该有序数组中。2比3小则需要把3放到2的位置上该操作会覆盖2所以我们还需要把2存储起来。接下来2和1比较2比1大比较结束我们把2放到1后一个位置上。依次插入我们就可以排序好该数组了。从代码角度来说我们需要知道有序数组末尾位置end然后end1获取待排序数据再用tmp把该数据存储起来。如图所示我们先将3视作有序数组后面的就是待排序数据。我们用i来遍历数组。end先获取有序数组末尾位置iend1获取的就是待排序数据1的位置tmp存储起来。然后tmp跟end处数据比较1比3小将end处数据放到end1处。然后end- -end来到了-1越界了此时结束比较将tmp放到end1的位置处。第一个数据插入结束i此时i1endi1end1就是待排序数据的位置tmp存储该数据。tmp和end处数据比较2比3小把end处数据放到end1处然后end- -。再将end和tmp比较2比1大不用将end处数据放到end1处比较结束将tmp放到end1处这个数据插入也完成了。接下来继续iendiend1获取下个排序数据循环插入直到排序完为止。代码实现综上所述我们需要一个for 循环 i来遍历整个数组因为获取的i是有序数组末尾下标end一开始i 0每次循环后有序数组元素个数都会1。循环就可以获取到end。后面我们还要通过end1获取待排序数据所以循环条件为i n - 1。然后我们初始化一下end 和待排序数据。接下来我们要插入待排序数据tmp需要从后往前与有序数组中的数据进行比较根据思路我们是让end- -来从后往前拿到有序数组中的数据的所以循环条件为end ≥ 0。我们将tmp和end处的数据进行比较如果tmp小于arr[end]则说明要把end处数据放到end1相当于往后挪然后end- -进入下次循环。直到end0自动跳出循环arr[end1]tmp此次插入数据结束如果tmp大于arr[end]则说明不用往后挪元素了break跳出循环然后arr[end1]tmp相当于自己给自己赋值。这个代码也就完成了。我们测试一下结果符合预期说明代码逻辑没什么问题。时间复杂度评估外层我们写了一个for循环循环n-1次内部嵌套了一个while循环在最坏情况下时间复杂度为O(n)。最坏情况也就是一个降序数组每次排序数据的移动都达到了最大值也就是大的数据在前小的数据在后。如果我们可以尽量让小的数据在前大的数据在后那么每次排序数据的移动量会尽可能减小时间复杂度就会接近O(n)。既然如此我们可不可以给原数组进行预排序让小的数据在前大的数据在后呢答案是可以的希尔排序因此诞生了。希尔排序希尔排序法又称缩小增量法。希尔排序法的基本思想是先选定一个整数通常是 gap n/3 1把待排序文件所有记录分成各组所有的距离相等的记录分在同一组内并对每一组内的记录进行排序然后 gap gap/3 1 得到下一个整数再将数组分成各组进行插入排序当 gap 1 时就相当于直接插入排序。思路比如说有以下数组一开始 gap4每隔 gap 个位置的数据分为一组。每组就是 {5,6,4}, {2,9}, {3,8}, {7,1}。然后我们对每组都进行预排序将小的数据放前大的数据放后面。每组就变成 {4,5,6}, {2,9}, {3,8}, {1,7} 了。然后 gapgap/312再进行分组。这次分为了两组{4,3,5,8,6}, {2,1,9,7}。再次给每组进行预排序。然后gapgap/311gap1时相当于直接插入排序。此时排序就排序好了。这就是希尔排序的整个过程。我们代码思路简单过一遍一开始gap4我们用i来遍历整个数组我们是一整组排完再排下一组吗不是我们是i直接遍历一遍数组。一开始i0endiendgap就可以获取该组待排序数据。同样地需要tmp来存储。6比5大不用挪数据此次插入结束。i拿到下一个组的有序数组末尾endiendgap拿到该组待排序数据tmp存储。9比2大不用挪数据此次插入结束。i拿到下一个组的有序数组末尾endiendgap拿到该组待排序数据tmp存储。8比3大不用挪数据此次插入结束。i拿到下一个组的有序数组末尾endiendgap拿到该组待排序数据tmp存储。1比7小end放到endgap的位置处然后end-gap获取有序数组前面的数据。此时发现end越界了说明该组前面没有数据比较结束tmp放到endgap的位置处。此次插入结束i拿到下一个组的有序数组末尾endiendgap拿到该组待排序数据tmp存储。4比6小将end放到endgap的位置处end-gap拿到有序数组前一个数据。4比5小end放到endgap的位置处end-gap拿到有序数组前一个数据。end越界说明该组前面没有数据了比较结束将tmp放到endgap的位置处。此次插入结束i拿到下一个组的有序数组末尾endiendgap拿到该组待排序数据tmp存储。发现endgap越界了说明本次预排序结束。下次gapgap/31继续预排序直到gap1时变成直接插入排序。我们会发现用i遍历当i0时排序第一组的一个数据i1时可能就排的是第二组的一个数据了说明用i来遍历可以实现该功能并且排序的循环条件应该是in-gap。然后和直接插入排序不同的是每次end是end-gap获取该组前一个数据。其他基本一样。代码实现我们先让 gapn然后每次进入预排序 gapgap/31开始预排序。这里循环条件为 gap 1 的原因是gap 到最后一定是 1gapgap/31如果循环条件改为 gap 0 的话会进入死循环。然后我们开始写预排序的代码逻辑实际上和直接插入排序没什么区别只是在细微处做了一些改动。代码就完成了我们来测试一下。结果符合预期说明代码逻辑没有问题。时间复杂度评估希尔排序不是嵌套了三层循环吗为什么时间效率比直接插入排序好我们简单来看一下随机生成10万个数据然后让这两个算法来排序看哪个算法用时更少。voidtest(){srand(time(NULL));//开辟10万个整型空间int*a1(int*)malloc(100000*sizeof(int));if(a1NULL){perror(malloc);exit(-1);}int*a2(int*)malloc(100000*sizeof(int));if(a2NULL){perror(malloc);exit(-1);}//随机生成10万个数for(inti0;i100000;i){a1[i]rand();a2[i]a1[i];}//排序并计时intbegin1clock();SelectSort(a1,100000);intend1clock();intbegin2clock();ShellSort(a1,100000);intend2clock();printf(SelectSort:%d\n,end1-begin1);printf(ShellSort:%d\n,end2-begin2);}我们可以发现希尔排序比直接插入排序快了 2000 多倍也就是几毫秒的时间就排好了 10 万个数据。对于希尔排序的时间复杂度和 gap 值的选取还有初始数据的有序程度有关平均情况下希尔排序的时间复杂度为 O(n^1.3) ~ O(nlogn) 之间比直接插入排序要快得多。
排序所谓排序就是使一串记录按照其中的某个或某些关键字的大小递增或递减地排列起来的操作。关于数组排序的问题我们有很多种解决办法如冒泡排序、堆排序等。接下来我们将系统地了解并掌握几大排序算法的实现思路插入、选择、交换、归并排序有些排序算法我们会讲好几种实现方法。这些都是比较排序我们还将学习一种简单的非比较排序——计数排序。接下来让我们先进入插入排序的学习。插入排序直接插入排序直接插入排序是一种简单的插入排序法其基本思想是把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中直到所有的记录插入完毕为止得到一个新的有序序列。就像我们玩扑克牌一样每次抽到一张牌都会插入到我们当前的手牌中按顺序排列。思路我们以下面这个数组为例来讲解排序思路我们将3看作是一个有序数组然后1是待排序数据将1插入这个有序数组中。因为1比3小所以需要交换位置有序数组变为{1,3}我们再获取待排序数据2插入该有序数组中。2比3小则需要把3放到2的位置上该操作会覆盖2所以我们还需要把2存储起来。接下来2和1比较2比1大比较结束我们把2放到1后一个位置上。依次插入我们就可以排序好该数组了。从代码角度来说我们需要知道有序数组末尾位置end然后end1获取待排序数据再用tmp把该数据存储起来。如图所示我们先将3视作有序数组后面的就是待排序数据。我们用i来遍历数组。end先获取有序数组末尾位置iend1获取的就是待排序数据1的位置tmp存储起来。然后tmp跟end处数据比较1比3小将end处数据放到end1处。然后end- -end来到了-1越界了此时结束比较将tmp放到end1的位置处。第一个数据插入结束i此时i1endi1end1就是待排序数据的位置tmp存储该数据。tmp和end处数据比较2比3小把end处数据放到end1处然后end- -。再将end和tmp比较2比1大不用将end处数据放到end1处比较结束将tmp放到end1处这个数据插入也完成了。接下来继续iendiend1获取下个排序数据循环插入直到排序完为止。代码实现综上所述我们需要一个for 循环 i来遍历整个数组因为获取的i是有序数组末尾下标end一开始i 0每次循环后有序数组元素个数都会1。循环就可以获取到end。后面我们还要通过end1获取待排序数据所以循环条件为i n - 1。然后我们初始化一下end 和待排序数据。接下来我们要插入待排序数据tmp需要从后往前与有序数组中的数据进行比较根据思路我们是让end- -来从后往前拿到有序数组中的数据的所以循环条件为end ≥ 0。我们将tmp和end处的数据进行比较如果tmp小于arr[end]则说明要把end处数据放到end1相当于往后挪然后end- -进入下次循环。直到end0自动跳出循环arr[end1]tmp此次插入数据结束如果tmp大于arr[end]则说明不用往后挪元素了break跳出循环然后arr[end1]tmp相当于自己给自己赋值。这个代码也就完成了。我们测试一下结果符合预期说明代码逻辑没什么问题。时间复杂度评估外层我们写了一个for循环循环n-1次内部嵌套了一个while循环在最坏情况下时间复杂度为O(n)。最坏情况也就是一个降序数组每次排序数据的移动都达到了最大值也就是大的数据在前小的数据在后。如果我们可以尽量让小的数据在前大的数据在后那么每次排序数据的移动量会尽可能减小时间复杂度就会接近O(n)。既然如此我们可不可以给原数组进行预排序让小的数据在前大的数据在后呢答案是可以的希尔排序因此诞生了。希尔排序希尔排序法又称缩小增量法。希尔排序法的基本思想是先选定一个整数通常是 gap n/3 1把待排序文件所有记录分成各组所有的距离相等的记录分在同一组内并对每一组内的记录进行排序然后 gap gap/3 1 得到下一个整数再将数组分成各组进行插入排序当 gap 1 时就相当于直接插入排序。思路比如说有以下数组一开始 gap4每隔 gap 个位置的数据分为一组。每组就是 {5,6,4}, {2,9}, {3,8}, {7,1}。然后我们对每组都进行预排序将小的数据放前大的数据放后面。每组就变成 {4,5,6}, {2,9}, {3,8}, {1,7} 了。然后 gapgap/312再进行分组。这次分为了两组{4,3,5,8,6}, {2,1,9,7}。再次给每组进行预排序。然后gapgap/311gap1时相当于直接插入排序。此时排序就排序好了。这就是希尔排序的整个过程。我们代码思路简单过一遍一开始gap4我们用i来遍历整个数组我们是一整组排完再排下一组吗不是我们是i直接遍历一遍数组。一开始i0endiendgap就可以获取该组待排序数据。同样地需要tmp来存储。6比5大不用挪数据此次插入结束。i拿到下一个组的有序数组末尾endiendgap拿到该组待排序数据tmp存储。9比2大不用挪数据此次插入结束。i拿到下一个组的有序数组末尾endiendgap拿到该组待排序数据tmp存储。8比3大不用挪数据此次插入结束。i拿到下一个组的有序数组末尾endiendgap拿到该组待排序数据tmp存储。1比7小end放到endgap的位置处然后end-gap获取有序数组前面的数据。此时发现end越界了说明该组前面没有数据比较结束tmp放到endgap的位置处。此次插入结束i拿到下一个组的有序数组末尾endiendgap拿到该组待排序数据tmp存储。4比6小将end放到endgap的位置处end-gap拿到有序数组前一个数据。4比5小end放到endgap的位置处end-gap拿到有序数组前一个数据。end越界说明该组前面没有数据了比较结束将tmp放到endgap的位置处。此次插入结束i拿到下一个组的有序数组末尾endiendgap拿到该组待排序数据tmp存储。发现endgap越界了说明本次预排序结束。下次gapgap/31继续预排序直到gap1时变成直接插入排序。我们会发现用i遍历当i0时排序第一组的一个数据i1时可能就排的是第二组的一个数据了说明用i来遍历可以实现该功能并且排序的循环条件应该是in-gap。然后和直接插入排序不同的是每次end是end-gap获取该组前一个数据。其他基本一样。代码实现我们先让 gapn然后每次进入预排序 gapgap/31开始预排序。这里循环条件为 gap 1 的原因是gap 到最后一定是 1gapgap/31如果循环条件改为 gap 0 的话会进入死循环。然后我们开始写预排序的代码逻辑实际上和直接插入排序没什么区别只是在细微处做了一些改动。代码就完成了我们来测试一下。结果符合预期说明代码逻辑没有问题。时间复杂度评估希尔排序不是嵌套了三层循环吗为什么时间效率比直接插入排序好我们简单来看一下随机生成10万个数据然后让这两个算法来排序看哪个算法用时更少。voidtest(){srand(time(NULL));//开辟10万个整型空间int*a1(int*)malloc(100000*sizeof(int));if(a1NULL){perror(malloc);exit(-1);}int*a2(int*)malloc(100000*sizeof(int));if(a2NULL){perror(malloc);exit(-1);}//随机生成10万个数for(inti0;i100000;i){a1[i]rand();a2[i]a1[i];}//排序并计时intbegin1clock();SelectSort(a1,100000);intend1clock();intbegin2clock();ShellSort(a1,100000);intend2clock();printf(SelectSort:%d\n,end1-begin1);printf(ShellSort:%d\n,end2-begin2);}我们可以发现希尔排序比直接插入排序快了 2000 多倍也就是几毫秒的时间就排好了 10 万个数据。对于希尔排序的时间复杂度和 gap 值的选取还有初始数据的有序程度有关平均情况下希尔排序的时间复杂度为 O(n^1.3) ~ O(nlogn) 之间比直接插入排序要快得多。
![[光学原理与应用-521]：对光的错误理解与纠偏](http://pic.xiahunao.cn/yaotu/[光学原理与应用-521]：对光的错误理解与纠偏)
