后端面试每日一题插入排序和选择排序

淩亂°似流年 2022-10-16 06:11 120阅读 0赞

*  插入排序

插入排序（Insertion Sort）算法是指依次循环当前的列表，通过对比将每个元素插入到合适的位置，它的具体执行过程，如下图所示：

![img][]  
插入算法的具体实现代码如下：

public class AlgorithmExample {
        public static void main(String[] args) {
            int[] insertNums = {4, 33, 10, 13, 49, 20, 8};
            // 插入排序调用
            insertSort(insertNums);
            System.out.println("插入排序后：" + Arrays.toString(insertNums));
        }
        /**
         * 插入排序
         */
        private static void insertSort(int[] nums) {
            int i, j, k;
            for (i = 1; i < nums.length; i++) {
                k = nums[i];
                j = i - 1;
                // 对 i 之前的数据，给当前元素找到合适的位置
                while (j >= 0 && k < nums[j]) {
                    nums[j + 1] = nums[j];
                    // j-- 继续往前寻找
                    j--;
                }
                nums[j + 1] = k;
            }
        }
    }

以上程序的执行结果为：

插入排序后：[4, 8, 10, 13, 20, 33, 49]

*  选择排序

选择排序（Selection Sort）算法是指依次循环数组，每轮找出最小的值放到数组的最前面，直到循环结束就能得到一个有序数组，它的执行过程如下图所示：  
![img][img 1]  
选择排序的具体实现代码如下：

public class AlgorithmExample {
        public static void main(String[] args) {
            int[] insertNums = {4, 33, 10, 13, 49, 20, 8};
            // 调用选择排序
            selectSort(insertNums);
            System.out.println("选择排序后结果：" + Arrays.toString(insertNums));
        }
        /**
         * 选择排序
         */
        private static void selectSort(int[] nums) {
            int index;
            int temp;
            for (int i = 0; i < nums.length - 1; i++) {
                index = i;
                for (int j = i + 1; j < nums.length; j++) {
                    if (nums[j] < nums[index]) {
                        index = j;
                    }
                }
                if (index != i) {
                    temp = nums[i];
                    nums[i] = nums[index];
                    nums[index] = temp;
                }
                System.out.print("第" + i + "次排序：");
                System.out.println(Arrays.toString(nums));
            }
        }
    }

以上程序的执行结果为：

第0次排序：[4, 33, 10, 13, 49, 20, 8]
    第1次排序：[4, 8, 10, 13, 49, 20, 33]
    第2次排序：[4, 8, 10, 13, 49, 20, 33]
    第3次排序：[4, 8, 10, 13, 49, 20, 33]
    第4次排序：[4, 8, 10, 13, 20, 49, 33]
    第5次排序：[4, 8, 10, 13, 20, 33, 49]
    选择排序后结果：[4, 8, 10, 13, 20, 33, 49]

[img]: /images/20221014/09282527a8a44e628df0df38150da0b5.png
[img 1]: /images/20221014/c8ab6e5db837496cb69ad8408a87e95a.png