常见的排序算法详细分析与实现

╰+攻爆jí腚メ 2022-05-21 04:15 110阅读 0赞

1.  **冒泡排序**
    
     *  外层循环n-1轮
     *  每轮循环都比较相邻位置的两个值，每轮循环比较次数都依次递减
     *  这样，每次循环都会把大的数移到后面
    
    效果如下：
    
        原始数据：8 1 4 9 0 3 5 2 7 6
        
        1 4 8 0 3 5 2 7 6 9 
        1 4 0 3 5 2 7 6 8 9 
        1 0 3 4 2 5 6 7 8 9 
        0 1 3 2 4 5 6 7 8 9 
        0 1 2 3 4 5 6 7 8 9 
        0 1 2 3 4 5 6 7 8 9 
        0 1 2 3 4 5 6 7 8 9 
        0 1 2 3 4 5 6 7 8 9 
        0 1 2 3 4 5 6 7 8 9 
        0 1 2 3 4 5 6 7 8 9 9 
        1 4 0 3 5 2 7 6 8 9 
        1 0 3 4 2 5 6 7 8 9 
        0 1 3 2 4 5 6 7 8 9 
        0 1 2 3 4 5 6 7 8 9 
        0 1 2 3 4 5 6 7 8 9 
        0 1 2 3 4 5 6 7 8 9 
        0 1 2 3 4 5 6 7 8 9 
        0 1 2 3 4 5 6 7 8 9 
        0 1 2 3 4 5 6 7 8 9
2.  **选择排序**
    
    1.  外层循环n-1轮
    2.  每次循环都和后面所有数比较，选出最小值，每轮循环比较次数也是依次递减
    3.  最后交换开始值和最小值的位置，所以交换次数固定
    
    效果如下：
    
        原始数据：8 1 4 9 0 3 5 2 7 6
        
        0 1 4 9 8 3 5 2 7 6 
        0 1 4 9 8 3 5 2 7 6 
        0 1 2 9 8 3 5 4 7 6 
        0 1 2 3 8 9 5 4 7 6 
        0 1 2 3 4 9 5 8 7 6 
        0 1 2 3 4 5 9 8 7 6 
        0 1 2 3 4 5 6 8 7 9 
        0 1 2 3 4 5 6 7 8 9 
        0 1 2 3 4 5 6 7 8 9 
        0 1 2 3 4 5 6 7 8 9 0 1 4 9 8 3 5 2 7 6 
        0 1 4 9 8 3 5 2 7 6 
        0 1 2 9 8 3 5 4 7 6 
        0 1 2 3 8 9 5 4 7 6 
        0 1 2 3 4 9 5 8 7 6 
        0 1 2 3 4 5 9 8 7 6 
        0 1 2 3 4 5 6 8 7 9 
        0 1 2 3 4 5 6 7 8 9 
        0 1 2 3 4 5 6 7 8 9 
        0 1 2 3 4 5 6 7 8 9
3.  **插入排序**
    
    1.  外层循环n-1轮
    2.  每轮循环当前值与前一个值比较，如果当前值小于前一个值，前一个值后移一位，依次向前比较
    3.  直到当前值大于前一个值，插入在它后面
    
    效果如下：
    
         
    
        原始数据：8 1 4 9 0 3 5 2 7 6
        1 8 4 9 0 3 5 2 7 6 
        1 4 8 9 0 3 5 2 7 6 
        1 4 8 9 0 3 5 2 7 6 
        0 1 4 8 9 3 5 2 7 6 
        0 1 3 4 8 9 5 2 7 6 
        0 1 3 4 5 8 9 2 7 6 
        0 1 2 3 4 5 8 9 7 6 
        0 1 2 3 4 5 7 8 9 6 
        0 1 2 3 4 5 6 7 8 9 
        1 8 4 9 0 3 5 2 7 6 
        1 4 8 9 0 3 5 2 7 6 
        1 4 8 9 0 3 5 2 7 6 
        0 1 4 8 9 3 5 2 7 6 
        0 1 3 4 8 9 5 2 7 6 
        0 1 3 4 5 8 9 2 7 6 
        0 1 2 3 4 5 8 9 7 6 
        0 1 2 3 4 5 7 8 9 6 
        0 1 2 3 4 5 6 7 8 9
4.  **快速排序**
    
    1.  采用分区递归的方法排序，直到所有最小分区大小为一，递归返回
    2.  每轮首先选取分区的第一个值作为基准数x，通过两个哨兵可以确定x的位置（基准数x在正确排序中的位置），并保证x的左边都是小于它的数，右边都是大于它的数
    3.  首先，哨兵j从分区的最右边向左移动，找到小于x的数，停下，把该数的放到x的位置或前面哨兵i停下的位置，然后哨兵i开始移动；
    4.  哨兵i从分区的最左边开始想右边移动，找到大于基准数x的数，停下，把该数放到前面哨兵j停下的位置，然后哨兵j又开始移动；
    5.  一直循环3,4步骤，知道哨兵i和哨兵j相遇，这个位置就是基准数x在正确排序中的位置，把x放在该位置，一轮循环完成；
    6.  基准数x前面的数为一个分区，后面的数为一个分区，分别进行递归调用，执行前面的步骤。
    
    效果如下：
    
        原始数据：8 1 4 9 0 3 5 2 7 6
        
        第一轮 基准数为8
        6 1 4 9 0 3 5 2 7 6 哨兵j从6开始向左移动
        6 1 4 9 0 3 5 2 7 9 哨兵i从1开始想右移动
        6 1 4 7 0 3 5 2 7 9 
        6 1 4 7 0 3 5 2 7 9 
        6 1 4 7 0 3 5 2 7 9 
        2 1 4 7 0 3 5 2 8 9 确定8的位置
        第二轮 基准数2, 只有8左边的分区进行排序
        2 1 4 7 0 3 5 7 8 9 确定9的位置
        2 1 4 5 0 3 5 7 8 9 
        2 1 4 5 0 3 5 7 8 9 
        2 1 4 5 0 3 5 7 8 9 
        0 1 4 5 0 3 6 7 8 9 
        0 1 4 5 4 3 6 7 8 9 
        0 1 4 5 4 3 6 7 8 9 
        0 1 4 5 4 3 6 7 8 9 
        0 1 4 5 4 3 6 7 8 9 
        0 1 2 5 4 3 6 7 8 9 确定2的位置
        第三轮 分区0 1 基准数0 
        0 1 2 5 4 3 6 7 8 9 确定1的位置
        0 1 2 5 4 3 6 7 8 9 确定0的位置
        第四轮 分区 5 4 3 6 7 基准数5
        0 1 2 5 4 3 6 7 8 9 
        0 1 2 3 4 3 6 7 8 9 
        0 1 2 3 4 3 6 7 8 9 
        0 1 2 3 4 3 6 7 8 9 
        0 1 2 3 4 5 6 7 8 9  确定5的位置
        第五轮 分区3 4 基准数3
        0 1 2 3 4 5 6 7 8 9 确定4的位置
        0 1 2 3 4 5 6 7 8 9 确定3的位置
        第六轮 分区 6 7 基准数6
        0 1 2 3 4 5 6 7 8 9 确定7的位置
        0 1 2 3 4 5 6 7 8 9 确定6的位置
        0 1 2 3 4 5 6 7 8 9 
        
        6 1 4 9 0 3 5 2 7 6 哨兵j从6开始向左移动
        6 1 4 9 0 3 5 2 7 9 哨兵i从1开始想右移动
        6 1 4 7 0 3 5 2 7 9 
        6 1 4 7 0 3 5 2 7 9 
        6 1 4 7 0 3 5 2 7 9 
        2 1 4 7 0 3 5 2 8 9 确定8的位置
        第二轮 基准数2, 只有8左边的分区进行排序
        2 1 4 7 0 3 5 7 8 9 确定9的位置
        2 1 4 5 0 3 5 7 8 9 
        2 1 4 5 0 3 5 7 8 9 
        2 1 4 5 0 3 5 7 8 9 
        0 1 4 5 0 3 6 7 8 9 
        0 1 4 5 4 3 6 7 8 9 
        0 1 4 5 4 3 6 7 8 9 
        0 1 4 5 4 3 6 7 8 9 
        0 1 4 5 4 3 6 7 8 9 
        0 1 2 5 4 3 6 7 8 9 确定2的位置
        第三轮 分区0 1 基准数0 
        0 1 2 5 4 3 6 7 8 9 确定1的位置
        0 1 2 5 4 3 6 7 8 9 确定0的位置
        第四轮 分区 5 4 3 6 7 基准数5
        0 1 2 5 4 3 6 7 8 9 
        0 1 2 3 4 3 6 7 8 9 
        0 1 2 3 4 3 6 7 8 9 
        0 1 2 3 4 3 6 7 8 9 
        0 1 2 3 4 5 6 7 8 9  确定5的位置
        第五轮 分区3 4 基准数3
        0 1 2 3 4 5 6 7 8 9 确定4的位置
        0 1 2 3 4 5 6 7 8 9 确定3的位置
        第六轮 分区 6 7 基准数6
        0 1 2 3 4 5 6 7 8 9 确定7的位置
        0 1 2 3 4 5 6 7 8 9 确定6的位置
        0 1 2 3 4 5 6 7 8 9

实现代码：

package test;
    
    import java.util.Random;
    
    /**
     * 排序算法
     */
    public class SortTest {
        static int b = 0;
        static int h = 0;
    
        public static void main(String[] args) {
            Random random = new Random();
            int[] nums = new int[10000];
            for (int i = 0; i < nums.length; i++) {
                nums[i] = random.nextInt(nums.length);
            }
            printArr(nums);
    
            printArr(maopao(nums.clone()));
    
            printArr(xuanze(nums.clone()));
    
            printArr(charu(nums.clone()));
    
            printArr(quickSort(nums));
        }
    
        /**
         * 冒泡排序
         * 1、外层循环n-1轮
         * 2、内层循环比较相邻的两个值
         * 3、如果前一个大于后一个，则交换两个值的位置
         *
         * @param nums
         * @return
         */
        public static int[] maopao(int[] nums) {
            long start = System.currentTimeMillis();
            int bj = 0;
            int jh = 0;
            for (int j = 0; j < nums.length; j++) {
                for (int i = 0; i < nums.length - j - 1; i++) {
                    bj++;
                    if (nums[i] > nums[i + 1]) {
                        jh++;
                        int tmp = nums[i];
                        nums[i] = nums[i + 1];
                        nums[i + 1] = tmp;
                    }
                }
            }
            System.out.println("冒泡排序------耗时: " + (System.currentTimeMillis() - start) + "ms, " + "比较次数: " + bj + ", 交换次数: " + jh);
            return nums;
        }
    
        /**
         * 选择排序
         * 1、外层循环n-1轮
         * 2、每次循环选出最小的值
         * 3、最后交换开始值和最小值的位置，所以交换次数固定
         *
         * @param nums
         * @return
         */
        public static int[] xuanze(int[] nums) {
            long start = System.currentTimeMillis();
            int bj = 0;
            int jh = 0;
            int mix, tmp;
            for (int j = 0; j < nums.length; j++) {
                mix = j;
                for (int i = j + 1; i < nums.length; i++) {
                    bj++;
                    if (nums[mix] > nums[i]) {
                        mix = i;
                    }
                }
                jh++;//每轮比较找出最小的数，交换一次
                tmp = nums[j];
                nums[j] = nums[mix];
                nums[mix] = tmp;
            }
            System.out.println("选择排序------耗时: " + (System.currentTimeMillis() - start) + "ms, " + "比较次数: " + bj + ", 交换次数: " + jh);
            return nums;
        }
    
        /**
         * 插入排序
         * 1、外层循环n-1轮
         * 2、每轮循环当前值与前一个值比较，如果当前值小于前一个值，前一个值后移一位，依次向前比较
         * 3、直到当前值大于前一个值，插入在它后面
         *
         * @param nums
         * @return
         */
        public static int[] charu(int[] nums) {
            long start = System.currentTimeMillis();
            int bj = 0;
            int jh = 0;
            int preIndex, current = 0;
            for (int i = 1; i < nums.length; i++) {
                preIndex = i - 1;
                current = nums[i];
                while (preIndex >= 0 && nums[preIndex] > current) {//前一个值大于当前值，
                    bj++;
                    jh++;
                    nums[preIndex + 1] = nums[preIndex];//前一个值移到当前值位置
                    preIndex--;//当前值再与前前一个值比较
                }
                nums[preIndex + 1] = current;//当前值大于preIndex处的值，插入在它后面
            }
            System.out.println("插入排序------耗时: " + (System.currentTimeMillis() - start) + "ms, " + "比较次数: " + bj + ", 交换次数: " + jh);
            return nums;
        }
    
        /**
         * 快速排序
         *
         * @param nums
         * @return
         */
        public static int[] quickSort(int[] nums) {
            long start = System.currentTimeMillis();
            nums = kuaisu(nums, 0, nums.length - 1);
            System.out.println("快速排序------耗时: " + (System.currentTimeMillis() - start) + "ms, " + "比较次数: " + b + ", 交换次数: " + h);
            return nums;
        }
    
        public static int[] kuaisu(int[] nums, int l, int r) {
            if (l > r) {
                // 每次递归排序分区大小为1时，返回
                return nums;
            }
            // 哨兵i向右移动，哨兵j向左移动，基准数x
            int i = l, j = r, x = nums[l];//每次都选择第一个数为基准数
            while (i != j) {
                while (i < j && nums[j] >= x) {
                    b++;
                    j--;//哨兵j从右边向左找第一个小于x的数
                }
                nums[i] = nums[j];//把小于x的数放在基准数x的位置，或已复制到右边的大于基准数的位置
                while (i < j && nums[i] <= x) {
                    b++;
                    i++;//哨兵i从左边向右找第一个大于x的数
                }
                nums[j] = nums[i];//把大于x的数放到已复制到左边的小于x的数的位置
                h++;
            }
            nums[i] = x;//完成一轮循环，确定了一个基准数x的位置
            kuaisu(nums, l, i - 1);
            kuaisu(nums, i + 1, r);
            return nums;
        }
    
        public static void printArr(int[] nums) {
            for (int i : nums) {
                System.out.print(i + " ");
            }
            System.out.println();
        }
    }

排序10000个随机顺序数的结果：

冒泡排序------耗时: 203ms, 比较次数: 49995000, 交换次数: 25069325
    
    选择排序------耗时: 93ms, 比较次数: 49995000, 交换次数: 10000
    
    插入排序------耗时: 31ms, 比较次数: 25069325, 交换次数: 25069325
    
    快速排序------耗时: 0ms, 比较次数: 149399, 交换次数: 31226