关于java:教了公司新来的小姐姐这七种排序算法以及实现她一脸崇拜的看着我

28次阅读

共计 6827 个字符，预计需要花费 18 分钟才能阅读完成。

前言

最近学习一些排序算法，怕本人当前遗记就打算整顿起来供本人温习

如有谬误心愿大佬斧正，欢送大家在评论区交换探讨。

1. 冒泡排序

  • 通过待排序的序列从前往后顺次比拟相邻的元素，若发现逆序则两两替换，直到下一趟排序下来没有进行替换，阐明排序实现
  • 冒泡排序每一趟会确定一个最大值（默认从小到大）
import java.util.Arrays;

public class BubbleSort {public static void main(String[] args) {int array[] = {10,9,2,-3,6,8,1,-6,-5,4};
        for (int i = 0; i < array.length ; i++) { // 循环每一趟排序
            for (int j = 0; j < array.length-1-i ; j++) {
// 每一趟排序的数据交换
// 因为 array[j] 是和 array[j+1] 比拟, 避免数据越界这里 array.length 要减一
                int temp = 0;
                if (array[j]>array[j+1]){temp = array[j+1];
                    array[j+1] = array[j];
                    array[j] = temp;
                }
            }
        }
//  两种办法输入
//  1. 格式化输入, 需 import，之后的代码演示全用格式化输入
        System.out.println(Arrays.toString(array));
//  2.for 循环输入
        for (int i = 0; i < array.length ; i++) {System.out.print(array[i]+" ");
        }

    }
}

2. 抉择排序

  • 第一趟排序是从 array[0] 到 array[array.length-1] 找到一个最小值 array[n] 与 array[0] 进行替换，第一趟排序是从 array[1] 到 array[array.length-1] 找到一个最小值 array[n] 与 array[1] 进行替换，直到排序实现
  • 抉择排序每一趟排序会确定一个最小值（默认从小到大）
  • 以下是三种不同的代码实现 
import java.util.Arrays;

public class SelectSortDemo01 {public static void main(String[] args) {int array[] = {10,9,2,-3,6,8,1,-6,-5,4};
        for (int i = 0; i < array.length-1 ; i++) {for (int j = 1+i; j < array.length; j++) {
//  此算法与冒泡排序的算法相似, 只不过冒泡算法的每一趟排序是两两比拟, 这个是第一个数与每一个数比拟
                int temp = 0;
                if (array[i] > array[j]){temp = array[j];
                    array[j] = array[i];
                    array[i] = temp;
                }
            }
        }
        System.out.println(Arrays.toString(array));
    }
}

import java.util.Arrays;

public class SelectSortDemo02 {public static void main(String[] args) {int array[] = {10,9,2,-3,6,8,1,-6,-5,4};
        int temp = 0;
        for (int j = 0; j <array.length-1 ; j++) {for (int i = 1; (i+j)< array.length ; i++) {
// 此算法与下面一个大同小异，也实现了雷同的成果，能够依据本人的思维抉择一个适合的算法              
                if (array[j] > array[i+j]) {temp = array[i+j];
                    array[i+j] = array[j];
                    array[j] = temp;
                }
            } 
        }
      System.out.println(Arrays.toString(array));
    }
}

public class SelectSortDemo02 {public static void main(String[] args) {int array[] = {10,9,2,-3,6,8,1,-6,-5,4};
        for (int i = 0; i < array.length-1 ; i++) { 
 //      与后面两种办法不同的是此算法间接先假设每一趟排序的第 i 个数的数值最小，提取以后下标 i，//      不便每一趟排序与第 i 个数据进行替换
 //      这样也更容易了解
            int min = array[i];
            int minIndex = i;
            for (int j =  1 + i; j < array.length; j++) {if (min > array[j] ){
 //      阐明假设的最小值并不是最小的，须要重置 min, 此时只需赋值，不须要替换
 //      让其循环完结直到赋值到最小值
                    min = array[j];
                    minIndex = j;
                }
            }
//        将最小值放在 arr[0], 替换
            if (minIndex != j) {array[minIndex] = arr[j];
                array[j] = min;
            }
        }
        System.out.println(Arrays.toString(array));
    }
}

3. 插入排序

  • 如果有 n 个数，第一趟排序就是比拟前两个数将它们排好 (默认从小到大)，而后在来一个数比拟他们三个再排好
  • 能够了解为斗地主的摸牌，先摸了两张 J 和 K，要把 J 放在 K 的后面，在摸一张 6 要放在 J 和 K 的后面，在摸一张 10 就要放在 6 和 J 之间，排摸完了就相当于排序完结 
import java.util.Arrays;

public class InsertSortDemo01 {public static void main(String[] args) {int[] array = {5, 2, -1, 4, 7};
        for (int i = 1; i < array.length; i++) {
//      与抉择排序第三种相似, 先定义一个待插入的数据和插入的地位, 便于之后赋值
            int insertVal = array[i];
//      为了将待插入的数插入到 array[i] 的前一个地位
            int insertIndex = i - 1;
//      待插入的地位必须大于等于 0, 保障数组不越界
            while (insertIndex >= 0 && insertVal < array[insertIndex]) {
//      间接赋值不必替换数据
                array[insertIndex + 1] = array[insertIndex];
//      为了让第 i 个数与后面的数都进行比拟而后赋值, 后面有条件不必但不必放心数组越界         
                insertIndex--;
            }
//      insertIndex + 1 = i 阐明第 i 轮曾经有序      
            if (insertIndex + 1 != i) {array[insertIndex + 1] = insertVal;
            }
        }
        System.out.println(Arrays.toString(array));
    }

}

4. 希尔排序

  • 希尔排序相当于对插入排序进行优化，是一种放大增量排序
  • 希尔排序第一趟依照 arraylength2 进行分组，每组别离进行间接插入排序，第二趟依照 arraylength22 进行分组，每组别离进行间接插入排序, 直到增量减至为一，整个文件恰好被分为一组
  • 以下是两种不同的代码实现 
import java.util.Arrays;
//      交换法，此实现办法速度是很慢，//      因为插入排序比拟之后间接移位，而此类办法一遇到逆序就会产生替换，//      交换法与冒泡排序相似，不停的替换效率很低
public class ShellSortDemo02 {public static void main(String[] args) {int array[] = {10,9,2,-3,6,8,1,-6,-5,4};
        int temp = 0;
        for (int len = array.length/2; len > 0;len/=2) {
//      循环每一次分组
            for (int i = len; i < array.length; i++) {
//      遍历各组的所有元素, 有 len 组
                for (int j = i - len; j >= 0; j -= len) {if (array[j] > array[j + len]) {temp = array[j];
                        array[j] = array[j + len];
                        array[j + len] = temp;
                    }
                }
            }
        }
        System.out.println(Arrays.toString(array));

    }
}

import java.util.Arrays;

public class ShellSortDemo03 {
//    对交换式的希尔排序进行优化, 采纳移位法
//    当须要插入的数是最小数时, 后移的次数显著增多, 所以应用分组插入排序会大大的提高效率
    public static void main(String[] args) {int[] array = {10, 9, 2, -3, 6, 8, 1, -6, -5, 4};
//    依然应用增量 len, 并逐渐放大增量
        for (int len = array.length / 2; len > 0; len /= 2) {
//    一一对其所在的组进行间接插入排序
            for (int i = len; i < array.length; i++) {
                int j = i;
                int temp = array[j];
                if (array[j] < array[j - len]) {while (j-len >= 0 && temp < array[j - len]) {
//  挪动, 与间接插入排序不同的是这个是间距 len 之间的数据移位, 而间接插入排序是两两移位
                        array[j] = array[j - len];
                        j -=len;
                    }
//     当退出 while 循环后, 就给 temp 找到了插入的地位
                    array[j] = temp;
                }
            }
        }
        System.out.println(Arrays.toString(array));
    }
}

5. 疾速排序

  • 疾速排序是一种对冒泡排序的改良，第一趟排序以两头的一个数为基准，将数组中比他小的数放在此数的右边，比他大的数放在此数的左边，第二趟排序以第一趟排好的左右的两头一个数为基准，在别离反复下面操作 
import java.util.Arrays;

public class QuickSortDemo01 {public static void main(String[] args) {int array[] = {10,9,2,-3,6,8,1,-6,-5,4};
        quickSort(array,0,array.length-1);
        System.out.println(Arrays.toString(array));
    }
    public static void quickSort(int a[],int l,int r){if(l>=r)
            return;

        int i = l; int j = r; int key = a[(l+r)/2];
//     抉择第一个数为 key, 咱们数组两头的数为例
        while(i<j){while(i<j && a[j]>=key)
//     从右向左找第一个小于 key 的值, 找到了，j 就前移
                j--;
//     如果 a[j]<key 值，a[j] 会放到后面的 a[i] 同时 i 会后移          
            if(i<j){a[i] = a[j];
                i++;
            }

            while(i<j && a[i]<key)
//     从左向右找第一个大于 key 的值，找到了 i 就后移
                i++;
//     如果 a[i]>key 值，a[i] 会放到前面的 a[j] 同时 j 会前移 
            if(i<j){a[j] = a[i];
                j--;
            }
        }
        //i == j
        a[i] = key;
        quickSort(a, l, i-1);// 递归调用
        quickSort(a, i+1, r);// 递归调用
    }
}

6. 归并排序

  • 归并算法的核心思想就是合成在合并，也就是分治，合成能够采纳递归，设一个数组最左边的元素索引为 low，最右边的元素的索引为 height，两头元素索引为 (low+height)/2, 每一次合成能够发现当 low==height 的时候，整个数组被分解成每一个元素，合并就是将两个有序归并段归并为一个有序的归并段，直到有序为止 
import java.util.Arrays;

public class MergeSortDemo01 {
    // 合并函数
    public static void merge(int[] array,int low,int mid,int height){
        int s1 = low;
        int s2 = mid+1;
        int[] ret = new int[height-low+1];
        int i = 0;// 示意 ret 数组的下标
        while (s1<=mid && s2<=height){if (array[s1]<=array[s2]){ret[i++] = array[s1++];
            }else{ret[i++] = array[s2++];
            }
        }
        while (s1<=mid){ret[i++] = array[s1++];
        }
        while (s2<=height){ret[i++] = array[s2++];
        }
        for (int j=0;j<ret.length;j++){array[low+j] = ret[j];
        }

    }
    public static void mergeSort(int[]array,int low,int height){if (low>=height){return;}
        int mid = (low+height)/2;
        mergeSort(array,low,mid);// 递归合成左半局部
        mergeSort(array,mid+1,height);// 递归合成右半部本
        merge(array,low,mid,height);// 合并操作
    }

    public static void main(String[] args) {int array[] = {10,9,2,-3,6,8,1,-6,-5,4};
        System.out.println(Arrays.toString(array));
        mergeSort(array,0,array.length-1);
        System.out.println(Arrays.toString(array));
    }
}

7. 基数排序

  • 实质上是将整数按位数切割成不同的数字，而后按每个位数别离比拟，基数排序又叫桶子法
  • 定义 10 个编号为 0~9 一维数组，找到每个数的个位数别离放在对应编号的数组中，而后再将十位数取出别离放在对应编号的数组中，直到取到最高位就变为有序
  • 基数排序是效率最高的稳定性排序法 
import java.util.Arrays;

public class RadixSortDemo01 {public static void main(String[] args) {int array[] = {10, 99, 2, 457, 6, 83, 16, 96, 25, 48};
        radixSort(array);
    }

    // 基数排序算法
    public static void radixSort(int[] arr) {int max = arr[0];
//    假如第一个数是最大数
        for (int i = 0; i < arr.length; i++) {if (arr[i] > max) {max = arr[i];
            }
        }
        int maxLength = (max + " ").length();
//        定义一个二维数组，示意 10 个桶，每一个桶是一个一维数组用于存放数据
//        为了避免放入数的时候，数据溢出，则每个一维数组的大小定位 arr.length
        int[][] bucket = new int[10][arr.length];
//      为了记录每个桶中，理论寄存了多少数据，咱们定义一个一维数组，咱们定义一个一维数组记录各个桶每次放入的数据个数
        int[] bucketCounts = new int[10];
        for (int k=0,n=1;k<maxLength-1;k++,n *=10){for (int i = 0; i < arr.length; i++) {
//         取出每个元素的个位
                int digitOfElement = arr[i] / n % 10;
//          放入到对应的桶中
                bucket[digitOfElement][bucketCounts[digitOfElement]] = arr[i];
//            每放一个数据此桶的中的数据就要加一
                bucketCounts[digitOfElement]++;
            }
//        依照这个桶的程序（一维数组的下标顺次取出数据，放入原来数组）int index = 0;
//        遍历每一个桶并将桶中数据放入原数组
            for (int i = 0; i < bucketCounts.length; i++) {
//         如果桶中有数据咱们才放入到原数组
                if (bucketCounts[i] != 0) {for (int j = 0; j < bucketCounts[i]; j++) {
//         取出元素放入到 arr
                        arr[index++] = bucket[i][j];
                    }
                }
//            第轮解决后须要将每一个 bucketCounts[i] = 0;
                bucketCounts[i] = 0;
            }
            System.out.println("第"+(k+1)+"轮排序 arr =" + Arrays.toString(arr));
        }
    }
}

最初

感激你看到这里，看完有什么的不懂的能够在评论区问我，感觉文章对你有帮忙的话记得给我点个赞，每天都会分享 java 相干技术文章或行业资讯，欢送大家关注和转发文章！

正文完
java
发表至： java
2020-07-29
 0
关于java:学妹问我OpenJDK是什么作为师哥必须万字详解屁颠屁颠奉上
关于java:秋招上岸我都做对了哪些事
java并发编程学习之线程的ForkJoin-框架基本概念一
带你了解集合世界的failfast机制-和-CopyOnWriteArrayList-源码详解