int nums[10],x;
cin>>x;
for(int i=0;i

• 1
• 2
• 3
• 4
• 5
• 6

空间复杂度上面仅仅引入i这个变量为O（1）。
时间复杂度为最坏情况下的O（n）

插入排序

原理：每次插入一个元素，每一趟完成对一个待排元素的放置，直到全部插入完成。

直接插入排序

将每个待排元素插入到已知的已经排好的序列中。（每次从原有数据中取出一个新排列，插入到之前已经排好的序列中，直到所有数字取完，这个新排列就完成了）

算法详解：
假设前面 n-1(其中 n>=2)个数已经是排好顺序的，现将第 n 个数插到前面已经排好的序列中，然后找到合适自己的位置，使得插入第n个数的这个序列也是排好顺序的。

从小到大的插入排序整个过程如图示：

第一轮：从第二位置的 6 开始比较，比前面 7 小，交换位置。

第二轮：第三位置的 9 比前一位置的 7 大，无需交换位置。

第三轮：第四位置的 3 比前一位置的 9 小交换位置，依次往前比较。

第四轮：第五位置的 1 比前一位置的 9 小，交换位置，再依次往前比较。

public class InsertionSort {
    public static void sort(Comparable[] arr){
    
        int n = arr.length;
        for (int i = 0; i < n; i++) {
            // 寻找元素 arr[i] 合适的插入位置
           for( int j = i ; j > 0 ; j -- )
                if( arr[j].compareTo( arr[j-1] ) < 0 )
                    swap( arr, j , j-1 );
                else
                    break;
        }
    }
    //核心代码---结束
   }
 }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

折半插入排序

由于在插入排序的过程中，已经生成一个有序序列。所以在插入待排序元素时用折半查找能更快确定新元素的位置。当元素个数较多的时候，折半插入排序优于直接插入排序。

希尔排序

将全部元素分成几组之后，在每一组内使用直接插入排序，然后继续减少间距，形成新的分组进行排序，直到间距为0为止。