基础算法练习03--直接插入排序

水深无声 2024-02-19 13:58 23阅读 0赞

**直接插入排序是一种简单的排序方法，它的基本操作是将一个纪录插入到已经排好的记录中，从而得到一个新的、记录数增1的有序表。**

**代码:**

import java.util.Arrays;
    
    /**
     * 使用数组进行演示：
     * 首先我们将数组的第一个元素作为"有序表"，其余的元素作为 "无序表"
     * 排序方法：
     * 	1.将 arr[1] 加入到 "有序表"中，和arr[0] 比较，若arr[1]>arr[0] 则交换位置
     * 	2.将 arr[2] 加入到 "有序表"中，和arr[1]进行比较，若arr[2]>arr[1] 则交换位置
     * 	     然后将arr[1]和arr[0] 比较，若arr[1]>arr[0] 交换位置 以此类推
     *      3.重复进行比较和交换直到数组中的元素都是有序的
     * @author drc
     *
     */
    public class StraightInsertSortDemo {
        public static void main(String[] args) {
    	// 测试
    	int[] arr = {7, 3, 9, 2, 11, 44, 6, 1, 77};
    	straightInsertSort(arr);
    	System.out.println(Arrays.toString(arr));
        }
        /**
         * 直接插入排序
         * @param arr
         * @return
        */
        static int[] straightInsertSort(int[] arr) {
    	int order = 1; // 初始有序序列长度为1
    	while (order<arr.length) { // 当整个数组变成有序的时候退出循环
    	    for (int x=order-1; x>=0; x--) { // 从有序序列的最后一个元素开始比较
    		if (arr[x] > arr[x+1]) {
    		    arr[x] = arr[x]+arr[x+1];
    		    arr[x+1] = arr[x]-arr[x+1];
    		    arr[x] = arr[x]-arr[x+1];
    		} else {
                        order++; // 每插入一个元素，有序表的长度增1
                        break; // 元素插入后即可跳出for循环
                    }
    	    }
    	}
            return arr;
        }
    }