JAVA实现三种排序算法+二分查找算法

女爷i 2022-05-15 10:21 206阅读 0赞

### 冒泡排序 ###

> 冒泡排序（Bubble Sort），是一种计算机科学领域的较简单的排序算法。  
> 其核心思想是：  
> 对于一组需要排序的数字，依次将个位置上的数字与逐一与其之后的数字进行比较，如果他们的顺序错误就把他们交换过来。 这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端，故名。

package com.wip.sorting;
    import java.util.Arrays;
    public class BubbleSort { 
        /** * 冒泡排序 * @param arr 需要排序的数组元素 * @param asc 是否升序 */
        public static void sort(int[] arr, boolean asc) { 
            for (int i = 0; i < arr.length; i++) { 
                for (int j = i+1; j < arr.length; j++) { 
                    if (asc) { 
                        if (arr[i] > arr[j]) { 
                            swap(arr,i,j);
                        }
                    } else { 
                        if (arr[i] < arr[j]) { 
                            swap(arr,i,j);
                        }
                    }
                }
            }
        }
    
        /** * 交换数组中的两个元素的位置 * @param arr // 数组 * @param i // 变量i * @param j // 变量j */
        private static void swap(int[] arr, int i, int j) { 
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    
        public static void main(String[] args) { 
            int[] arr = { 1,3,2,5,9,10,53,33,55};
            System.out.println("排序数组：" + Arrays.toString(arr));
            sort(arr,true);
            System.out.println("升序排列：" + Arrays.toString(arr));
            sort(arr,false);
            System.out.println("降序排序：" + Arrays.toString(arr));
        }
    }
    // 输出结果
    排序数组：[1, 3, 2, 5, 9, 10, 53, 33, 55]
    升序排列：[1, 2, 3, 5, 9, 10, 33, 53, 55]
    降序排序：[55, 53, 33, 10, 9, 5, 3, 2, 1]

### 选择排序 ###

> 选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。 选择排序是不稳定的排序方法（比如序列\[5， 5， 3\]第一次就将第一个\[5\]与\[3\]交换，导致第一个5挪动到第二个5后面）。

package com.wip.sorting;
    import java.util.Arrays;
    public class SelectSort { 
    
        /** * 选择排序 * @param arr 排序的数组 * @param asc 是否升序 */
        public static void sort(int[] arr, boolean asc) { 
            for (int i = 0; i < arr.length; i++) { 
                int index = i;
                for (int j = i + 1; j < arr.length; j++) { 
                    if (asc) { 
                        if (arr[index] > arr[j]) {  // 升序，选择无序区最小的元素
                            index = j;
                        }
                    } else { 
                        if (arr[index] < arr[j]) { // 降序，选择无序区最大的元素
                            index = j;
                        }
                    }
                }
                if (index != i) { 
                    swap(arr,index,i);
                }
            }
    
        }
    
        /** * 交换数组中的两个元素的位置 * @param arr // 数组 * @param i // 变量i * @param j // 变量j */
        private static void swap(int[] arr, int i, int j) { 
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    
        public static void main(String[] args) { 
            int[] arr = { 1,3,23,8,10,34,13,56};
            System.out.println("排序数组：" + Arrays.toString(arr));
            sort(arr, true);
            System.out.println("升序排列：" + Arrays.toString(arr));
            sort(arr, false);
            System.out.println("降序排列：" + Arrays.toString(arr));
    
        }
    }
    
    // 输出结果
    排序数组：[1, 3, 23, 8, 10, 34, 13, 56]
    升序排列：[1, 3, 8, 10, 13, 23, 34, 56]
    降序排列：[56, 34, 23, 13, 10, 8, 3, 1]

### 插入排序 ###

> 插入排序(Insert Sort)将待排序的数组分为2部分：有序区，无序区。其核心思想是每次取出无序区中的第一个元素，插入到有序区中。 有序与无序区划分，就是通过一个变量标记当前数组中，前多少个元素已经是局部有序了。

package com.wip.sorting;
    import java.util.Arrays;
    public class InsertSort { 
        /** * 插入排序 * @param arr 排序数组 * @param asc 是否升序 */
        public static void sort(int[] arr, boolean asc) { 
            // 有序区最后一个元素位置
            int orderedLastIndex = 0;//开始排序时，将有序区结束位置设为0 (开始位置总是0)，对应的无序区范围就是 1-arr.length
            for (int i = orderedLastIndex + 1; i < arr.length; i++) { //迭代无序区中的每一个元素，依次插入有序区中
                int temp = arr[i];//记录无序区中的第一个元素值
                int insertIndex = i;//在有序区中插入的索引的位置，刚开始就设置为自己的位置
                for (int j = orderedLastIndex; j >= 0; j--) { //从有序区从后往前开始比较
                    if (asc) { //升序，有序区中比当前无序区中元素大的都右移一个位置
                        if (arr[j] > temp) { 
                            arr[j+1] = arr[j];
                            insertIndex --;//有序区每移动一次，将插入位置-1
                        } else { 
                            break;//有序区当前位置元素<=无序区第一个元素，那么之前的元素都会<=，不需要继续比较
                        }
                    } else { //降序，有序区中比当前无序区中元素小的都右移一个位置
                        if (arr[j] < temp) { 
                            arr[j+1] = arr[j];
                            insertIndex --;
                        } else { 
                            break;
                        }
                    }
                }
                arr[insertIndex] = temp;
                orderedLastIndex ++;
            }
        }
    
        public static void main(String[] args) { 
            int[] arr = { 1,8,3,2,10,34,67,93,11};
            System.out.println("排序数组：" + Arrays.toString(arr));
            sort(arr,true);
            System.out.println("升序数组：" + Arrays.toString(arr));
            sort(arr,false);
            System.out.println("降序数组：" + Arrays.toString(arr));
    
        }
    }
    
    // 输出结果
    排序数组：[1, 8, 3, 2, 10, 34, 67, 93, 11]
    升序数组：[1, 2, 3, 8, 10, 11, 34, 67, 93]
    降序数组：[93, 67, 34, 11, 10, 8, 3, 2, 1]

### 高级二分查找 ###

> 1.二分查找以称折半查找，优点是比较次数少，查找速度快，平均性能好。  
> 2.其缺点是要求待查表为有序表。  
> 3.二分查找的目的是查找元素索引，有个前提是数组元素必须为有序。

package com.wip.sorting;
    public class BinarySearch { 
        /** * 获取某个数在数组里出现在位置 * @param arr // 数组 * @param num // 要找的数 * @return */
        public static int getIndex(int[] arr, int num) { 
            int min = 0;
            int max = arr.length - 1;
            int mid = (min + max) /2;
            System.out.println("min: " + min + " mid: " + mid + " max: " + max);
    
            // 查找的算法
            int index = -1; // 如果算到最后，index人值没有改变，代表num在arr中不存在
    
            while (true) { 
    
                if (arr[mid] == num) { // 找到查找的数
                    index = mid;
                    break;
                }
    
                if (arr[mid] > num) { // num 在左边
                    max = mid - 1;
                    mid = (min + max) / 2;
                }
    
                if (arr[mid] < num) { // num 在右边
                    min = mid + 1;
                    mid = (min + max) / 2;
                }
    
                if (min > max) {  // 不符合逻辑
                    break;// 退出循环
                }
            }
            return index;
        }
    
        public static void main(String[] args) { 
            int[] arr = { 11,22,33,89,34,66};
            int num = 33;
            if (getIndex(arr, num) == -1) { 
                System.out.println(num + " 在数组中不存在");
            } else { 
                System.out.println(num + "索引位置: " + getIndex(arr, num)); //33索引位置: 2
            }
        }
    }