面试常问的排序算法和经典算法（代码示例）

关于时间复杂度：

1. 平方阶 (O(n2)) 排序 各类简单排序：直接插入、直接选择和冒泡排序。
2. 线性对数阶 (O(nlog2n)) 排序 快速排序、堆排序和归并排序。
3. O(n1+§)) 排序，§ 是介于 0 和 1 之间的常数。希尔排序。
4. 线性阶 (O(n)) 排序 基数排序，此外还有桶、箱排序。

关于稳定性：

稳定的排序算法：冒泡排序、插入排序、归并排序和基数排序。

不是稳定的排序算法：选择排序、快速排序、希尔排序、堆排序。

  
	@Test
    public void bubbleSort(String[] args) {
        int[] num = new int[]{3, 2, 1, 4, 5, 6, 8, 9, 7};
        // 需进行length-1次冒泡
        for (int i = 0; i < num.length - 1; i++) {
            for (int j = 0; j < num.length - 1 - i; j++) {
                // 比较并交换
                if (num[j] > num[j + 1]) {
                    int temp = num[j];
                    num[j] = num[j + 1];
                    num[j + 1] = temp;
                }
            }
        }
        System.out.println("从小到大排序后的结果是:");
        for (int i = 0; i < num.length; i++) {
            System.out.print(num[i] + " ");
        }
    }

    
    @Test
    public void selectionSort() {
        int[] num = new int[]{3, 2, 1, 4, 5, 6, 8, 9, 7};
        // 需进行length-1次遍历
        for (int i = 0; i < num.length - 1; i++) {
            // 记录最小值的索引位置，默认值为i
            int index = i;
            for (int j = i + 1; j < num.length; j++) {
                // 获取最小值的下标
                if (num[j] < num[index]) {
                    index = j;
                }
            }
            // 交换位置
            if (i != index) {
                int temp = num[i];
                num[i] = num[index];
                num[index] = temp;
            }
        }
        System.out.println("从小到大排序后的结果是:");
        for (int i = 0; i < num.length; i++) {
            System.out.print(num[i] + " ");
        }
    }

	
    @Test
    public void insertionSort() {
        int[] num = new int[]{3, 2, 1, 4, 5, 6, 8, 9, 7};
        for (int i = 1; i < num.length; i++) {
            for (int j = i; j > 0; j--) {
                if (num[j] < num[j - 1]) {
                    int temp = num[j - 1];
                    num[j - 1] = num[j];
                    num[j] = temp;
                }
            }
        }
        System.out.println("从小到大排序后的结果是:");
        for (int i = 0; i < num.length; i++) {
            System.out.print(num[i] + " ");
        }
    }

	
    @Test
    public void shellSortSmallToBig() {
        int[] num = new int[]{3, 2, 1, 4, 5, 6, 8, 9, 7};
        int j = 0;
        int temp = 0;
        for (int increment = num.length / 2; increment > 0; increment /= 2) {
            for (int i = increment; i < num.length; i++) {
                temp = num[i];
                for (j = i - increment; j >= 0; j -= increment) {
                    if (temp < num[j]) {
                        num[j + increment] = num[j];
                    } else {
                        break;
                    }
                }
                num[j + increment] = temp;
            }
        }
        System.out.println("从小到大排序后的结果是:");
        for (int i = 0; i < num.length; i++) {
            System.out.print(num[i] + " ");
        }
    }

	
    @Test
    public void mergeSort () {
        int[] num = new int[]{3, 2, 1, 4, 5, 6, 8, 9, 7};
        int j = 0;
        int temp = 0;
        for (int increment = num.length / 2; increment > 0; increment /= 2) {
            for (int i = increment; i < num.length; i++) {
                temp = num[i];
                for (j = i - increment; j >= 0; j -= increment) {
                    if (temp < num[j]) {
                        num[j + increment] = num[j];
                    } else {
                        break;
                    }
                }
                num[j + increment] = temp;
            }
        }
        System.out.println("从小到大排序后的结果是:");
        for (int i = 0; i < num.length; i++) {
            System.out.print(num[i] + " ");
        }
    }

public class QuickSort {
    public static void sort(int a[], int low, int hight) {
        int i, j, index;
        if (low > hight) {
            return;
        }
        i = low;
        j = hight;
        index = a[i]; // 用子表的第一个记录做基准
        while (i < j) { // 从表的两端交替向中间扫描
            while (i < j && a[j] >= index) {
                j--;
            }
            if (i < j) {
                a[i++] = a[j];// 用比基准小的记录替换低位记录
            }
            while (i < j && a[i] < index) {
                i++;
            }
            if (i < j) // 用比基准大的记录替换高位记录
            {
                a[j--] = a[i];
            }
        }
        a[i] = index;// 将基准数值替换回 a[i]
        sort(a, low, i - 1); // 对低子表进行递归排序
        sort(a, i + 1, hight); // 对高子表进行递归排序

    }

    public static void quickSort(int a[]) {
        sort(a, 0, a.length - 1);
    }

    public static void main(String[] args) {

        int arr[] = {49, 38, 65, 97, 76, 13, 27, 49};
        quickSort(arr);
        System.out.println("从小到大排序的结果为: " + Arrays.toString(arr));
    }

}

public class CountingSort {
    public static int[] countingSort(int[] array) {
        if (array.length == 0) {
            return array;
        }
        int bias, min = array[0], max = array[0];
        for (int i = 1; i < array.length; i++) {
            if (array[i] > max) {
                max = array[i];
            }
            if (array[i] < min) {
                min = array[i];
            }
        }
        bias = 0 - min;
        int[] bucket = new int[max - min + 1];
        Arrays.fill(bucket, 0);
        for (int i = 0; i < array.length; i++) {
            bucket[array[i] + bias]++;
        }
        int index = 0, i = 0;
        while (index < array.length) {
            if (bucket[i] != 0) {
                array[index] = i - bias;
                bucket[i]--;
                index++;
            } else {
                i++;
            }
        }
        return array;
    }

    public static void main(String[] args) {
        int[] arr = new int[]{5, 3, 6, 2, 1, 9, 4, 8, 7};
        countingSort(arr);
        System.out.println("从小到大排序的结果为: " + Arrays.toString(arr));

    }

}

public class RadixSort {
    public static void main(String[] args) {
        //定义整型数组
        int[] arr = {21, 56, 88, 195, 354, 1, 35, 12, 6, 7};
        //调用基数排序函数
        lsd_RadixSort(arr, 3);
        //输出排序后的数组
        System.out.println("从小到大排序的结果为: " + Arrays.toString(arr));
    }

    
    public static void lsd_RadixSort(int[] arr, int max) {
        //count数组用来计数
        int[] count = new int[arr.length];
        //bucket用来当桶（在下面你就理解了什么是桶了），放数据，取数据
        int[] bucket = new int[arr.length];

        //k表示第几位，1代表个位，2代表十位，3代表百位
        for (int k = 1; k <= max; k++) {
            //把count置空，防止上次循环的数据影响
            for (int i = 0; i < arr.length; i++) {
                count[i] = 0;
            }

            //分别统计第k位是0,1,2,3,4,5,6,7,8,9的数量
            //以下便称为桶
            //即此循环用来统计每个桶中的数据的数量
            for (int i = 0; i < arr.length; i++) {
                count[getFigure(arr[i], k)]++;
            }

            //利用count[i]来确定放置数据的位置
            for (int i = 1; i < arr.length; i++) {
                count[i] = count[i] + count[i - 1];
            }
            //执行完此循环之后的count[i]就是第i个桶右边界的位置

            //利用循环把数据装入各个桶中，注意是从后往前装
            //这里是重点，一定要仔细理解
            for (int i = arr.length - 1; i >= 0; i--) {
                int j = getFigure(arr[i], k);
                bucket[count[j] - 1] = arr[i];
                count[j]--;
            }

            //将桶中的数据取出来，赋值给arr
            for (int i = 0, j = 0; i < arr.length; i++, j++) {
                arr[i] = bucket[j];
            }

        }
    }

    //此函数返回整型数i的第k位是什么
    public static int getFigure(int i, int k) {
        int[] a = {1, 10, 100};
        return (i / a[k - 1]) % 10;
    }

}

public class Faibonacci {
    public static void main(String[] args) {
        System.out.println("请输入您要测试的数:");
        int n = new Scanner(System.in).nextInt();
        //判断n是否是不正常的范围
        if (n < 1) {
            System.out.println("输入数据有误！！！");
        }
        //n==1
        if (n == 1) {
            System.out.println(0);
        }
        //n==2
        if (n == 2) {
            System.out.println(0 + "t" + 1);
        }
        //n==3
        if (n == 3) {
            System.out.println(0 + "t" + 1 + "t" + 1);
        }
        //拼接前n项
        if (n > 3) {
            System.out.print(0 + "t" + 1 + "t" + 1 + "t");
        }
        //循环输出后面的数据
        int f1 = 1;
        int f2 = 1;
        int next = 0;
        for (int i = 4; i <= n; i++) {
            next = f1 + f2;
            f1 = f2;
            f2 = next;
            System.out.print(next + "t");
        }
    }
}

public class GetRabbitNum {
    public static void main(String[] args) {
        System.out.println("请输入要判断的月数：");
        int month = new Scanner(System.in).nextInt();
        System.out.println("第" + month + "月兔子的对数为：" + getSum(month));
    }

    public static int getSum(int month) {
        //如果是前两个月，还是1对兔子
        if (month == 1 || month == 2) {
            return 1;
        } else {
            //从第三个开始，兔子按照2 3 5 8 13 21变化
            return getSum(month - 1) + getSum(month - 2);
        }
    }
}

public class GetDaffodilNum {
    public static void main(String[] args) {
        //1.遍历所有的三位数
        for (int i = 100; i < 1000; i++) {
            //2.调用自定义方法判断是不是水仙花数
            if (isAim(i)) {
                //3.如果是水仙花数，就打印
                System.out.println(i);
            }
        }
    }

    //4.自定义判断水仙花数的方法
    public static boolean isAim(int a) {
        int x = a / 100;
        int y = a / 10 % 10;
        int z = a % 10;
        if (a == x * x * x + y * y * y + z * z * z) {
            return true;
        }
        return false;
    }
}

public class TestNumber {
    public static void main(String[] args) {
        System.out.println("请输入一个字符串:");
        String s = new Scanner(System.in).nextLine();

        if (!stringJudge(s)) {
            System.out.println(s + "不是回文字符串");
        } else {
            System.out.println(s + "是回文字符串");
        }

    }

    //判断字符串是否回文
    private static boolean stringJudge(String str) {
        for (int i = 0; i < str.length() - i - 1; i++) {
            if (str.charAt(i) == str.charAt(str.length() - i - 1)) {
                continue;
            } else {
                return false;
            }
        }

        return true;
    }

}

public class DichotomizingSearch {
    public static void main(String[] args) {
        // 二分法查找
        int[] binaryNums = {1, 6, 15, 18, 27, 50};
        int findValue = 27;
        int binaryResult = binarySearch(binaryNums, 0, binaryNums.length - 1, findValue);
        System.out.println("元素第一次出现的位置（从0开始）：" + binaryResult);
    }

    
    private static int binarySearch(int[] nums, int start, int end, int findValue) {
        if (start <= end) {
            // 中间位置
            int middle = (start + end) / 2;
            // 中间的值
            int middleValue = nums[middle];
            if (findValue == middleValue) {
                // 等于中值直接返回
                return middle;
            } else if (findValue < middleValue) {
                // 小于中值，在中值之前的数据中查找
                return binarySearch(nums, start, middle - 1, findValue);
            } else {
                // 大于中值，在中值之后的数据中查找
                return binarySearch(nums, middle + 1, end, findValue);
            }
        }
        return -1;
    }
}

6.杨辉三角

public class TriangleArray {
    public static void main(String[] args) {
        final int NMAX = 10;
        // allocate triangular array
        int[][] odds = new int[NMAX + 1][];
        for (int n = 0; n <= NMAX; n++) {
            odds[n] = new int[n + 1];
        }
        // fill triangular array
        for (int n = 0; n < odds.length; n++) {
            for (int k = 0; k < odds[n].length; k++) {
                
                int lotteryOdds = 1;
                for (int i = 1; i <= k; i++)
                    lotteryOdds = lotteryOdds * (n - i + 1) / i;

                odds[n][k] = lotteryOdds;
            }
        }

        for (int[] row : odds) {
            for (int odd : row) {
                System.out.printf("%4d", odd);
            }
            System.out.println();
        }
    }
}

由于网页不好传动图，排序算法的动图关注私信我领取