排序算法

排序入门

冒泡排序

思路：俩俩交换，大的放在后面，第一次排序后最大值已在数组末尾。因为俩俩交换，需要n-1趟排序（比如10个数，需要9趟排序）
代码实现要点：两个for循环，外层循环控制排序的趟数，内层循环控制比较的次数。每趟过后，比较的次数都应该要减1

    public static void main(String[] args) {
        Integer[] arr = new Integer[]{2,6,3,4,2};
        for(int i=0; i<arr.length-1; i++){
            boolean flag = true;
            int temp;
            for(int j=0; j<arr.length-i-1; j++){
                if(arr[j] > arr[j+1]){
                    temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                    flag = false;
                }
            }
            if(flag)
                break;;
        }
        Arrays.stream(arr)
                .forEach(a -> System.out.println(a));
    }

选择排序

思路：找到数组中最大的元素，与数组最后一位元素交换。当只有一个数时，则不需要选择了，因此需要n-1趟排序
代码实现要点：两个for循环，外层循环控制排序的趟数，内层循环找到当前趟数的最大值，随后与当前趟数组最后的一位元素交换

    public static void main(String[] args) {
        int pos;//储存下标
        int temp; //临时储存值
        Integer[] arr = new Integer[]{2,6,3,4,2};
        for(int i=0; i<arr.length-1; i++){
            pos = 0;
            for(int j=0; j<arr.length-i; j++){
                if(arr[j] > arr[pos]){
                    pos = j;
                }
            }
            temp = arr[pos];
            arr[pos] = arr[arr.length - i -1];
            arr[arr.length - i -1] = temp;
        }
        Arrays.stream(arr)
                .forEach(a -> System.out.println(a));
    }

插入排序

思路：将一个元素插入到已有序的数组中，在初始时未知是否存在有序的数据，因此将元素第一个元素看成是有序的。与有序的数组进行比较，
比它大则直接放入，比它小则移动数组元素的位置，找到个合适的位置插入。当只有一个数时，则不需要插入了，因此需要n-1趟排序
代码实现：一个for循环内嵌一个while循环实现，外层for循环控制需要排序的趟数，while循环找到合适的插入位置(并且插入的位置不能小于0)

    public static void main(String[] args) {
        int temp; //临时储存值
        Integer[] arr = new Integer[]{2,6,3,4,2};
        for(int i=1; i<arr.length; i++){
            temp = arr[i];
            int j = i-1;
            while (j>=0 && arr[j]>temp){
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = temp;
        }
        Arrays.stream(arr)
                .forEach(a -> System.out.println(a));
    }

快速排序

• 底层使用分治法：取出数列中的第一个数作为基准数；将数列中的比基准数大的放在右边 小的放在左边；然后对左右两部分重复第二个操作直到各区间只有一个数

public static void main(String[] args) {
        int[] arr = {6,1,3,2,5,4};
        kuaipai(arr, 0, arr.length - 1);
        for(int i=0; i < arr.length; i++){
            System.out.println(arr[i]);
        }
    }

    //快速排序算法
    public static void kuaipai(int[] arr, int low, int high){
        int i,j,temp,t;
        if(low > high){
            return;
        }
        i = low;
        j = high;
        //temp就是基准数
        temp = arr[low];

        while (i < j){
            //先看右边 依次往左递减
            while (temp <= arr[j] &&  i < j){
                j--;
            }
            //再看左边 依次往右递增
            while (temp >= arr[i] && i < j){
                i++;
            }
            //如果满足条件则交换
            if(i < j){
                t = arr[i];
                arr[j] = arr[i];
                arr[i] = t;
            }
        }
        //最后将基准与i和j相等位置的数字交换
        arr[low] = arr[i];
        arr[i] = temp;
        //递归调用左半数组
        kuaipai(arr, low, j -1);
        //递归调用右半数组
        kuaipai(arr, j+1, high);
    }

本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名,转载请标明出处
最后编辑时间为: 2022/02/13 22:33