资讯专栏INFORMATION COLUMN

我的面试准备过程--排序算法(更新中)

Karrdy / 2001人阅读

摘要:通常情况下,快速排序的时间复杂度为,但在最坏情况下它的时间复杂度会退化至,不过我们可以通过对输入数组进行随机化打乱元素的排列顺序来避免最坏情况的发生。

写在最前面

导师贪腐出逃美国,两年未归,可怜了我。拿了小米和美团的offer,要被延期,offer失效,工作重新找。把准备过程纪录下来,共勉。

冒泡算法

最初级

</>复制代码

  1. public void bubbleSort(int[] a){
  2. int len = a.length;
  3. for(int i = 0; i < len; i++){
  4. for(int j = 1; j < len; j++){
  5. if(a[j - 1] > a[j]){
  6. int temp = a[j];
  7. a[j] = a[j - 1];
  8. a[j - 1] = temp;
  9. }
  10. }
  11. }
  12. }

小优化

</>复制代码

  1. public void bubbleSort(int[] a){
  2. int len = a.length;
  3. for(int i = 0; i < len; i++){
  4. for(int j = 1; j < len - i; j++){
  5. if(a[j - 1] > a[j]){
  6. int temp = a[j];
  7. a[j] = a[j - 1];
  8. a[j - 1] = temp;
  9. }
  10. }
  11. }
  12. }

大优化,一次冒泡过程没有交换,直接退出排序

</>复制代码

  1. public void bubbleSort(int[] a){
  2. int len = a.length;
  3. boolean flag = true;
  4. while(flag){
  5. flag = false;
  6. for(int j = 0; j < len - 1; j++){
  7. if(a[j] > a[j + 1]){
  8. int temp = a[j];
  9. a[j] = a[j + 1];
  10. a[j + 1] = temp;
  11. flag = true;
  12. }
  13. }
  14. }
  15. }
快速排序

快速排序是目前应用最广泛的排序算法之一,它是一般场景中大规模数据排序的首选,它的实际性能要好于归并排序。通常情况下,快速排序的时间复杂度为O(nlogn),但在最坏情况下它的时间复杂度会退化至O(n^2),不过我们可以通过对输入数组进行“随机化”(打乱元素的排列顺序)来避免最坏情况的发生。除了实际执行性能好,快速排序的另一个优势是它能够实现“原地排序”,也就是说它几乎不需要额外的空间来辅助排序。

</>复制代码

  1. public static void quickSort(int[] a){
  2. qSort(a, 0, a.length - 1);
  3. }
  4. private static void qSort(int[] a, int low, int high){
  5. if(low < high){
  6. int pivot = partition(a, low, high);
  7. qSort(a, low, pivot - 1);
  8. qSort(a, pivot + 1, high);
  9. }
  10. }
  11. private static void partition(int[] a, int low, int high){
  12. int pivotValue = a[low];
  13. while(low < high){
  14. while(low < high && a[high] >= pivotValue){
  15. high--;
  16. }
  17. a[low] = a[high];
  18. while(low < high && a[low] <= pivotValue){
  19. low++;
  20. }
  21. a[high] = a[low];
  22. }
  23. a[low] = pivotValue;
  24. return low;
  25. }
关于快排的不稳定性

稳定性的概念并不复杂,它只表示两个值相同的元素在排序前后是否有位置变化。如果前后位置变化,则排序算法是不稳定的,否则是稳定的。稳定性的定义符合常理,两个值相同的元素无需再次交换位置,交换位置是做了一次无用功。
两个循环在进行元素比较时,分别用了小于和大于操作(也可以改用小于等于和大于等于,但是对性能没有影响)。这就意味着如果出现和pivot值相同的元素,它都会被作为交换对象而移动到pivot的前面或者后面,这就出现了值相同的元素会交换顺序的问题,因而是不稳定的。

</>复制代码

  1. 本节参考 http://blog.csdn.net/yutianzu...

快排的优化

优化选取枢轴,优化不必要的交换
三数取中,即取三个关键字先进行排序,将中间数作为枢轴, 一般是取左端、右端和中间三个数, 也可以随机选取。
修改partition算法

</>复制代码

  1. private static int partition(int[] a, int low, int high){
  2. choosePivotValue(a, low, high);
  3. int pivotValue = a[low];
  4. while(low < high){
  5. while(low < high && a[high] > pivotValue){
  6. high--;
  7. }
  8. //swap(a,low ,high);交换
  9. //采用替换而不是交换的方式进行操作
  10. a[low] = a[high];
  11. while(low < high && a[low] < pivotValue){
  12. low++;
  13. }
  14. a[high] = a[low];
  15. }
  16. a[low] = pivotValue;
  17. return low;
  18. }
  19. private static void swap(int[] a,int low,int high){
  20. int temp = a[low];
  21. a[low] = a[high];
  22. a[high] = temp;
  23. }
  24. //使中间值处于a[low]的位置
  25. private static void choosePivotValue(int[] a,int low,int high){
  26. int mid = (low + high) / 2;
  27. if(a[low] > a[high]){ // 保证左端较小
  28. swap(a, low, high);
  29. }
  30. if(a[mid] > a[high]){//保证中间较小
  31. swap(a, mid, high);
  32. }
  33. if(a[mid] > a[low]){//保证中间较小
  34. swap(a, low, mid);
  35. }
  36. }

优化小数组时的排序方案
快速排序适用于非常大的数组的解决办法, 那么相反的情况,如果数组非常小,其实快速排序反而不如直接插入排序来得更好(直接插入是简单排序中性能最好的)。其原因在于快速排序用到了递归操作,在大量数据排序时,这点性能影响相对于它的整体算法优势是可以忽略的,但如果数组只有几个记录需要排序时,这就成了大材小用,因此我们需要改进一下 qSort函数。

</>复制代码

  1. public static void qSort(int[] a, int low, int high){
  2. if((high - low) > MAX_LENGTH){
  3. int pivot = partition(a, low, high);
  4. qSort(a, low, pivot - 1);
  5. qSort(a, pivot + 1, high);
  6. }else{
  7. insertSort(a);
  8. }
  9. }
  10. private static void insertSort(int[] a){
  11. for(int i = 1; i < a.length; i++){
  12. int key = a[i];
  13. int j = i - 1;
  14. while(j >= 0 && a[j] > key){
  15. a[j + 1] = a[j];
  16. }
  17. a[j + 1] = key;
  18. }
  19. }

优化递归操作
递归对性能是有一定影响的, qSort 函数在其尾部有两次递归操作。
如果待排序的序列划分极端不平衡,递归深度将趋近与N ,而不是平衡时的 logN,就不仅仅是速度快慢的问题了,栈的大小是很有限的,每次递归调用都会耗费一定的空间 ,函数的参数越多,每次递归耗费的空间也越多。如果能减少递归,将会提高性能。我们对 qSort 实施尾递归优化。

</>复制代码

  1. public static void qSort(int[] a, int low, int high){
  2. if((high - low) > MAX_LENGTH){
  3. while(low < high){
  4. int pivot = partition(a, low, high);
  5. qSort(a, low, pivot - 1);
  6. low = pivot + 1;
  7. }
  8. }else{
  9. insertSort(a);
  10. }
  11. }

当我们将 if 改成 while 后,因为第一次递归以后,变量low就没有用处了,所以可以将pivot+1 赋值给low,再循环后,来一次 partition(arr,low,high)时,其效果等同于“qSort(arr, pivot+1, high);”。结果相同,但因采用迭代而不是递归的方法可以缩减堆栈深度,从而提高了整体性能。

</>复制代码

  1. 本节参考 http://blog.csdn.net/scgaligu...

归并排序

</>复制代码

  1. public static void sort(int[] a, int low, int high){
  2. int mid = (low + high) / 2;
  3. sort(a, low, mid);
  4. sort(a, mid + 1, high);
  5. merge(a, low, mid, high);
  6. }
  7. private static void merge(int[] a, int low, int mid, int high){
  8. int i = low;
  9. int j = mid + 1;
  10. int k = 0;
  11. int[] temp = new int[high - low + 1];
  12. while(i <= mid && j <= high){
  13. if(a[i] < a[j]){
  14. temp[k++] = a[i++];
  15. }else{
  16. temp[k++] = a[j++];
  17. }
  18. }
  19. while(i <= mid){
  20. temp[k++] = a[i++];
  21. }
  22. while(j <= high){
  23. temp[k++] = a[j++];
  24. }
  25. for(k = 0; k < temp.length; k++){
  26. a[low + k] = temp[k];
  27. }
  28. }
选择排序

</>复制代码

  1. public static void choseSort(int[] a){
  2. for(int i = 0; i < a.length; i++){
  3. int lowIndex = i;
  4. for(int j = i; j < a.length; j++){
  5. if(a[j] < a[lowIndex]){
  6. lowIndex = j;
  7. }
  8. }
  9. int temp = a[i];
  10. a[i] = a[lowIndex];
  11. a[lowIndex] = temp;
  12. }
  13. }
插入排序

</>复制代码

  1. public static void insertSort(int[] a){
  2. for(int i = 1; i < a.length; i++){
  3. int j = i - 1;
  4. int key = a[i];
  5. while(j >= 0 && a[j] > key){
  6. a[j + 1] = a[j];
  7. j--;
  8. }
  9. a[j + 1] = key;
  10. }
  11. }

</>复制代码

  1. 本文参考 http://blog.csdn.net/xsf50717...

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/70125.html

相关文章

  • 求职准备 - 收藏集 - 掘金

    摘要:一基础接口的意义百度规范扩展回调抽象类的意义想不想通过一线互联网公司面试文档整理为电子书掘金简介谷歌求职记我花了八个月准备谷歌面试掘金原文链接翻译者 【面试宝典】从对象深入分析 Java 中实例变量和类变量的区别 - 掘金原创文章,转载请务必保留原出处为:http://www.54tianzhisheng.cn/... , 欢迎访问我的站点,阅读更多有深度的文章。 实例变量 和 类变量...

    cuieney 评论0 收藏0
  • 记一次XX前端面试

    摘要:面试官说那我问你一个哲学的问题,为什么有数据结构这种东西哇,这是啥,巴拉巴拉扯了一通,大致就是物以类聚,人以群分,先人积累下来的经验,这些让我们更方便处理数据啥的。 前因,没有比摸鱼有趣的事了 距离自己被外派(俗称外包)出去,已经过了快五个月,工作的话,很闲。人啊,一定保持好的习惯,懒惰是会上瘾,日常摸鱼,怀疑人生,我是谁,我在哪,我要干什么。 中午吃饭的时候,收到了boss直聘的一条...

    Shisui 评论0 收藏0
  • 一个JAVA渣渣的校招成长记,附BAT美团网易等20家面经总结

    摘要:作者重庆森林链接来源牛客网整个三月份通过牛客网和网友分享的经验学到了很多东西,现在反馈一下我的面试经历,希望对同学们有帮助。个人情况大三本方向渣硕,经过实验室学长内推,于三月底完成面试。校招是实力和运气的结合,缺一不可。 欢迎关注我的微信公众号:Java面试通关手册(坚持原创,分享美文,分享各种Java学习资源,面试题,以及企业级Java实战项目回复关键字免费领取):showImg(h...

    mozillazg 评论0 收藏0
  • 春招:我居然三天就拿到了offer?

    摘要:算法名称描述优点缺点标记清除算法暂停除了线程以外的所有线程算法分为标记和清除两个阶段首1 回顾我的时间线 在本文的开头,先分享一下自己的春招经历吧: 各位掘友大家好,我是练习时长快一年的Android小蔡鸡,喜欢看源码,逛掘金,写技术文章...... 好了好,不开玩笑了OWO,今年春招投了许多简历的,但是被捞的只有阿里,头条和美团,一路下来挺不容易的. 个人认为在春招中运气>性格>三观>技术...

    stormjun 评论0 收藏0
  • 一个 16年毕业生所经历的 PHP 面试

    摘要:正确做法是给加索引,还有联合索引,并不能避免全表扫描。 前言:有收获的话请加颗小星星,没有收获的话可以 反对 没有帮助 举报三连 有心的同学应该会看到我这个noteBook下面的其它知识,希望对你们有些许帮助。 本文地址 时间点:2017-11 一个16年毕业生所经历的php面试 一、什么是面试 二、面试准备 1. 问:什么时候开始准备? 2. 问:怎么准备? 三、面试...

    dabai 评论0 收藏0

发表评论

0条评论

Karrdy

|高级讲师

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<