
来源百度百科:
算法描述:
从最简单开始,首先我们创建一个数组,该数组有5位数字:
下面我们根据算法的描述来进行代码验算 (第一趟排序):
如果前一位的数比后一位的数要大,那么就交换,直到将数组的所有元素都比较了一遍!
经过我们第一趟比较,我们可以发现:最大的值就在数组的末尾了!
第二趟排序跟第一趟排序一样,也是用前一位与后一位比较,如果前一位比后一位要大,那就交换。值得注意的是:并不需要与最后一位比较了,因为在第一趟排序完了,最后一位已经是最大的数了。同理,我们第二趟排序完了之后,倒数第二位也是第二大的数了。
第二趟排序的代码如下:
结果:我们的第二大数已经排在了倒数第二位了
值得说明的是:上面的结果看起来已经是排序好的了,其实是我在测试时数据还不足够乱,如果数据足够乱的话,是需要4(n-1)趟排序的!
但我们从上面的代码就可以发现:第一趟和第二趟的比较、交换代码都是重复的,并且我们的比较都是写死的(0,1,2,3,4),并不通用!
我们的数组有5位数字
我们可以根据上面规律推断出:
再从上面的规律可以总结出:5位数的数组需要4躺排序的,每躺排序之后次数减1(因为前一趟已经把前一趟数的最大值确定下来了)!
于是我们可以根据for循环和变量将上面的代码进行简化:
从上面的例子我们可以看出来,如果数据足够乱的情况下是需要经过4躺比较才能将数组完整排好序。但是我们在第二躺比较后就已经得到排好序的数组了。
但是,我们的程序在第二趟排序后仍会执行第三趟、第四趟排序。这是没有必要的,因此我们可以对其进行优化一下:
代码如下:
C语言实现第一种方式:
C语言实现第二种方式递归:
测试代码:
选择排序
思路:找到数组中最大的元素,与数组最后一位元素交换。当只有一个数时,则不需要选择了,因此需要n-1趟排序
代码实现要点:两个for循环,外层循环控制排序的趟数,内层循环找到当前趟数的最大值,随后与当前趟数组最后的一位元素交换
思路:将一个元素插入到已有序的数组中,在初始时未知是否存在有序的数据,因此将元素第一个元素看成是有序的。与有序的数组进行比较,比它大则直接放入,比它小则移动数组元素的位置,找到个合适的位置插入。当只有一个数时,则不需要插入了,因此需要n-1趟排序
代码实现:一个for循环内嵌一个while循环实现,外层for循环控制需要排序的趟数,while循环找到合适的插入位置(并且插入的位置不能小于0)
思路:在数组中找一个元素(节点),比它小的放在节点的左边,比它大的放在节点右边。一趟下来,比节点小的在左边,比节点大的在右边。不断执行这个操作….
代码实现:支点取中间,使用L和R表示数组的最小和最大位置。不断进行比较,直到找到比支点小(大)的数,随后交换,不断减小范围。递归L到支点前一个元素(j)。递归支点后一个元素(i)到R元素
思路:将两个已排好序的数组合并成一个有序的数组。将元素分隔开来,看成是有序的数组,进行比较合并。不断拆分和合并,直到只有一个元素
代码实现:在第一趟排序时实质是两个元素(看成是两个已有序的数组)来进行合并,不断执行这样的操作,最终数组有序,拆分左边,右边,合并…
思路:堆排序使用到了完全二叉树的一个特性,根节点比左孩子和右孩子都要大,完成一次建堆的操作实质上是比较根节点和左孩子、右孩子的大小,大的交换到根节点上,直至最大的节点在树顶。随后与数组最后一位元素进行交换
代码实现:只要左子树或右子树大于当前根节点,则替换。替换后会导致下面的子树发生了变化,因此同样需要进行比较,直至各个节点实现父>子这么一个条件
思路:希尔排序实质上就是插入排序的增强版,希尔排序将数组分隔成n组来进行插入排序,直至该数组宏观上有序,最后再进行插入排序时就不用移动那么多次位置了~
代码思路:希尔增量一般是gap = gap / 2,只是比普通版插入排序多了这么一个for循环而已。
思路:基数排序(桶排序):将数字切割成个、十、百、千位放入到不同的桶子里,放一次就按桶子顺序回收一次,直至最大位数的数字放完~那么该数组就有序了
代码实现:先找到数组的最大值,然后根据最大值/10来作为循环的条件(只要>0,那么就说明还有位数)。将个位、十位、…分配到桶子上,每分配一次就回收一次
我最近一直在连载《对线面试官》系列,目前已经连载38篇啦!一个说人话的面试系列!
【大厂面试知识点】、【简历模板】、【原创文章】电子书,共有1263页
我把这些上传到网盘,你们有需要直接下载就好了。做到这份上了,不会还想白嫖吧?点赞和转发又不用钱。
链接:pan.baidu.com/s/1pQTuKBYs… 密码:3wom
