时间戳

首页 > 技术文章 > JAVA 排序(直接插入/快速/冒泡/直接选择)

JAVA 排序(直接插入/快速/冒泡/直接选择)

ruhuanxingyun 2020-07-07 10:56 原文

1. 排序知识

　　A. 分类：简单排序(直接插入排序、冒泡排序、简单选择排序)、快速排序、希尔排序、堆排序、归并排序、基数排序和桶排序，这几种都属于内部排序；

　　B. 排序稳定性： 假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。

 

2. 直接插入排序

　　A. 原理：把n个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包含1个元素，无序表中包含n-1个元素，排序过程中每次从无序表中取出第一个元素，从有序表中从后向前扫描，将它插入到有序表中的适当位置，使之成为新的有序表，插入位置及其后的记录依次向后移动，重复n-1次可完成排序过程；

　　B. 特性：排序具有稳定性，时间复杂度为O(n^2)，空间复杂度为O(1)；

　　C. 示例代码

package com.ruhuanxingyun.javabasic.sort;

/**
 * @description: 直接插入排序
 * @author: ruphie
 * @date: Create in 2020/7/8 22:14
 * @company: ruhuanxingyun
 */
public class InsertSort {

    public static void main(String[] args) {
        int[] arr = {11, 8, 10, 62, 3, 1, 8, 15, 34};
        System.out.println("------ 直接插入排序前数据顺序 ------");
        for (int value : arr) {
            System.out.println(value);
        }

        insertSort(arr);
        System.out.println("------ 直接插入排序后数据顺序 ------");
        for (int value : arr) {
            System.out.println(value);
        }
    }

    /**
     * 直接插入排序(升序)
     *
     * @param arr 待排序的整形数组
     */
    private static void insertSort(int[] arr) {
        int j, temp;
        for (int i = 1, len = arr.length; i < len; i++) {
            // 若是后面元素比前面元素还大，就没有必要往下接着走
            if (arr[i] < arr[i - 1]) {
                // 保存需要插入的数
                temp = arr[i];
                for (j = i - 1; j >= 0 && arr[j] > temp; j--) {
                    // 把大于需要插入的数往后移动
                    arr[j + 1] = arr[j];
                }
                // 将需要插入的数放入这个位置
                arr[j + 1] = temp;
            }
        }
    }

}

 

3. 快速排序

　　A. 原理：选择一个基准数，通过一趟排序将要排序的数据分割成独立的两部分，其中一部分所有的数据都要比另外一部分所有的数据都要小，然后再按照此方法对这两部分数据分别进行快速排序，整个过程可以递归进行，以此达到整个数据变成有序序列；

　　B. 特性：时间复杂度为O(N*lgN)，不稳定；

　　C. 示例代码

package com.ruhuanxingyun.javabasic.sort;

/**
 * @description: 快速排序
 * @author: ruphie
 * @date: Create in 2020/7/7 22:48
 * @company: ruhuanxingyun
 */
public class QuickSort {

    public static void main(String[] args) {
        int[] arr = {11, 8, 10, 62, 3, 1, 8, 15, 34};
        System.out.println("------ 快速排序前数据顺序 ------");
        for (int value : arr) {
            System.out.println(value);
        }

        quickSort(arr, 0, arr.length - 1);
        System.out.println("------ 快速排序后数据顺序 ------");
        for (int value : arr) {
            System.out.println(value);
        }
    }

    /**
     * 快速排序（升序）
     *
     * @param arr   待排序的整形数组
     * @param start 数组的左边界
     * @param end   数组的右边界
     */
    private static void quickSort(int[] arr, int start, int end) {
        if (start >= end) {
            return;
        }

        int i = start;
        int j = end;
        // 元素集的第一个值作为分界点
        int temp = arr[start];
        while (i < j) {
            // 从右向左找大于temp的数
            while (i < j && temp < arr[j]) {
                j--;
            }
            // 交换数据
            if (i < j) {
                arr[i++] = arr[j];
            }

            // 从左向右找小于temp的数
            while (i < j && temp > arr[i]) {
                i++;
            }
            // 交换数据
            if (i < j) {
                arr[j--] = arr[i];
            }
        }
        arr[i] = temp;

        // 递归调用左半数组
        quickSort(arr, start, i - 1);
        // 递归调用右半数组
        quickSort(arr, i + 1, end);
    }

}

 

 

4. 冒泡排序

　　A. 原理：它会遍历若干次要排序的数列，每次遍历时，它都会从前往后依次的比较相邻两个数的大小，如果前者比后者大，则交换它们的位置；这样，一次遍历之后，最大的元素就在数列的末尾， 采用相同的方法再次遍历时，第二大的元素就被排列在最大元素之前，重复此操作，直到整个数列都有序为止；

　　B. 特性：排序具有稳定性，时间复杂度为O(n^2)，空间复杂度为O(1)；

　　C. 示例代码

package com.ruhuanxingyun.javabasic.sort;

/**
 * @description: 冒泡排序
 * @author: ruphie
 * @date: Create in 2020/10/21 21:31
 * @company: ruhuanxingyun
 */
public class BubbleSort {

    public static void main(String[] args) {
        int[] arr = {11, 8, 10, 62, 3, 1, 8, 15, 34};
        System.out.println("------ 冒泡排序前数据顺序 ------");
        for (int value : arr) {
            System.out.println(value);
        }

        bubbleSort(arr);
        System.out.println("------ 冒泡排序后数据顺序 ------");
        for (int value : arr) {
            System.out.println(value);
        }
    }

    /**
     * 冒泡排序(升序)
     *
     * @param arr 待排序的整形数组
     */
    private static void bubbleSort(int[] arr) {
        boolean status = true;
        int temp;
        // 外层控制循环多少趟
        for (int len = arr.length, i = len - 1; i > 0; i--) {
            // 内层控制每一趟循环的次数
            for (int j = 0; j < i; j++) {
                // 比较并交换数据，将数组中最大数据放在末尾
                if (arr[j] > arr[j + 1]) {
                    temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    status = false;
                }
            }

            // 若没有发生交换，就代表数组本身就是有序
            if (status) {
                break;
            }
        }
    }

}

 

5. 直接选择排序

　　A. 原理：首先在未排序的数列中找到最小或最大元素，然后将其存放到数列的起始位置；接着，再从剩余未排序的元素中继续寻找最小或最大元素，然后放到已排序序列的末尾，以此类推，直到所有元素均排序完毕；

　　B. 特性：排序不稳定，时间复杂度为O(n^2)，空间复杂度为O(1)；

　　C. 示例代码

package com.ruhuanxingyun.javabasic.sort;

/**
 * @description: 简单选择排序
 * @author: ruphie
 * @date: Create in 2020/10/21 21:31
 * @company: ruhuanxingyun
 */
public class SelectSort {

    public static void main(String[] args) {
        int[] arr = {11, 8, 10, 62, 3, 1, 8, 15, 34};
        System.out.println("------ 简单选择排序前数据顺序 ------");
        for (int value : arr) {
            System.out.println(value);
        }

        selectSort(arr);
        System.out.println("------ 简单选择排序后数据顺序 ------");
        for (int value : arr) {
            System.out.println(value);
        }
    }

    /**
     * 简单选择排序(升序)
     *
     * @param arr 待排序的整形数组
     */
    private static void selectSort(int[] arr) {
        int k, temp;
        for (int i = 0, len = arr.length; i < len - 1; i++) {
            k = i;
            for (int j = i + 1; j < len; j++) {
                // 找出最小整数的下标
                if (arr[j] < arr[k]) {
                    k = j;
                }
            }

            // 避免后面的值本来就大导致无效的移位
            if (k != i) {
                temp = arr[i];
                arr[i] = arr[k];
                arr[k] = temp;
            }
        }
    }

}

 

推荐阅读