美文网首页
算法实现——二分法查找、选择排序、快速排序、冒泡排序

算法实现——二分法查找、选择排序、快速排序、冒泡排序

作者: 生信小书童 | 来源:发表于2021-06-05 23:19 被阅读0次

    上篇文章介绍了大O表示方法和5种常见算法的大O表示时间,本篇文章主要对二分法查找、选择排序、快速排序算法进行了实现。

    1 二分法查找

    二分法查找是一种速度非常快的算法,但是它有固定的应用范围。仅当列表是有序的时候,二分查找才管用。例如,电话簿中的名字是按照顺序排列的,因此可以使用二分查找来找名字。二分法查找需要执行log n 次操作,大O表示法为 O(log n)。
    算法问题描述:
    函数binary_search接受一个有序数组和元素。如果指定的元素包含在数组中,如何编写函数binary_search返回元素的位置。
    算法实现:
    二分查找每次都检查中间元素,比较中间元素与查询元素的大小,不断缩小查询区域

    #二分法查找(python代码)
    def binary_search(list,item):
        low = 0
        high = len(list) -1 
        while low <= high:
            mid = (low + high)/2
            guess = list[mid]
            if guess == item:
                return mid
            if guess > item:
                high = mid - 1
            else:
                low = mid + 1
        return None
    
    my_list = [1,3,5,7,9] 
    print binary_search(my_list,3)
    1 #返回值
    print binary_search(my_list,-1) 
    None #返回值   
    

    2 选择排序

    有很多算法只有经过排序后的数据才能使用,例如上部分介绍的二分法查找。排序是最基础、最重要的算法之一,很多编程语言都内置了排序算法,基本上不需要你从头开始编写自己的版本。但是,对基础排序算法的学习是掌握其他重要算法的基础。本部分介绍的选择排序算法就是一种最简单的排序算法。选择性排序需要执行n+(n-1)+(n-2)+...+2+1次操作,大O表示法为O(n2).
    算法问题描述:
    如下图所示,假设计算机存储了很多乐曲。对于每个乐队,你都记录了其作品被播放的次数。你需要写一个选择排序算法按照乐队播放的次数进行排序,从而选择出你最喜欢的乐队。

    image.png
    算法实现:
    选择排序算法会重复的遍历列表,找出作品播放次数最终的乐队,将其加入到一个新列表中,并将其从原始的列表中删除。
    #选择排序(python代码)
    #选择列表中最小元素的函数
    def findSmallest(arr):
        smallest = arr[0]
        smallest_index = 0
        for i in range(1,len(arr)):
            if arr[i] < smallest:
                smallest = arr[i]
                smallest_index = i
        return smallest_index
    #对输入列表进行排序
    def selectionSort(arr):
        newArr = []
        for i in range(len(arr)):
            smallest = findSmallest(arr)
            newArr.append(arr.pop(smallest))
        return newArr
    
    print selectionSort([5,3,6,3,6,2,1])
    [1, 2, 3, 3, 5, 6, 6] #返回值
    

    3 快速排序

    选择排序的大O表示法为O(n2),快速排序排序的大O表示法为O(n log n)。快速排序的速度是选择排序的n/logn倍。快速排序主要是应用了分而治之(divide and conquer, D&C)——一种著名的递归式的问题解决方法。
    使用 D&C 解决问题主要包括两个步骤:
    (1)找出基线条件,这种基线条件必须尽可能的简单。(注意:递归函数的基线条件通常是数组为空或者只包含一个元素)
    (2)不断将问题分解(或者说缩小规模),直到符合基线条件。
    算法问题描述:
    函数 quicksort 接受一个无序列表。如何编写函数 quicksort 对列表中的元素进行快速排序。
    算法实现:
    快速排序 D&C 策略(如下图所示):
    1 、快速排序的基线——列表为空或者只有一个元素的列表是天然“有序”的列表
    2、快速排序问题分解:(1)选择基准值(2)将数组分成两个子列表:小于基准值的列表和大于基准值的列表(3)对两个子列表再进行快速排序

    image.png
    快速排序的代码还是比较优雅的!
    #快速排序(python代码)
    def quicksort(array):
        if len(array) < 2:
            return array #基线条件
        else:
            #递归条件
            pivot = array[0] #选取基准值
            less = [i for i in array[1:] if i <= pivot]
            greater = [i for i in array[1:] if i > pivot]
            return quicksort(less) + [pivot] + quicksort(greater)
    print quicksort([2,3,6,8,1,2])
    [1, 2, 2, 3, 6, 8] #返回值
    

    4 冒泡排序

    冒泡排序和选择排序的思路比较类似,大O表示法为O(n2)。它的思路为:
    1、比较相邻的元素,如果第一个比第二个大,就交换他们两个
    2、对每一对儿相邻的元素做同样的工作,执行完毕后,找到第一个最大值
    3、重复以上的步骤,每次比较次数 - 1,直到不需要比较

    //冒泡排序 C++代码
    #include <iostream>
    #include <string>
    using namespace std;
    
    int main()
    {
        int arr[] = { 4,2,8,0,5,7,3,9 };
        //总共排序的轮数为:元素个数 - 1
        for (int i = 0; i < 9 - 1; i++) {
            //内层循环次数:元素个数 - 当前轮数 -1
            for (int j = 0; j < 9 - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
        for (int i = 0; i < 9; i++) {
            cout << arr[i] << endl;
        }
    }
    

    参考资料

    1、《算法图解》

    相关文章

      网友评论

          本文标题:算法实现——二分法查找、选择排序、快速排序、冒泡排序

          本文链接:https://www.haomeiwen.com/subject/adjfeltx.html