伊人博客 一款有技术又有生活的博客

简单温习一下快速排序

发布时间:2020-04-27 12:17:24 标签: | 阅读(609)

排序算法中,我记得最清楚的就是冒泡排序,因为写起来简单,每次一用到排序,马上就把冒泡排序捞出来用,今天又用了冒泡排序,不过趁着空闲,本着优化的想法,决定改成快速排序。


然而,我不会告诉你,快速排序我已经完全忘记是什么思路了,对她的了解仅仅只是这个名字而已。


稍微百度科普科普,然后搬过来与你共享。


快速排序的时间复杂度为O(nlogn),她的思想其实很简单:

1、给定一个数组,然后选择一项作为key,然后把数组改成key的左边都比key小(大),而key的右边都比key大(小),这样就确定了key最终的位置。


2、利用递归思想,继续按照上边的思路对key左边的数组、key右边的数组继续操作,最终就可以达到从小到大(从大到小)排序。


实现步骤:

1、选择第left个元素作为key

2、从右向左找right元素,如果比key大,继续找,否则,将该元素插入到left的位置

3、从右向左找left元素,如果比key小,继续找,否则,将元素插入到right的位置

4、重复2和3,直到left>=right

5、上述1-4放到一个方法中QuickSort(int[] a,int le,int ri),此处递归调用这个方法QuickSort(a,le,left-1);    QuickSort(a,left+1,ri)

原创文章如转载,请注明出处“伊人博客

站内搜索
关注公众号(随时搜索)
文章归档
热门推荐
随机推荐
冷门晾晒