二分查找

特点

时间复杂度：logN

基于有序排序

思路

1、双指针，折半查找。

问题

整体相加溢出问题
left + right可能会出现整数溢出问题

• left + (right - left)/2
• 移位运算(正数) (left + right)>>>1

查看遍历的次数

{1, 5, 8, 11, 19, 22, 31, 35, 40, 45, 48, 49, 50}

找到 48 需要遍历几次 -- 4次

31(1) -> 35 -- 45(2) -> 48 -- 49(3) -> 48 -- 48(4) 此时48满足条件 结束

代码实现

package com.zmz.datastructure;

/**
 * @author 张明泽
 * Create by 2022/5/10 21:54
 * 二分查找
 */
public class BinaryLookUp {
    public static void main(String[] args) {
        int[] arr = {1, 5, 8, 11, 19, 22, 31, 35, 40, 45, 48, 49, 50};
        int target = 48;
        int index = binaryLookUp(arr, target);
        System.out.println(index);
    }
    public static int binaryLookUp(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;
        while(left <= right) {
            int mid = (left + right)>>>1;
            if(arr[mid] == target) {
                return mid;
            } else if (arr[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return -1;
    }
}

冒泡排序

特点

时间复杂度：N²

稳定排序算法

思路

1、依次比较相邻的元素。如果第一个比第二个大，就交换他们两个。

问题

循环次数问题，因为每次比较当当前元素和最后一个元素，所以最后一个元素不需要比较 length - 1

优化

• 设置个是否交换的变量
• 设置两个变量，监听最后交换的索引下标

代码实现

package com.zmz.datastructure;

import java.util.Arrays;

/**
 * @author 张明泽
 * Create by 2022/5/12 12:28
 * 冒泡排序
 */
public class BubbleSort {
    public static void main(String[] args) {
        int[] arr = { 4, 7, 1, 11, 19, 18 ,13 };
        bubble(arr);
    }
    public static void bubble(int[] arr) {
        for(int i = 0; i < arr.length - 1; i++) {
            for(int j = 0; j < arr.length - 1 - i; j++) {
                if(arr[j] > arr[j+1]) {
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
        }
        System.out.println(Arrays.toString(arr));
    }
}

选择排序

特点

时间复杂度：N²

不稳定排序算法

思路

1、循环数组，在每一次循环时找到比当前元素更小的值的索引并交换数据

问题

循环次数问题，最后一个元素是需要被比较的 length

package com.zmz.datastructure;

import java.util.Arrays;

/**
 * @author 张明泽
 * Create by 2022/5/12 22:28
 * 选择排序
 */
public class ChooseSort {
    public static void main(String[] args) {
        int arr[] = { 4, 7, 1, 8, 2, 9, 5, 10, 6, 3 };
        choose(arr);
    }
    public static void choose(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            int min = i;
            for (int j = i + 1; j < arr.length; j++) {
                if(arr[j] < arr[min]) {
                    min = j;
                }
            }
            int temp = arr[min];
            arr[min] = arr[i];
            arr[i] = temp;
        }
        System.out.println(Arrays.toString(arr));
    }
}

插入排序

特点

时间复杂度：N²

稳定排序算法

思路

1、循环从第一个元素开始，并记录该元素为 A。

2、记录A的下标 - 1，依次往回退，比较元素大小，一旦小将该元素向右赋值(移动)

3、一旦比元素大或相等，则退出循环。

4、将 A 赋值给停止的下标 + 1 的元素

代码实现

package com.zmz.datastructure;

import java.util.Arrays;

/**
 * @author 张明泽
 * Create by 2022/5/13 10:22
 * 插入排序
 */
public class InsertSort {
    public static void main(String[] args) {
        int[] arr = { 4, 7, 1, 11, 19, 18 ,13 };
        insert(arr);
    }
    public static void insert(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int temp = arr[i]; // 当前要插入的值
            int t = i - 1; // 插入的前一个元素
            while(t >= 0) {
                if(arr[t] > temp) {
                    arr[t+1] = arr[t];
                } else {
                    break;
                }
                t--;
            }
            arr[t+1] = temp;
        }
        System.out.println(Arrays.toString(arr));
    }
}

希尔排序

特点

时间复杂度：nlogN

不稳定排序算法

思路

1、将数组按照增量 d 分割，分别进入插入排序。

2、将 d 缩小，继续直接插入排序

实现代码

package com.zmz.datastructure;

import java.util.Arrays;

/**
 * @author 张明泽
 * Create by 2022/8/28 21:17
 * 希尔排序
 */
public class ShellSort {
    public static void main(String[] args) {
        int[] arr = { 4, 7, 1, 11, 19, 18 ,13 };
        shellSort(arr);
    }
    public static void shellSort(int[] arr) {
        for (int gap = arr.length / 2; gap > 0; gap /= 2) {
            for (int j = 0; j < gap; j++) {
                for (int i = j + gap; i < arr.length; i +=gap) {
                    int temp = arr[i]; 
                    int t = i - gap;
                    while (t >= 0) {
                        if (arr[t] > temp) {
                            arr[t + gap] = arr[t];
                        }
                        else {
                            break;
                        }
                        t -=gap;
                    }
                    arr[t + gap] = temp;
                }
            }
        }
        System.out.println(Arrays.toString(arr));
    }
}

快速排序

特点

时间复杂度：nlogN

不稳定排序算法

思路

1、快速排序使用分治法策略来把一个串行分为两个子串行。

2、递归调用,双边循环,以第一个元素作为基准点pv,两个指针 r 和 l 。

3、每次将基准点pv移动到数组中排序后的正常位置，并将pv左边的数都比它小，右面的数都比它大。

问题

• 内循环还要加上 l<r 条件,否则可能会停不下来退不出外循环

• l 的条件要有 = ,刚开始 pv = arr[l] 不会走

  • 要先执行 r ,在执行 l

代码实现

package com.zmz.datastructure;

import java.util.Arrays;

/**
 * @author 张明泽
 * Create by 2022/5/13 14:54
 */
public class QuickSort {
    public static void main(String[] args) {
        int[] arr = { 4, 7, 22, 1, 24, 11, 19, 18 ,13, 23, 20 };
        quick(arr, 0 , arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }
    public static void quick(int[] arr, int left, int right) {
        if(left >= right) {
            return;
        }
        int pv = quicksort2(arr,left,right);
        // 左
        quick(arr,left,pv - 1);
        // 右
        quick(arr, pv + 1, right);
    }

    public static int quicksort2(int[] arr, int left, int right) {
        int pv = arr[left];
        int l = left;
        int r = right;
        while (l < r) {
            while ( l < r && arr[r] > pv) {
                r--;
            }
            while ( l < r && arr[l] <= pv) {
                l++;
            }
            int temp = arr[l];
            arr[l] = arr[r];
            arr[r] = temp;
        }
        int temp = arr[left];
        arr[left] = arr[r];
        arr[r] = temp;
        return r;
    }
}

归并排序

特点

时间复杂度：nlogN

稳定排序算法

思路

1、分治思想。

2、利用递归将数组一直一分为二。

3、将两个数组利用一个新数组将其合并排序，在赋值回去。

实现代码

package com.zmz.datastructure;

import java.util.Arrays;

/**
 * @author 张明泽
 * Create by 2022/5/18 11:54
 * 归并排序
 */
public class MergeSort {
    public static void main(String[] args) {
        int[] arr = { 4, 7, 1, 11, 19, 18 ,13 };
        merge(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }
    public static void merge(int[] arr, int left, int right) {
        if(left == right) {
            return;
        }
        int mid = left + ((right - left) >>> 1);
        merge(arr, left, mid);
        merge(arr, mid + 1, right);
        sort(arr,left,mid,right);
    }
    public static void sort(int[] arr, int left, int mid, int right) {
        // 注意新数组的范围
        int[] help = new int[right - left + 1];
        int i = 0;
        int p1 = left;
        int p2 = mid + 1;
        while ( p1 <= mid && p2 <= right) {
            help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
        }
        while (p1 <= mid) {
            help[i++] = arr[p1++];
        }
        while (p2 <= right) {
            help[i++] = arr[p2++];
        }
        // 替换是把新数组替换到原数组中(不是arr的长度！)
        for (int j = 0; j < help.length; j++) {
            // 要带上left
            arr[j + left] = help[j];
        }
    }
}

堆排序

特点

时间复杂度：nlogN

不稳定排序算法

思路

大顶堆是每个节点都比子节点大，用来升序！

小顶堆是每个节点都比子节点小，用来降序！

计数排序

特点

时间复杂度： n+k

空间复杂度： n+k

稳定排序算法

思路

1、必须要有确定的范围。

2、用一个计数数组来维护数组元素的个数 索引为值，元素值为出现的次数。

3、遍历计数数组。

桶排序

特点

时间复杂度： n+k

空间复杂度： n+k

稳定排序算法

思路

1、将待排序序列中的元素根据规则分组。

2、每一组采用快排、插入排序等算法进行排序，然后再按照次序将所有元素合并。

3、就可以得到一个有序序列。

基数排序

特点

• MSD：先从高位开始进行排序，在每个关键字上，可采用计数排序
• LSD：先从低位开始进行排序，在每个关键字上，可采用桶排序

思路

1、LSD：先看个位，十位，千位。

2、桶中若有多个元素，按照先进先出的原则。

稳定的排序算法：冒泡排序、插入排序、归并排序和基数排序。

不是稳定的排序算法：选择排序、快速排序、希尔排序、堆排序。