[数据结构与算法]数据结构：第二章（二）

视频链接：https://www.bilibili.com/video/BV1HQ4y1d7th

视频范围P65 - P86

1.冒泡排序

思想：通过对待排序序列从前往后依次比较相邻元素值，若发现逆序则交换，使值较大的元素从前逐步移向后面，就像水中气泡

package sort;

import java.util.Arrays;

public class BubblingSort {
    public static void main(String[] args) {
        int[] arrays = new int[]{4,5,6,3,2,1};

        //第一层for循环控制行数
        for (int i = 0; i < arrays.length - 1; i++) {
            //控制比较次数
            for (int j = 0; j < arrays.length - 1 - i; j++) {
                if (arrays[j] > arrays[j + 1]){
                    int temp = 0;
                    temp = arrays[j];
                    arrays[j] = arrays[j + 1];
                    arrays[j + 1] = temp;
                }
            }
        }

        System.out.println(Arrays.toString(arrays));//输出为：[1, 2, 3, 4, 5, 6]
    }
}

2.快速排序

1. 快速排序是对冒泡排序的一种改进。
2. 通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另一部分所有的数据都要小,然后再按此方法对这两部分数据分别进行快速排序
3. 整个排序过程可以递归进行，以此达到整个数据变成有序序列

思想演示图：

package sort;

import java.util.Arrays;

public class QuickSort {
    public static void main(String[] args) {
        int[] arrays = new int[]{2,9,4,7,3,3,6,5};

        sort(arrays,0,arrays.length - 1);
        System.out.println(Arrays.toString(arrays));//输出为：[2, 3, 3, 4, 5, 6, 7, 9]
    }

    public static void sort(int[] arrays,int left,int right){
        int l = left;
        int r = right;

        int pivot  = arrays[(l + r) / 2];

        int temp = 0;
        while (l < r){
            //在左边查找小于中间值的
            while (arrays[l] < pivot){
                l++;
            }

            //在右边查找大于中间值的
            while (arrays[r] > pivot){
                r--;
            }

            if (l >= r){
                break;
            }

            //交换变量
            temp = arrays[l];
            arrays[l] = arrays[r];
            arrays[r] = temp;

            //特殊情况
            if (arrays[l] == pivot){
                r--;
            }

            if (arrays[r] == pivot){
                l++;
            }

            if (r == l){
                l++;
                r--;
            }

            if (left < r){
                sort(arrays,left,r);
            }

            if (right > l){
                sort(arrays,l,right);
            }
        }
    }
}

3.插入排序

插入排序属于内部排序，是对于排序的元素以插入的方式寻找该元素的适当位置，以达到排序的目的。

package sort;

import java.util.Arrays;

public class InsertSort {
    public static void main(String[] args) {

        int[] arrays = new int[]{2,5,6,3,4,7,8};

        //获取每一个元素
        for (int i = 1; i < arrays.length; i++) {
            //比较次数
            for (int j = i; j >= 1 ; j--) {
                if (arrays[j] < arrays[j - 1]){
                    int temp = 0;
                    temp = arrays[j];
                    arrays[j] = arrays[j - 1];
                    arrays[j - 1] = temp;
                }else {
                    break;
                }
            }
        }
        System.out.println(Arrays.toString(arrays));//输出为：[2, 3, 4, 5, 6, 7, 8]
    }
}

4.选择排序

选择排序也属于内部排序法，是从欲排序的数据中按指定的规则选择某一个元素，再以规则交换位置后达到的排序目的。

package sort;

import java.util.Arrays;

public class SelectSort {
    public static void main(String[] args) {
        int[] arrays = new int[]{3,2,4,5,6,8,7,1};

        for (int i = 0; i < arrays.length; i++) {
            for (int j = arrays.length - 1; j > i; j--) {
                if (arrays[j] < arrays[i]){
                    int temp = 0;
                    temp = arrays[j];
                    arrays[j] = arrays[i];
                    arrays[i] = temp;
                }
            }
        }
        System.out.println(Arrays.toString(arrays));//输出为：[1, 2, 3, 4, 5, 6, 7, 8]
    }
}

5.希尔排序

1. 希尔排序(Shell’s Sort)是插入排序的一种，又称“缩小增量排序”(Diminishing IncrementSort)是插入排序算法的一种更高效的改进版本，该方法因D.L.Shell于1959年提出而得名
2. 希尔排序是非稳定排序算法
3. 希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序;随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

package sort;

import java.util.Arrays;

public class ShellSort {
    public static void main(String[] args) {
        int[] arrays = new int[]{1,5,9,7,2,6,0,3,8,4};

        //实现增量的变化
        for (int gap = arrays.length / 2; gap > 0 ; gap /= 2) {
            for (int i = gap; i < arrays.length; i++) {
                for (int j = i - gap; j >= 0; j -= gap) {
                    if (arrays[j] > arrays[j + gap]){
                        int temp = 0;
                        temp = arrays[j];
                        arrays[j] = arrays[j + gap];
                        arrays[j + gap] = temp;
                    }
                }
            }
        }
        System.out.println(Arrays.toString(arrays));//输出为：[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
    }
}

6.归并排序

1. 归并排序（Merge Sort）是建立在归并操作上的一种有效，稳定的排序算法
2. 该算法是采用分治法（Divide and Conquer）的一个非常典型的应用
3. 将已有序的子序列合并，得到完全有序的序列;即先使每个子序列有序，再使子序列段间有序
4. 若将两个有序表合并成一个有序表，称为二路归并。

 package sort;

import java.lang.reflect.Array;
import java.util.Arrays;

public class MSort {
    public static void main(String[] args) {
        int[] array = new int[]{6,9,4,7,1,2,0,5,3,8};
        //临时数组
        int[] temp = new int[array.length];

        sort(array,0,array.length - 1,temp);

        System.out.println(Arrays.toString(array));//输出为：[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

    }

    public static void sort(int[] array,int left,int right,int[] temp){
        if (left < right){
            //求出中间值
            int mid = (left + right) / 2;

            //向左边分解
            sort(array,left,mid,temp);

            //向右边分解
            sort(array,mid + 1,right,temp);

            //合并数据
            sum(array,left,right,mid,temp);
        }
    }

    //合并数据
    public static void sum(int[] array,int left,int right,int mid,int[] temp){
        int i = left;
        int j = mid + 1;

        //指向临时数组下标
        int t = 0;

        //开始循环比较左右两边数组元素
        while (i <= mid && j <= right){
            if (array[i] <= array[j]){
                temp[t] = array[i];
                t++;
                i++;
            }else {
                temp[t] = array[j];
                t++;
                j++;
            }
        }

        //把剩余的元素直接存放在临时数组中
        while (i <= mid){
            temp[t] = array[i];
            t++;
            i++;
        }

        while (j <= right){
            temp[t] = array[j];
            t++;
            j++;
        }

        //将临时数组中的元素拷贝到原数组中
        int tempIndex = left;
        int k = 0;
        while (tempIndex <= right){
            array[tempIndex] = temp[k];
            k++;
            tempIndex++;
        }
    }
}

7.查找算法

7.1 线性查找算法

线性查找又称顺序查找，是一种最简单的查找方法
基本思想：从第一个记录开始，逐个比较记录的关键字，直到和给定的K值相等，则查找成功;

package select;

public class LinearSelect {
    public static void main(String[] args) {

        //查询下面数组是否存在某个元素，如果存在则返回索引值，否则返回-1
        int[] array = new int[]{2,4,8,6,4,9,0};
        int i = show(array,4);
        System.out.println(i);
    }

    public static int show(int[] array,int target){
        for (int i = 0; i < array.length; i++) {
            if (array[i] == target){
                return i;
            }
        }
        return -1;
    }
}

7.2 二分查找算法

1. 二分查找也称折半查找（Binary Search)，它是一种效率较高的查找方法
2. 折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列

package select;

public class BinarySearch {
    public static void main(String[] args) {
        int[] array = new int[]{10,11,12,13,14,15,16,17};
        int target = 17;
        int search = search(array, target);
        System.out.println(search);//输出为：7
    }

    public static int search(int[] array,int target){
        //最小索引指针
        int min = 0;

        //最大索引指针
        int max = array.length - 1;

        while (min <= max){
            int mid = (min + max) / 2;
            if (array[mid] == target){
                return mid;
            }

            if (array[mid] < target){
                min = mid + 1;
            }

            if (array[mid] > target){
                max = mid - 1;
            }
        }

        return -1;
    }
}

7.3 插值查找算法

1. 插值查找，有序表的一种查找方式。插值查找是根据查找关键字与查找表中最大最小记录关键字比较后的查找方法。
2. 插值查找基于二分查找，将查找点的选择改进为自适应选择，提高查找效率。

二分查找:
$$mid=\frac{(l+r)}{2}=l+\frac{(r?l)}{2}$$
插值查找:
$$mid=l+\frac{findval?arry[l]}{array[r]?array[l]}?(r?l)$$

package select;

public class InsertSelect {
    public static void main(String[] args) {
        int[] array = new int[]{1,2,3,4,5,6};

        int left = 0;
        int right = array.length - 1;
        int searchVal = 3;

        System.out.println(select(array,left,right,searchVal));//输出为：2
    }

    public static int select(int[] array,int left,int right,int searchVal){
        //防止数组越界
        if (left > right || searchVal < array[0] || searchVal > array[array.length - 1]){
            return -1;
        }

        int mid = left + (right - left)*(searchVal - array[left]) / (array[right] - array[left]);

        int midValue = array[mid];

        if (searchVal > midValue){
            return select(array,mid + 1,right,searchVal);
        }else if(searchVal < midValue){
            return select(array,left,mid - 1,searchVal);
        }else{
            return mid;
        }
    }
}

7.4 斐波那契查找算法

黄金比例又称黄金分割，是指事物各部分间一定的数学比例关系，即将整体一分为二，较大部分与较小部分之比等于整体与较大部分之比,其比值约为1:0.618或1.618:1。因此被称为黄金分割。
斐波那契数列:1,1,2,3,5,8,13,21,34,55,89……，(从第三个数开始，后边每一个数都是前两个数的和)，随着斐波那契数列的递增，前后两个数的比值会越来越接近0.618，利用这个特性，就可以将黄金比例运用到查找技术中。

可以将一个长度为 F(n) 的数组看作左右两段，左边一段长度是 F(n-1)，右边一段长度是 F(n-2)

斐波那契查找算法相对于二分查找和插值查找的基本思路是一致的，其中最重要的区别就是它们的查找点（或称中间值）的确定。斐波那契查找算法的查找点的计算公式如下：
$$mid=left+F(n?1)?1$$

完整的斐波那契查找的基本思想如下：
在斐波那契数列找一个等于或第一个大于查找表中元素个数的数 F[n]，然后将原查找表的长度扩展为 Fn (如果要补充元素，则重复补充原查找表最后一个元素，直到原查找表中满足 F[n] 个元素)；扩展完成后进行斐波那契分割，即 F[n] 个元素分割为前半部分 F[n-1] 个元素，后半部分 F[n-2] 个元素；接着找出要查找的元素在哪一部分并递归，直到找到

package select;

import java.util.Arrays;

public class FibonacciSelect {
    public static void main(String[] args) {
        int[] array = new int[]{1,1,2,3,5,8,13,21,34,55,89};

        System.out.println(select(array,13));//输出为：6
    }

    //f[k] = f[k - 1] + f[k - 2]
    public static int[] f(){
        int[] f = new int[20];
        f[0] = 1;
        f[1] = 1;
        for (int i = 2; i < f.length; i++) {
            f[i] = f[i - 1] + f[i - 2];
        }
        return f;
    }

    //mid = low + f(k - 1) - 1
    public static int select(int[] array,int key){

        int low = 0;
        int hight = array.length - 1;
        int k = 0;
        int mid = 0;
        int[] f = f();

        //找分割点
        while (hight > f[k] - 1){
            k++;
        }

        //将原查找表的长度扩展为 fk
        int[] temp = Arrays.copyOf(array,f[k]);

        //如果要补充元素，则重复补充原查找表最后一个元素
        for (int i = hight + 1; i < temp.length; i++) {
            temp[i] = array[hight];
        }

        //进行查找
        while (low <= hight){
            mid = low + f[k - 1] - 1;

            //f[k - 1]+ f[k - 2] = f[k];
            if (key < temp[mid]){
                hight = mid - 1;
                k--;
            }else if(key > temp[mid]){
                low = mid + 1;
                k -= 2;
            }else{
                if (mid <= hight){
                    return mid;
                }else {
                    return hight;
                }
            }
        }
        return -1;
    }
}

创作打卡挑战赛

赢取流量/现金/CSDN周边激励大奖