【228期】面试高频：Java常用的八大排序算法一网打尽！

小半 • 2022年5月17日下午4:03 • 面试题 • 阅读 249

来源：jianshu.com/p/5e171281a387

1.直接插入排序

经常碰到这样一类排序问题：把新的数据插入到已经排好的数据列中。

将第一个数和第二个数排序，然后构成一个有序序列
将第三个数插入进去，构成一个新的有序序列。
对第四个数、第五个数……直到最后一个数，重复第二步。

如何写成代码：

首先设定插入次数，即循环次数，for(int i=1;i<length;i++)，1个数的那次不用插入。
设定插入数和得到已经排好序列的最后一个数的位数。insertNum和j=i-1。
从最后一个数开始向前循环，如果插入数小于当前数，就将当前数向后移动一位。
将当前数放置到空着的位置，即j+1。

代码实现如下：

public void sort(int[] array) {  
        //首先确定排序的趟数;       
        int max = array[0];  
        for (int i = 1; i < array.length; i++) {  
            if (array[i] > max) {  
                max = array[i];  
            }  
        }  
        int time = 0;  
        //判断位数;       
        while (max > 0) {  
            max /= 10;  
            time++;  
        }  
        //建立10个队列;       
        List<ArrayList> queue = new ArrayList<ArrayList>();  
        for (int i = 0; i < 10; i++) {  
            ArrayList<Integer> queue1 = new ArrayList<Integer>();  
            queue.add(queue1);  
        }  
        //进行time次分配和收集;       
        for (int i = 0; i < time; i++) {  
            //分配数组元素;       
            for (int j = 0; j < array.length; j++) {  
                //得到数字的第time+1位数;     
                int x = array[j] % (int) Math.pow(10, i + 1) / (int) Math.pow(10, i);  
                ArrayList<Integer> queue2 = queue.get(x);  
                queue2.add(array[j]);  
                queue.set(x, queue2);  
            }  
            int count = 0;//元素计数器;       
            //收集队列元素;       
            for (int k = 0; k < 10; k++) {  
                while (queue.get(k).size() > 0) {  
                    ArrayList<Integer> queue3 = queue.get(k);  
                    array[count] = queue3.get(0);  
                    queue3.remove(0);  
                    count++;  
                }  
            }  
        }  
    }