本文讲述了Java排序课程——java常见排序算法实现！具有很好的参考价值，希望对大家有所帮助。一起跟随六星小编过来看看吧，具体如下:

列举java中比较常见的几种排序：冒泡排序、快速排序、插入排序、希尔排序、选择排序、归并排序以及基数排序。

冒泡排序

/**

 * @author fandongfeng

 * @description 冒泡排序

 *  两两比较，大的右移，比出最大的，然后重新开始比

 */

public class BubbleSort {

    public static void main(String[] args) {

        int[] arr = new int[] {5,7,2,9,4,1,0,5,7};

        bubbleSort(arr);

        System.out.println(Arrays.toString(arr));

    }

    public static void bubbleSort(int[] arr) {

        //控制共比较多少轮

        for (int i = 0; i < arr.length -1; i++) {

            for (int j = 0; j < arr.length-1-i; j++) {

                if(arr[j]>arr[j+1]){

                    int temp = arr[j];

                    arr[j] = arr[j+1];

                    arr[j+1] = temp;

                }

            }

        }

    }

}

快速排序

/**

 * @author fandongfeng

 * @description 快速排序

 *  开始位置，结束位置，以第一个数作为标准，比标准大的放到左边，比标准大的放到右边，然后递归标准数位置左右两边的数组就OK了

 */

public class QuickSort {

    public static void main(String[] args) {

        int[] arr = new int[] {3,4,6,7,4,1,2,9,0,5,7};

        quickSort(arr, 0, arr.length - 1);

        System.out.println(Arrays.toString(arr));

    }

    public static void quickSort(int[] arr, int start, int end) {

        if(start < end) {

            //把第0个做为标准

            int stard = arr[start];

            //记录需要排序的下标

            int low = start;

            int high = end;

            //循环找比标准数大的数

            while(low<high) {

                //右边比标准大

                while(low<high && stard <= arr[high]){

                    high--;

                }

                //使用右边数字替换左边数字

                arr[low]=arr[high];

                //如果左边数字比标准数字小

                while(low<high && arr[low]<=stard){

                    low++;

                }

                arr[high] = arr[low];

            }

            //把标准数赋给低所在的位置的元素

            arr[low] = stard;

            //处理所有的比标准数小的数字

            quickSort(arr, start, low-1);

            //处理所有的比标准数大的数字

            quickSort(arr, low+1, end);

        }

    }

}

插入排序

/**

 * @author fandongfeng

 * @description 插入排序

 *  默认该位置左边都是排好序的，所以只要和左边比较

 *  如果小于左边，则此值赋给临时变量，左边值赋给当前（左边位置+1），继续向左与临时变量比较，小于继续赋值给该位置+1处，

 *  不满足则将临时变量赋给不满足位置+1处

 */

public class InsertSort {

    public static void main(String[] args) {

        int[] arr = new int[] {3,4,6,7,4,1,2,9,0,5,7};

        insertSort(arr);

        System.out.println(Arrays.toString(arr));

    }

    private static void insertSort(int[] arr) {

        //遍历所有数字

        for (int i = 1; i < arr.length; i++) {

            //如果当前数字比前一个小

            if(arr[i] < arr[i-1]){

                int temp = arr[i];

                //遍历当前数字前面的所有数字

                int j;

                for (j = i-1; j >=0 && temp < arr[j]; j--) {

                    //把前一个数字赋给后一个数字

                    arr[j+1] = arr[j];

                }

                //把临时变量赋给不满足条件的后一个元素

                arr[j+1] = temp;

            }

        }

    }

}

希尔排序

/**

 * @author fandongfeng

 * @description 希尔排序

 * 长度/2  相隔相同步长的元素进行插入排序 长度/2/2 依次进行

 * 优点，将比较小的元素快速排到前面

 */

public class ShellSort {

    public static void main(String[] args) {

        int[] arr = new int[] {3,4,6,7,4,1,2,9,0,5,7};

        shellSort(arr);

        System.out.println(Arrays.toString(arr));

    }

    private static void shellSort(int[] arr) {

        //遍历所有步长

        for (int d = arr.length/2; d > 0; d/=2) {

            //遍历所有元素

            for (int i = d; i < arr.length; i++) {

                //遍历本组中所有元素

                for (int j = i-d; j >= 0; j-=d) {

                    //如果当前元素大于加上步长后的那个元素

                    if(arr[j] > arr[j+d]){

                        int temp = arr[j];

                        arr[j] = arr[j+d];

                        arr[j+d] = temp;

                    }

                }

            }

        }

    }

}

选择排序

/**

 * @author fandongfeng

 * @description 选择排序

 *  遍历找出最小元素放在第一位，遍历找第二个...

 */

public class SelectSort {

    public static void main(String[] args) {

        int[] arr = new int[] {3,4,6,7,4,1,2,9,0,5,7};

        selectSort(arr);

        System.out.println(Arrays.toString(arr));

    }

    private static void selectSort(int[] arr) {

        //遍历

        for (int i = 0; i < arr.length; i++) {

            int minIndex = i;

            //

            for (int j = i+1; j < arr.length; j++) {

                if(arr[minIndex] > arr[j]) {

                    //记录最小坐标

                    minIndex = j;

                }

            }

            //不相等则交换

            if(i != minIndex) {

                int temp = arr[i];

                arr[i] = arr[minIndex];

                arr[minIndex] = temp;

            }

        }

    }

}

归并排序

/**

 * @author fandongfeng

 * @description 归并排序

 *  先拆分成两个有序数组

 *  然后两个数组合并

 */

public class MergeSort {

    

    public static void main(String[] args) {

        int[] arr = new int[] {1,3,5,2,4,6,8,10};

        mergeSort(arr,0,arr.length - 1);

        System.out.println(Arrays.toString(arr));

    }

    /**

     * 将一个数组分成两个有序数组

     *   左右两边各递归出来两个有序数组，在进行合并

     */

    public static void mergeSort(int[] arr, int low, int high) {

        int middle = (low + high)/2;

        if(low < high) {

            //处理左边

            mergeSort(arr, low, middle);

            //处理右边

            mergeSort(arr, middle+1, high);

            //归并

            merge(arr, low, middle, high);

        }

    }

    public static void merge(int[] arr, int low, int middle, int high) {

        /**

         * ----------arr = [1, 3, 5, 2, 4, 6, 8, 10], low = 0, middle = 0, high = 1

         * ----------arr = [1, 3, 5, 2, 4, 6, 8, 10], low = 2, middle = 2, high = 3

         * ----------arr = [1, 3, 2, 5, 4, 6, 8, 10], low = 0, middle = 1, high = 3

         * ----------arr = [1, 2, 3, 5, 4, 6, 8, 10], low = 4, middle = 4, high = 5

         * ----------arr = [1, 2, 3, 5, 4, 6, 8, 10], low = 6, middle = 6, high = 7

         * ----------arr = [1, 2, 3, 5, 4, 6, 8, 10], low = 4, middle = 5, high = 7

         * ----------arr = [1, 2, 3, 5, 4, 6, 8, 10], low = 0, middle = 3, high = 7

         *

         * [1, 2, 3, 4, 5, 6, 8, 10]

         */

        System.out.println("----------arr = "+ Arrays.toString(arr)+", low = " + low + ", middle = " + middle + ", high = " + high);

        //用于存储归并后的临时数组

        int[] temp = new int[high-low+1];

        //记录第一个数组中需要遍历的下标

        int i = low;

        //记录第二个数组中需要遍历的下标

        int j = middle + 1;

        //用于记录在临时数组中存放的下标

        int index = 0;

        //遍历两个数组，取出小的数字，放入临时数组中

        while (i<=middle && j<=high) {

            if(arr[i] <= arr[j]) {

                temp[index] = arr[i];

                i++;

            }else {

                temp[index] = arr[j];

                j++;

            }

            index ++;

        }

        //处理多余的数据

        while (j <= high) {

            temp[index] = arr[j];

            j++;

            index++;

        }

        while (i <= middle) {

            temp[index] = arr[i];

            i++;

            index++;

        }

        //把临时数组数据重新存入原数组

        for (int k = 0; k < temp.length; k++) {

            arr[k+low] = temp[k];

        }

    }

}

基数排序

/**

 * @author fandongfeng

 * @description 基数排序

 */

public class RadixSort {

    public static void main(String[] args) {

        int[] arr = new int[]{23,6,189,45,9,287,56,1,798,34,65,652,5};

        radixSort(arr);

        System.out.println(Arrays.toString(arr));

    }

    /**

     *  假设有0,1,2,3,4,5,6,7,8,9 十个桶，

     *  获得最大数字位数轮询

     *      按个位数字依次放入对应桶中，然后从0到9，先进先出取出所有数字

     *      按十位数字依次放入对应桶中，然后从0到9，先进先出取出所有数字

     *      ...

     * @param arr

     */

    private static void radixSort(int[] arr) {

        //存取数组最大数

        int max = Integer.MIN_VALUE;

        for (int i = 0; i < arr.length; i++) {

            if(arr[i] > max) {

                max = arr[i];

            }

        }

        //最大数字位数

        int maxLength = (max+"").length();

        //存储临时的数据数组

        int[][] temp = new int[10][arr.length];

        //用于记录temp中同一列存放数字个数

        int[] count = new int[10];

        //根据最大长度数决定比较次数

        for (int i=0, n=1; i < maxLength; i++,n*=10) {

            //把每一个数字分别计算余数

            for (int j = 0; j < arr.length; j++) {

                //余数

                int ys = arr[j] / n % 10;

                //存到相应的数组中

                temp[ys][count[ys]] = arr[j];

                //记录数量

                count[ys]++;

            }

            //记录取的元素需要放的位置

            int index = 0;

            //把数字取出来

            for (int k = 0; k < count.length; k++) {

                if(count[k] != 0) {

                    //循环取出元素

                    for (int l = 0; l < count[k]; l++) {

                        arr[index] = temp[k][l];

                        index++;

                    }

                    //把数量置为0

                    count[k] = 0;

                }

            }

        }

    }

}

既然是FIFO的排序，则可以用队列代替

/**

 * @author fandongfeng

 * @created 2020/1/13 18:57

 * @description 基数排序 - 基于队列（FIFO）实现

 */

public class RadixQueueSort {

    public static void main(String[] args) {

        int[] arr = new int[]{23,6,189,45,9,287,56,1,798,34,65,652,5};

        radixSort(arr);

        System.out.println(Arrays.toString(arr));

    }

    /**

     *  假设有0,1,2,3,4,5,6,7,8,9 十个桶，

     *  获得最大数字位数轮询

     *      按个位数字依次放入对应桶中，然后从0到9，先进先出取出所有数字

     *      按十位数字依次放入对应桶中，然后从0到9，先进先出取出所有数字

     *      ...

     * @param arr

     */

    private static void radixSort(int[] arr) {

        //存取数组最大数

        int max = Integer.MIN_VALUE;

        for (int i = 0; i < arr.length; i++) {

            if(arr[i] > max) {

                max = arr[i];

            }

        }

        //最大数字位数

        int maxLength = (max+"").length();

        //存储临时的数据队列

        Queue[] temp = new LinkedBlockingQueue[10];

        //初始化，防止NPE报错

        for (int i = 0; i < temp.length; i++) {

            temp[i] = new LinkedBlockingQueue();

        }

        //根据最大长度数决定比较次数

        for (int i=0, n=1; i < maxLength; i++,n*=10) {

            //把每一个数字分别计算余数

            for (int j = 0; j < arr.length; j++) {

                //余数

                int ys = arr[j] / n % 10;

                //存到指定队列

                temp[ys].add(arr[j]);

            }

            //记录取的元素需要放的位置

            int index = 0;

            //把数字取出来

            for (int k = 0; k < temp.length; k++) {

                if(!temp[k].isEmpty()) {

                    //循环取出元素

                    while (!temp[k].isEmpty()) {

                        arr[index] = Integer.valueOf(temp[k].poll()+"");

                        index++;

                    }

                }

            }

        }

    }

}

堆排序

/**

 * @author fandongfeng

 * @description 堆排序

 * 堆排序：

 *  堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。

 *  堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：

 *      即子结点的键值或索引总是小于（或者大于）它的父节点

 *

 *  堆排序的基本思想是：将待排序序列构造成一个大顶堆，

 *  此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。

 *  然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。

 *  如此反复执行，便能得到一个有序序列了

 *  一般升序采用大顶堆，降序采用小顶堆

 */

public class HeapSort {

    public static void main(String[] args) {

        int[] arr = new int[] {9,6,8,7,0,1,10,4,2};

        heapSort(arr);

        System.out.println(Arrays.toString(arr));

    }

    private static void heapSort(int[] arr) {

        //最后一个非叶子节点

        int start = arr.length/2 -1;

        //调整成大顶堆

        for (int i = start; i >= 0; i--) {

            maxHeap(arr, arr.length, i);

        }

        //先把数组的第0个和堆中最后一个交换位置，  在把前面的处理为大顶堆

        for (int i= arr.length -1; i>0; i--) {

            int temp = arr[0];

            arr[0] = arr[i];

            arr[i] = temp;

            maxHeap(arr, i, 0);

        }

    }

    /**

     * 数组转成大顶堆

     */

    private static void maxHeap(int[] arr, int size, int index) {

        //左子节点

        int leftNode = 2*index + 1;

        //右子节点

        int rightNode = 2*index + 2;

        int max = index;

        //和两个子节点分别对比，找出最大的节点

        if(leftNode < size && arr[leftNode] > arr[max]) {

            max = leftNode;

        }

        if(rightNode < size && arr[rightNode] > arr[max]) {

            max = rightNode;

        }

        //交换位置

        if(max != index) {

            int temp = arr[index];

            arr[index] = arr[max];

            arr[max] = temp;

            //交换之后，可能会破坏之前排好的序

            maxHeap(arr, size, max);

        }

    }

}

更多相关技术内容咨询欢迎前往并持续关注六星社区了解详情。

想高效系统的学习Java编程语言，推荐大家关注一个微信公众号：Java圈子。每天分享行业资讯、技术干货供大家阅读，关注即可免费领取整套Java入门到进阶的学习资料以及教程，感兴趣的小伙伴赶紧行动起来吧。