数据结构常用算法

1、二分法查找

1.1、实现思路：

二分法查找

1.2、Java代码实现

public class BinarySearch {
    @Test
    public void testBinarySearch() {
        int[] array = {1, 7, 11, 18, 23, 26, 29, 38, 39, 41, 42, 48, 56, 77, 83, 92};
        int target = 10;
        int idx = binarySearch(array, target);
        System.out.println(idx);
    }

    public int binarySearch(int[] a, int t) {
        int l = 0;
        int r = a.length;
        while (l <= r) {//设定终止条件，当查询位置从已经交换相对位置，说明没有找到，则返回-1
            int m = (l + r) >>> 1;//使用无符号位运算符，向右移动移位相当于除二，还可以有效避免数值溢出的问题
            if (a[m] == t) {
                return m;
            } else if (a[m] < t) {
                l = m + 1;
            } else {
                r = m - 1;
            }
        }
        return -1;
    }

}

---

2、冒泡排序

2.1、实现思路：

• 对数据中的数据两两进行比较，如果前者大于后者则交换位置

1.2、Java代码实现

public class Bubble {
    @Test
    public void testBinarySearch() {
        int[] array = {11, 7, 1, 8, 3, 6, 9, 8};
        bubble(array);
        System.out.println(Arrays.toString(array));
    }

    public void bubble(int[] a) {
//每执行一次循环就可以确定一个数，当数组有四个元素时，只要确定其中的三个元素，则另一个元素也自然就确定了
        for (int j = 0; j < a.length - 1; j++) {
            boolean isSwap = false;
            for (int i = 0; i < a.length - 1; i++) {//每执行一次内部循环都能确定一个数，因此不用每次都遍历整个数组，使用a.length - j
                if (a[i] > a[i + 1]) {
                    swap(a, i, i + 1);
                    isSwap = true;
                }
            }
            if (!isSwap) break;
        }

    }
      //辅助函数用于交换两个数的位置
    public void swap(int[] array, int index, int afterIndex) {
        int temp = array[index];
        array[index] = array[afterIndex];
        array[afterIndex] = temp;
    }

}

• 上面只是最原始的方法，当数组的顺序本来就有序时，仍然会执行数组长度-1次循环
• 对冒泡算法可以进行优化，添加一个布尔类型的变量，若执行一次内部循环没有进行过交换则说明已经有序直接退出循环即可
  
  

---

3、选择排序

3.1、实现思路：

• 将数组分为两个子集，排序的和未排序的，每一轮从未排序的子集中选出最小的元素，放入排序好的子集
• 重复第一步，直到整个数组有序

3.2、Java代码实现

public class SelectionSort {
    @Test
    public void testSort() {
        int[] array = {54, 11, 7, 1, 8, 3, 6, 9, 8, 11, 17, 13, 13, 10, 37};
        selectionSort(array);
        System.out.println(Arrays.toString(array));
    }

    public void selectionSort(int[] a) {
        //每循环一次，即每一个i，其对应的位置都会存放当前次序的最小值，
        for (int i = 0; i < a.length - 1; i++) {
            int s = i;//s保存的始终是更小值的索引，整个比较下来就是保存的未排序数组的最小值
            for (int j = s + 1; j < a.length; j++) {
                if (a[s] > a[j]) {
                    s = j;//这一步中，当发现更小的值的时候并没有直接交换，而是先保存小值所对应的索引，然后再
                          //一次循环结束后再进行交换，就可以有效的减少交换的次数
                }
            }
            if (s != i)
                swap(a, s, i);
        }


    }

    public void swap(int[] array, int index, int afterIndex) {
        int temp = array[index];
        array[index] = array[afterIndex];
        array[afterIndex] = temp;
    }

}