数据结构与算法之美
王争
前Google工程师
立即订阅
71638 人已学习
课程目录
已完结 75 讲
0/4登录后,你可以任选4讲全文学习。
开篇词 (1讲)
开篇词 | 从今天起,跨过“数据结构与算法”这道坎
免费
入门篇 (4讲)
01 | 为什么要学习数据结构和算法?
02 | 如何抓住重点,系统高效地学习数据结构与算法?
03 | 复杂度分析(上):如何分析、统计算法的执行效率和资源消耗?
04 | 复杂度分析(下):浅析最好、最坏、平均、均摊时间复杂度
基础篇 (38讲)
05 | 数组:为什么很多编程语言中数组都从0开始编号?
06 | 链表(上):如何实现LRU缓存淘汰算法?
07 | 链表(下):如何轻松写出正确的链表代码?
08 | 栈:如何实现浏览器的前进和后退功能?
09 | 队列:队列在线程池等有限资源池中的应用
10 | 递归:如何用三行代码找到“最终推荐人”?
11 | 排序(上):为什么插入排序比冒泡排序更受欢迎?
12 | 排序(下):如何用快排思想在O(n)内查找第K大元素?
13 | 线性排序:如何根据年龄给100万用户数据排序?
14 | 排序优化:如何实现一个通用的、高性能的排序函数?
15 | 二分查找(上):如何用最省内存的方式实现快速查找功能?
16 | 二分查找(下):如何快速定位IP对应的省份地址?
17 | 跳表:为什么Redis一定要用跳表来实现有序集合?
18 | 散列表(上):Word文档中的单词拼写检查功能是如何实现的?
19 | 散列表(中):如何打造一个工业级水平的散列表?
20 | 散列表(下):为什么散列表和链表经常会一起使用?
21 | 哈希算法(上):如何防止数据库中的用户信息被脱库?
22 | 哈希算法(下):哈希算法在分布式系统中有哪些应用?
23 | 二叉树基础(上):什么样的二叉树适合用数组来存储?
24 | 二叉树基础(下):有了如此高效的散列表,为什么还需要二叉树?
25 | 红黑树(上):为什么工程中都用红黑树这种二叉树?
26 | 红黑树(下):掌握这些技巧,你也可以实现一个红黑树
27 | 递归树:如何借助树来求解递归算法的时间复杂度?
28 | 堆和堆排序:为什么说堆排序没有快速排序快?
29 | 堆的应用:如何快速获取到Top 10最热门的搜索关键词?
30 | 图的表示:如何存储微博、微信等社交网络中的好友关系?
31 | 深度和广度优先搜索:如何找出社交网络中的三度好友关系?
32 | 字符串匹配基础(上):如何借助哈希算法实现高效字符串匹配?
33 | 字符串匹配基础(中):如何实现文本编辑器中的查找功能?
34 | 字符串匹配基础(下):如何借助BM算法轻松理解KMP算法?
35 | Trie树:如何实现搜索引擎的搜索关键词提示功能?
36 | AC自动机:如何用多模式串匹配实现敏感词过滤功能?
37 | 贪心算法:如何用贪心算法实现Huffman压缩编码?
38 | 分治算法:谈一谈大规模计算框架MapReduce中的分治思想
39 | 回溯算法:从电影《蝴蝶效应》中学习回溯算法的核心思想
40 | 初识动态规划:如何巧妙解决“双十一”购物时的凑单问题?
41 | 动态规划理论:一篇文章带你彻底搞懂最优子结构、无后效性和重复子问题
42 | 动态规划实战:如何实现搜索引擎中的拼写纠错功能?
高级篇 (9讲)
43 | 拓扑排序:如何确定代码源文件的编译依赖关系?
44 | 最短路径:地图软件是如何计算出最优出行路径的?
45 | 位图:如何实现网页爬虫中的URL去重功能?
46 | 概率统计:如何利用朴素贝叶斯算法过滤垃圾短信?
47 | 向量空间:如何实现一个简单的音乐推荐系统?
48 | B+树:MySQL数据库索引是如何实现的?
49 | 搜索:如何用A*搜索算法实现游戏中的寻路功能?
50 | 索引:如何在海量数据中快速查找某个数据?
51 | 并行算法:如何利用并行处理提高算法的执行效率?
实战篇 (5讲)
52 | 算法实战(一):剖析Redis常用数据类型对应的数据结构
53 | 算法实战(二):剖析搜索引擎背后的经典数据结构和算法
54 | 算法实战(三):剖析高性能队列Disruptor背后的数据结构和算法
55 | 算法实战(四):剖析微服务接口鉴权限流背后的数据结构和算法
56 | 算法实战(五):如何用学过的数据结构和算法实现一个短网址系统?
加餐:不定期福利 (6讲)
不定期福利第一期 | 数据结构与算法学习书单
不定期福利第二期 | 王争:羁绊前行的,不是肆虐的狂风,而是内心的迷茫
不定期福利第三期 | 测一测你的算法阶段学习成果
不定期福利第四期 | 刘超:我是怎么学习《数据结构与算法之美》的?
总结课 | 在实际开发中,如何权衡选择使用哪种数据结构和算法?
《数据结构与算法之美》学习指导手册
加餐:春节7天练 (7讲)
春节7天练 | Day 1:数组和链表
春节7天练 | Day 2:栈、队列和递归
春节7天练 | Day 3:排序和二分查找
春节7天练 | Day 4:散列表和字符串
春节7天练 | Day 5:二叉树和堆
春节7天练 | Day 6:图
春节7天练 | Day 7:贪心、分治、回溯和动态规划
加餐:用户学习故事 (2讲)
用户故事 | Jerry银银:这一年我的脑海里只有算法
用户故事 | zixuan:站在思维的高处,才有足够的视野和能力欣赏“美”
结束语 (3讲)
结束语 | 送君千里,终须一别
第2季回归 | 这一次,我们一起拿下设计模式!
打卡召集令 | 60 天攻克数据结构与算法
免费
数据结构与算法之美
登录|注册

春节7天练 | Day 3:排序和二分查找

王争 2019-02-06
你好,我是王争。初三好!
为了帮你巩固所学,真正掌握数据结构和算法,我整理了数据结构和算法中,必知必会的 30 个代码实现,分 7 天发布出来,供你复习巩固所用。今天是第三篇。
和昨天一样,你可以花一点时间,来完成测验。测验完成后,你可以根据结果,回到相应章节,有针对性地进行复习。
前两天的内容,是关于数组和链表、排序和二分查找的。如果你错过了,点击文末的“上一篇”,即可进入测试。

关于排序和二分查找的几个必知必会的代码实现

排序

实现归并排序、快速排序、插入排序、冒泡排序、选择排序
编程实现 O(n) 时间复杂度内找到一组数据的第 K 大元素

二分查找

实现一个有序数组的二分查找算法
实现模糊二分查找算法(比如大于等于给定值的第一个元素)

对应的 LeetCode 练习题(@Smallfly 整理)

Sqrt(x) (x 的平方根)
做完题目之后,你可以点击“请朋友读”,把测试题分享给你的朋友,说不定就帮他解决了一个难题。
祝你取得好成绩!明天见!
取消
完成
0/1000字
划线
笔记
复制
© 版权归极客邦科技所有,未经许可不得传播售卖。 页面已增加防盗追踪,如有侵权极客邦将依法追究其法律责任。
该试读文章来自付费专栏《数据结构与算法之美》,如需阅读全部文章,
请订阅文章所属专栏。
立即订阅
登录 后留言

精选留言(29)

  • 李皮皮皮皮皮
    各种排序算法真要说起来实际中使用的最多的也就是快排了。然而各种编程语言内置的标准库都包含排序算法的实现,基本没有自己动手实现的必要。然后作为经典的算法,自己实现一遍,分析分析时间空间复杂度对自己的算法设计大有裨益。需要注意的是为了高效,在实际的实现中,多种排序算法往往是组合使用的。例如c标准库中总体上是快排,但当数据量小于一定程度,会转而使用选择或插入排序。
    求平方根使用牛顿法二分逼近😄
    2019-02-06
    5
  • TryTs
    虽然现在有很多排序算法自己不会亲自写,但是作为算法的基础,分治,归并,冒泡等排序算法在时间复杂度,空间复杂度以及原地排序这些算法知识上的理解非常有帮助。递归分治这些算法思想在简单的算法中也能体现出来,其实更多的是思维方式的训练。

    编辑回复: 感谢您参与春节七天练的活动,为了表彰你在活动中的优秀表现,赠送您99元专栏通用阅码,我们会在3个工作日之内完成礼品发放,如有问题请咨询小明同学,微信geektime002。

    2019-02-07
    2
  • 虎虎❤️
    基本排序算法的关注点分为:
    1. 时间复杂度。如n的平方(冒泡,选择,插入);插入排序的优化希尔排序,则把复杂度降低到n的3/2次方;n乘以logn(快排,归并排序,堆排序)。
    2. 是否为原地排序。如,归并排序需要额外的辅助空间。
    3. 算法的稳定性。稳定排序(by nature)如冒泡,插入,归并。如果把次序考虑在内,可以把其他的排序(如快排,堆排序)也实现为稳定排序。
    4. 算法的实现。同为时间复杂度同为n平方的算法中,插入排序的效率更高。但是如果算法实现的不好,可能会降低算法的效率,甚至让稳定的算法变得不稳定。又如,快速排序有不同的实现方式,如三路快排可以更好的应对待排序数组中有大量重复元素的情况。堆排序可以通过自上而下的递归方式实现,也可以通过自下而上的方式实现。
    5. 不同算法的特点,如对于近乎有序的数组进行排序,首选插入排序,时间复杂度近乎是n,而快速排序则退化为n平方。

    二分查找,需要注意 (l+r)/2可能存在越界问题。

    leetcode题,用二分查找找到x*x > n 且(x-1)的平方小于n的数,则n-1就是结果。或者 x的平方小于n且x+1的平方大于n,则返回x。
    2019-02-07
    2
  • 失火的夏天
    牛顿法或者二分逼近都可以解决平方根问题,leetcode上有些大神的思路真的很厉害,经常醍醐灌顶
    2019-02-06
    2
  • hopeful
    #O(n)时间复杂度时间复杂度内找到一组数据的第 n大元素
    import random
    import time

    def Array(n):
        a = []
        for i in range(n):
            a.append(random.randint(0 , n))
        return a
    def QuickSort(n):
        array = Array(100)
        if n > len(array) or n < 1:
            print("超出范围,找不到")
            return
        n = n-1
        a = qsort(0 , len(array)-1 , array , n)
        print(sorted(array))
        print("-----------------------------")
        print(a)

    def qsort(start , end , array , n):
        if start == end:
            res = array[start]
        if start < end:
            key = partation(array , start , end)
            print(start , key , end)
            if key > n :
                res = qsort(start , key-1 , array , n)
            elif key < n:
                res = qsort(key+1 , end , array , n)
            else:
                res = array[key]
        return res

    def swap(array , start , end):
        temp = array[start]
        array[start] = array[end]
        array[end] = temp

    def partation(array , start , end):
        temp = array[start]
        while start < end :
            while start<end and array[end]<=temp:
                end-=1
            swap(array , start , end)
            while start<end and array[start]>=temp:
                start+=1
            swap(array , start , end)
        return start
    2019-02-16
    1
  • Monster
    /**
     * O(n)时间复杂度内求无序数组中第K大元素
     */
    public class TopK {

        public int findTopK(int[] arr, int k) {
            return findTopK(arr, 0, arr.length - 1, k);
        }

        private int findTopK(int[] arr, int left, int right, int k) {
            if (arr.length < k) {
                return -1;
            }
            int pivot = partition(arr, left, right);
            if (pivot + 1 < k) {
                findTopK(arr, pivot + 1, right, k);
            } else if (pivot + 1 > k) {
                findTopK(arr, left, pivot - 1, k);
            }
            return arr[pivot];
        }


        private int partition(int[] array, int left, int right) {
            int pivotValue = array[right];
            int i = left;

            //小于分区点放在左边 大于分区点放在右边
            for (int j = left; j < right; j++) {
                if (array[j] < pivotValue) {
                    int tmp = array[i];
                    array[i] = array[j];
                    array[j] = tmp;
                    i++;
                }
            }
            //与分区点交换
            int tmp = array[i];
            array[i] = array[right];
            array[right] = tmp;
            return i;
        }
    }

    编辑回复: 感谢您参与春节七天练的活动,为了表彰你在活动中的优秀表现,赠送您10元无门槛优惠券,我们会在3个工作日之内完成礼品发放,如有问题请咨询小明同学,微信geektime002。

    2019-02-13
    1
    1
  • EidLeung
    编程实现 O(n) 时间复杂度内找到一组数据的第 K 大元素。
    这个的时间复杂路应该是n·logk吧?
    2019-02-12
    1
  • abner
    java实现冒泡排序
    代码如下:
    package sort;

    public class BubbleSort {

        public int[] bubbleSort(int[] array) {
            for (int i = 0;i < array.length - 1;i++) {
                for (int j = 0;j < array.length - i - 1;j++) {
                    if (array[j] > array[j + 1]) {
                        int temp = array[j + 1];
                        array[j + 1] = array[j];
                        array[j] = temp;
                    }
                }
            }
            return array;
        }

        public static void main(String[] args) {
            int[] array = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
            BubbleSort bubbleSort = new BubbleSort();
            int[] result = bubbleSort.bubbleSort(array);
            for (int i = 0;i < result.length;i++) {
                System.out.print(result[i] + " ");
            }
        }

    }
    2019-02-11
    1
  • kai
    实现模糊二分查找算法2:

    public class BinarySearch {
        // 3. 查找第一个大于等于给定值的元素
        public static int bsFistGE(int[] array, int target) {
            int lo = 0;
            int hi = array.length - 1;

            while (lo <= hi) {
                int mid = lo + ((hi - lo) >> 1);

                if (array[mid] >= target) {
                    if (mid == 0 || array[mid-1] < target) {
                        return mid;
                    } else {
                        hi = mid - 1;
                    }
                } else {
                    lo = mid + 1;
                }
            }

            return -1;
        }

        // 4. 查找最后一个小于等于给定值的元素
        public static int bsLastLE(int[] array, int target) {
            int lo = 0;
            int hi = array.length - 1;

            while (lo <= hi) {
                int mid = lo + ((hi - lo) >> 1);

                if (array[mid] <= target) {
                    if (mid == hi || array[mid+1] > target) {
                        return mid;
                    } else {
                        lo = mid + 1;
                    }
                } else {
                    hi = mid - 1;
                }
            }

            return -1;
        }
    }
    2019-02-11
    1
  • kai
    实现模糊二分查找算法1:

    public class BinarySearch {
        
        // 1. 查找第一个值等于给定值的元素
        public static int bsFirst(int[] array, int target) {
            int lo = 0;
            int hi = array.length - 1;

            while (lo <= hi) {
                int mid = lo + ((hi - lo) >> 1);

                if (array[mid] > target) {
                    hi = mid - 1;
                } else if (array[mid] < target) {
                    lo = mid + 1;
                } else {
                    if (mid == lo || array[mid-1] != array[mid]) {
                        return mid;
                    } else {
                        hi = mid - 1;
                    }
                }
            }

            return -1;
        }

        // 2. 查找最后一个值等于给定值的元素
        public static int bsLast(int[] array, int target) {
            int lo = 0;
            int hi = array.length - 1;

            while (lo <= hi) {
                int mid = lo + ((hi - lo) >> 1);

                if (array[mid] > target) {
                    hi = mid - 1;
                } else if (array[mid] < target) {
                    lo = mid + 1;
                } else {
                    if (mid == hi || array[mid] != array[mid+1]) {
                        return mid;
                    } else {
                        lo = mid + 1;
                    }
                }
            }

            return -1;
        }
    }
    2019-02-11
    1
  • kai
    实现一个有序数组的二分查找算法:

    public class BinarySearch {
        // 最简单的二分查找算法:针对有序无重复元素数组
        // 迭代
        public static int binarySearch(int[] array, int target) {
            if (array == null) return -1;

            int lo = 0;
            int hi = array.length-1; // 始终在[lo, hi]范围内查找target

            while (lo <= hi) {
                int mid = lo + ((hi - lo) >> 1); // 这里若是 (lo + hi) / 2 有可能造成整型溢出

                if (array[mid] > target) {
                    hi = mid - 1;
                } else if (array[mid] < target) {
                    lo = mid + 1;
                } else {
                    return mid;
                }
            }

            return -1;
        }

        // 递归
        public static int binarySearchRecur(int[] array, int target) {
            if (array == null) return -1;
            return bs(array, target, 0, array.length-1);
        }

        private static int bs(int[] array, int target, int lo, int hi) {
            if (lo <= hi) {
                int mid = lo + ((hi - lo) >> 1);
                if (array[mid] > target) {
                    return bs(array, target, lo, mid-1);
                } else if (array[mid] < target) {
                    return bs(array, target, mid+1, hi);
                } else {
                    return mid;
                }
            }

            return -1;
        }
    }
    2019-02-11
    1
  • 纯洁的憎恶
    这道题似乎可以等价于从1到x中找到一个数y,使得y*y小于等于x,且(y+1)*(y+1)大于x。那么可以从1到x逐个尝试,提高效率可以采用二分查找方法,时间复杂度为O(logx)。
    2019-02-09
    1
  • 黄丹
    王争老师初三快乐!
    这是今天两道题的解题思路和代码
    1. O(n)时间内找到第K大的元素:
    解题思路:利用快排中分区的思想,选择数组区间A[0...n-1]的左右一个元素A[n-1]作为pivot,对数组A[0...n-1]原地分区,这样数组就分成了三部分,A[0..p-1],A[p],A[p+1...n-1],如果p+1=k,那么A[p]就是要求解的元素,如果K>p+1,则说明第K大的元素在A[p+1...n-1]这个区间,否则在A[0...p-1]这个区间,递归的查找第K大的元素
    2. Sqrt(x) (x 的平方根)
    解题思路:利用二分查找的思想,从1到x查找x的近似平方根
    代码:
    https://github.com/yyxd/leetcode/blob/master/src/leetcode/sort/Problem69_Sqrt.java
    2019-02-07
    1
  • C_love
    Use Binary Search

    class Solution {
        public int mySqrt(int x) {
            if (x == 0 || x == 1) {
                return x;
            }
            
            int start = 0;
            int end = (x >> 1) + 1;
            
            while (start + 1 < end) {
                final int mid = start + ((end - start) >> 1);
                final int quotient = x / mid;
                if (quotient == mid) {
                    return mid;
                } else if (quotient < mid) {
                    end = mid;
                } else {
                    start = mid;
                }
            }
            
            return start;
        }
    }

    编辑回复: 感谢您参与春节七天练的活动,为了表彰你在活动中的优秀表现,赠送您99元专栏通用阅码,我们会在3个工作日之内完成礼品发放,如有问题请咨询小明同学,微信geektime002。

    2019-02-07
    1
  • Geek_86533a
    不断学习,不断练习到今天。发现自己的代码能力、思考问题的能力有了明显的进步。感谢!
    2019-08-14
  • 懒猫
    打卡
    2019-05-23
  • hopeful
    #二分查找变种
    import random
    import time

    def Array(n):
        a = []
        for i in range(n):
            a.append(random.randint(0 , n))
        return a
    #查找第一个值等于给定值的元素
    def find_1(n):
        array = Array(100)
        array = sorted(array)
        left = 0
        right = len(array)-1
        while left <= right:
            mid = int((left+right)/2)
            if array[mid] > n:
                right = mid - 1
            elif array[mid] < n:
                left = mid + 1
            else:
                if mid==0 or array[mid] != array[mid-1]:
                    return mid
                else:
                    right = mid - 1
        print("找不到")
        return -1

    #查找最后一个值等于给定值的元素
    def find_2(n):
        array = Array(100)
        array = sorted(array)
        left = 0
        right = len(array)-1
        while left <= right:
            mid = int((left+right)/2)
            if array[mid] > n:
                right = mid - 1
            elif array[mid] < n:
                left = mid + 1
            else:
                if mid==right or array[mid] != array[mid+1]:
                    return mid
                else:
                    left = mid + 1
        print("找不到")
        return -1

    #查找第一个值大于等于给定值的元素
    def find_3(n):
        array = Array(100)
        array = sorted(array)
        left = 0
        right = len(array)-1
        while left <= right:
            mid = int((left+right)/2)
            if array[mid] >= n:
                if mid==0 or array[mid-1]<n:
                    return mid
                else:
                    right = mid - 1
            else array[mid] < n:
                left = mid + 1
        print("找不到")
        return -1

    #查找最后一个值小于等于给定值的元素
    def find_4(n):
        array = Array(100)
        array = sorted(array)
        left = 0
        right = len(array)-1
        while left <= right:
            mid = int((left+right)/2)
            if array[mid] <= n:
                if mid==right or array[mid+1]>n:
                    return mid
                else:
                    left = mid + 1
            else array[mid] > n:
                right = mid - 1
        print("找不到")
        return -1
    2019-02-17
  • hopeful
    #实现一个有序数组的二分查找算法
    import random
    import time

    def Array(n):
        a = []
        for i in range(n):
            a.append(random.randint(0 , n))
        return a

    def find(n):
        array = Array(100)
        array = sorted(array)
        left = 0
        right = len(array)-1
        while left <= right:
            mid = int((left+right)/2)
            if array[mid] > n:
                right = mid - 1
            elif array[mid] < n:
                left = mid + 1
            else:
                return mid
        print("找不到")
        return -1
    2019-02-16
  • 拉欧
    x 的平方根 go 语言实现
    func mySqrt(x int) int{

    if x==0{
    return 0
    }
    min:=1
    max:=x

    for {
    mid:=min+(max-min)/2
    if mid*mid==x{
    return mid
    }else if mid*mid<x{
    if (mid+1)*(mid+1)>x{
    return mid
    }else{
    min=mid+1
    }
    }else{
    max=mid-1
    }

    }
    }
    2019-02-15
  • TryTs
    #include<iostream>
    #include<cmath>
    using namespace std;
    double a = 1e-6;
    double sqrt(double n){
    double low = 0.0;
    double high = n;

    int i = 1000;

    while(i--){
    double mid = low + (high - low) / 2.0;
    //cout<<"n:"<<n<<endl;
    double square = mid * mid;
    //cout<<"sq:"<<square<<endl;
    //cout<<"s:"<<abs(square - n)<<endl;
    if(abs(mid * mid - n) < a){
    return mid;
    }
    else{

    if(square > n){
    high = mid;
    }
    else{
    low = mid;
    }
    }
    }
    return -2.0;
    }
    int main(){
    double t;
    while(true){
    cin>>t;
    cout<<sqrt(t)<<endl;
    }
    }
    2019-02-14
收起评论
29
返回
顶部