func Search(nums []int, target int) int {
    left:=0
    right:=len(nums)-1
    for ;left<=right;{
         middle:=(left+right)/2//更新middle，取整操作
         if target>nums[middle]{
             left=middle+1//更新left
         }else if target<nums[middle]{
             right=middle-1//更新right
         }else{    
         return middle
         }
    }
    return -1
}

第二种写法(左闭右闭)：

区间为[left,right)，所以需要注意以下两个点：

1 2	循环条件使用while(left<right) 因为更新前的nums[middle]是大于target的，,并且由于当前区间是[left,right)所以需要right=middle

代码如下：

func Search(nums []int, target int) int {
    left:=0
    right:=len(nums)//区间[left,right)
    for ;left<right;{
         middle:=(left+right)/2//更新middle,取整操作
         if target>nums[middle]{
             left=middle+1//更新left
         }else if target<nums[middle]{
             right=middle//更新right
         }else{    
         return middle
         }
    }
    return -1
}

总结：二分法最重要的两个点，就是循环条件和后续区间赋值问题

参考：

https://blog.csdn.net/qq_45978890/article/details/116094046

冒泡排序算法–时间复杂度O(n2)–稳定算法

算法原理

比较相邻的元素，如果第一个比第二个大，就交换他们两个;
对每一对相邻元素左同样的工作，从开始第一对到结尾最后一对;
针对所有的元素重复以上的步骤，除了最后一个;
重复步骤1~3，直到排序完成.

注意：

1
2

1.针对所有元素重复交换步骤，除了最后一个，所以外层循环次数应该是len(nums)-1 
2.每一次最外层循环完向右移动一位时内层循环也相应需要向右移动一位，并且每一次内层循环需要从外层循环的右边一个位置开始,所以每次初始化内存循环为内存右边以外一位开始，循环次数为数组长度len(arrs)-1-i(外层开始点位)

代码如下:

func BubbleSort(arrs *[]int) arrs []int{
    for i:=0;i<len(*arrs)-1;i++{
        for j:=i+1;j<len(*arrs)-1-i;j++{
            if arr[j]>arr[j+1]{
                arr[j],arr[j+1]=arr[j+1],arr[j]
        }
    }
}

选择排序–时间复杂度O(n2)–稳定算法

算法原理

在未排序序列中找到最小(大)元素，存放到排序序列的起始位置，然后再从剩余未排序元素中继续寻找最小(大)元素，然后放到已排序序列的末尾，以此类推
初始状态：无序区未arr[1,n],有序区为空
第i趟排序，当前有序区和无序区分别为R[1,…,i-1]和R(i,…,n),在无序区中依次比较交换，选出i位置应该最小或者最大的值，这样有序区记录个数增加一个，无序区记录格式减少一个
n-1趟结束，数组变为有序化数组

注意：

1 2	1.外层有序点位只需要到n-2的位置，最后一个点位在n-2排序后就是最佳 2.内层循环需要从外层循环点位的下一位开始

代码如下(以递增排序为例)：

func SelectionSort(arr []int){
    for i:=0;i<len(arr)-1;i++{
        minIndex:=i
        for j:=i+1;j<len(arr);j++{
            if arr[j]<arr[minIndex]{ //小于-->算法稳定;小于等于算法不稳定
                minIndex=j//点位交换，在内层循环内
            }
        }
        arr[i],arr[minIndex]=arr[minIndex],arr[i]//值交换在外层循环内，内层循环外
    }
}

(直接)插入排序–时间复杂度O(n2)–稳定算法

算法原理

将待排序的数组分成已排序和未排序两部分，初始的时候把第一个元素认为是已经排好序的
从第二个元素开始，在已排好的的部分数组中找到适合该元素的位置并且插入
重复以上步骤，知道最后一个元素插入有序数组部分

注意：

1	因为默认数组第一个元素为有序数组部分，所以插入元素应该从数组第二位开始，即外层循环从数组第二位开始

代码如下(go)：

func InsertSort(arr []int){
    for i:=1;i<len(arr);i++{
        j:=i
        for ;j>0;{
            if arr[j]<arr[j-1]{
                arr[j],arr[j-1]=arr[j-1],arr[j]
                j-=1
            }else{
                break
        }
    }
}

归并排序(分治法)–时间复杂度O(n)

算法原理

把长度为n的输入序列分成两个长度为n/2的子序列
对这两个子序列分别采用重复步骤一至不可再分；
将已排好序的子序列重新向上合并成一个完整的有序序列

代码如下(go)

//归并算法：将两个已经有序的子序列归并为一个有序的序列
func merge(left,right []int) []int{
    result:=make([]int,0)//
    i,j:=0,0 //左序列和右序列的初始位置
    for i<len(left)&&j<len(right){
        if left[i]<right[j]{
            result=append(result,left[i])
            i+=1
            continue
        }
        result=append(result,right[j])
        j+=1
    }
    
    result=append(result,left[i:]...)
    result=append(result,right[j:]...)
    return result
}

func MergeSort(arr []int) []int{
     if len(arr)<2{
        return arr
     }else{
        i:=len(arr)/2
        left:=MergeSort(arr[0:i])
        right:=MergeSort(arr[i:])
        result:=merge(left,right)
        return right
     }
}

#####################################################

快速排序(分治法)–算法复杂度O(nlogn)

算法原理

分解：先给定一个基准p(pivot)，然后根据基准p将数组arr[l,r]分区(partition),即划分为两个（可能为空）子数组A[l…p-1]和A[p+1…r]，使得A[l…p-1]中的每个元素小于等于A[p]，A[p+1…r]中的每个元素大于等于A[p]，q下标是在划分过程中计算得出的
解决：通过递归的(recursive)调用快速排序，对小于基准元素的子数组A[l…p-1]和大于基准元素的子数组A[p+1…r]进行排序
合并：因为两个子数组是就地排序，不需要合并操作，整个数组A[l…r]排序完成

注意：

1	基准点和基准值：基准点以该点左边是小于此点的值的元素值，基准值是数值与位置信息无关

代码如下：

func QuickSort(arr []int,l int,r int){
    if l<r{
        p:=partition(arr,l,r)//基准点
        partition(arr,l,p-1)//分区
        partition(arr,p+1,r)
    }
}

func partition(arr []int, l int, r int)int{
    key:=arr[r]//以right位置上的值为基准值
    i:=l
    j:=l
    for j<r{//j需要经过基准点前的所有数组元素。
        if arr[j]<key{
            arr[i],arr[j]=arr[j],arr[i]
            i+=1
        }
        j+=1
    }
    arr[i],arr[r]=arr[r],arr[i]
    return i//基准点
}

希尔排序–平均算法复杂度O(nlogn)–不稳定

算法原理

每一趟排序都需要首先定义一个增量(步长),如果起始增量(步长)定义为gap=length/2(这个增量称为希尔增量，当然增量长度可以自己定义)，那么这里每一趟的增量可以用一个序列来表示：{gap/2,(gap/2)/2,…,1}
每一趟的增量那么将整个数组分为这个增量大小的数组，然后对每一组分别进行直接插入排序，小的元素被调换到前面，然后缩小增量进行下一趟的排序
直到增量缩小到1时，最后对序列进行调整，整个数组排序完成

注意

1	数组元素个数是偶数或者奇数不影响

代码如下：

func ShellSort(arr []int) []int{
    gap:=len(arr)/2 //定义增量(步长)，向下取整
    for gap>0{ //gap等于1的时候是最后一次调整
        for i:=0;i<len(arr);i++{
            j:=i
            for ((j-gap>0) && (arr[j]<arr[j-gap])){
                arr[j],arr[j-gap]=arr[j-gap],arr[j] //交换
                j-=gap //跳出这一层while循环-->关键点
            }
       }
       gap/=2 //每一趟过后gap更新
    }
    return arr
}

Cofeesy的博客

简单算法

目录

二分算法–时间复杂度O(logn)

二分算法不用纠结数组长度是奇数还是偶数(因为中间的数字两边的数字不一样)，只需要记住：

第一种写法(左闭右闭)；

具体代码(go)：

第二种写法(左闭右闭)：

代码如下：

总结：二分法最重要的两个点，就是循环条件和后续区间赋值问题

参考：

冒泡排序算法–时间复杂度O(n2)–稳定算法

算法原理

注意：

代码如下:

选择排序–时间复杂度O(n2)–稳定算法

算法原理

注意：

代码如下(以递增排序为例)：

(直接)插入排序–时间复杂度O(n2)–稳定算法

算法原理

注意：

代码如下(go)：

归并排序(分治法)–时间复杂度O(n)

算法原理

代码如下(go)

快速排序(分治法)–算法复杂度O(nlogn)

算法原理

注意：

代码如下：

希尔排序–平均算法复杂度O(nlogn)–不稳定

算法原理

注意

代码如下：