直接插入排序算法思想：
每步将一个待排序的纪录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。
range：
range是左闭右开
for i in range(5):
      print(i)

输出1 2 3 4
直接插入排序代码实现：
def insert_sort(alist):
    n=len(alist)
    for j in range(1,n):  
        for i in range(j):
            if alist[i] > alist[j]:
               alist[j],alist[i]=alist[i],alist[j]
    #return alist
                
                
if __name__ =="__main__":
    alist=[0,1,8,7,9,2,10]
    print(alist)
    insert_sort(alist)
    print(alist) 

此方法是每次都和前面的第一个进行比较，如果前面的大，那么交换，如果一直不大，那么其在原位置不动。其中每次交换后
def insert_sort(alist):
    n=len(alist)
    for j in range(1,n):  
        for i in range(j,0,-1):
            if alist[i] < alist[i-1]:
               alist[i],alist[i-1]=alist[i-1],alist[i]
    #return alist
                
                
if __name__ =="__main__":
    alist=[0,1,8,7,9,2,10]
    print(alist)
    insert_sort(alist)
    print(alist) 

最常见的是此种方法，每次都是把要比较的那个和前面那个进行比较，如果比前面那个小，则进行交换，一直到和第一个比较完毕。这里不懂的地方是怎么从后往前来用Python书写，其(j,0,-1)从 j 开始到 1 步长 -1
def insert_sort(alist):
    n=len(alist)
    for j in range(1,n):  
        i=j
        while i > 0:
            if alist[i] < alist[i-1]:
               alist[i],alist[i-1]=alist[i-1],alist[i]
               i-=1
            else:
                break;
    #return alist
                
                
if __name__ =="__main__":
    alist=[0,1,8,7,9,2,10]
    print(alist)
    insert_sort(alist)
    print(alist) 

while方法写直接插入排序
range用法巩固

range(9) 为0~8的有序集合
range(start,stop,[step])  start表示数字的开始值，stop代表数字的结束值，step代表循环时数字递增的步长(默认值为1）

1.1排序基本概念

排序：重新排列表中的元素，使表中的元素满足按关键字递增或递减的过程。

算法的稳定性：如果待排序表中有两个元素Ri、Rj，其对应的关键字keyi=keyj，且在排序前Ri在Rj前面，如果使用某一排序算法排序后，Ri仍在Rj的前面，则称这个排序算法是稳定的。

分类：在排序过程中，根据数据元素是否完全在内存中，可将排序算法分为两类。

         内部排序：在排序期间元素全部存放在内存中的排序。

         外部排序：在排序期间元素无法全部同时存放在内存中，必须在排序过程中根据要求不断地在内外存之间移动的排序。

1.2插入排序

基本思想：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子序列中，直到全部记录完成。

1.2.1直接插入排序

原理：把n个待排序的元素看成一个有序表和一个无需表，开始的时候有序表只有1个元素，无序表中有n-1个元素每次从无序表中取出第一个元素，将它插入到有序表中，使之成为新的有序表，重复n-1次完成整个排序过程。

具体流程如下：

首先比较数组的前两个数据，并排序；
	
比较第三个元素与前两个排好序的数据，并将第三个元素放入适当的位置；
	
比较第四个元素与前三个排好序的数据，并将第四个元素放入适当的位置；

	…
	
直至把最后一个元素放入适当的位置
实例：

0.初始状态 3，1，5，7，2，4，9，6（共8个数）

有序表：3；无序表：1，5，7，2，4，9，6

1.第一次循环，从无序表中取出第一个数 1，把它插入到有序表中，使新的数列依旧有序

有序表：1，3；无序表：5，7，2，4，9，6

2.第二次循环，从无序表中取出第一个数 5，把它插入到有序表中，使新的数列依旧有序

有序表：1，3，5；无序表：7，2，4，9，6

3.第三次循环，从无序表中取出第一个数 7，把它插入到有序表中，使新的数列依旧有序

有序表：1，3，5，7；无序表：2，4，9，6

4.第四次循环，从无序表中取出第一个数 2，把它插入到有序表中，使新的数列依旧有序

有序表：1，2，3，5，7；无序表：4，9，6

5.第五次循环，从无序表中取出第一个数 4，把它插入到有序表中，使新的数列依旧有序

有序表：1，2，3，4，5，7；无序表：9，6

6.第六次循环，从无序表中取出第一个数 9，把它插入到有序表中，使新的数列依旧有序

有序表：1，2，3，4，5，7，9；无序表：6

7.第七次循环，从无序表中取出第一个数 6，把它插入到有序表中，使新的数列依旧有序

有序表：1，2，3，4，5，6，7，9；无序表：（空）

性能分析：

空间效率：仅使用常数个辅助单元，空间复杂度O(1)
时间效率：时间复杂度O(n2)

                最差情况：反序，需要移动n*(n-1)/2个元素，时间复杂度O(n2)

                最好情况：正序，不需要移动元素，时间复杂度O(n)

稳定性：稳定的

适用性：适用于顺序存储和链式存储的线性表

import java.util.Scanner;
import java.util.Arrays;
public class InsertSort {
    public static void insertSort(int[] arr){
        int i=0,j=0,temp=0;//定义变量i,j,temp并初始化
        for (i=1;i<arr.length;i++){//从第二个开始比较
            temp = arr[i];
            for (j=i-1;j>=0;j--){
                if (arr[j]>temp){//如果前面的数大于当前数，将它后移
                    arr[j+1] = arr[j];
                }else {
                    break;
                }
            }
            arr[j+1] = temp;//一轮比较结束，将此轮确定元素放到正确位置
        }
        System.out.println("直接插入排序："+Arrays.toString(arr));
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);//Scanner工具类键盘输入数据
        while (scanner.hasNext()) {
            int n = scanner.nextInt();
            if (n > 0) {
                int arr[] = new int[n];
                for (int i = 0; i < n; i++) {
                    arr[i] = scanner.nextInt();
                }
                insertSort(arr);//调用直接插入排序insertSort方法
            }
        }
    }
}



 

直接插入排序算法的思想：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子序列中，直到全部记录插入完成。 

代码如下：



这里写代码片def insert_sort(a,n):
    #a是待排序的数组，n是数组的长度
    for i in range(1,n):#将循环从1开始而不是从0开始
        if a[i-1]>a[i]:#如果带插入的值小于前面的值，就将带插入的值赋值给t
            #j是为了给带插入的元素寻找位置而添加的变量
            t=a[i]
            j=i-1
            while a[j]>t and j>=0:
                a[j+1]=a[j]
                j-=1
            a[j+1]=t#因为在while循环的时候j值已经减了一,所以最后要把这个1加上

a=[3,1,2,6,8,5]
insert_sort(a,len(a))
print(a)

目录

插入排序

直接排序

一、排序原理

二、时间复杂度

三、 动画演示

​四、实现代码

五、算法分析： 

概念：所谓排序，就是整理文件中的记录。使之按关键字递增（或递减）的次序排列起来，当待排序关键字均不相同时，排序结果是唯一的，否则排序结果不唯一。

插入排序

基本思想：每步将一个待排序码值的大小，插到前面已经排好的文件中的适当位置，直到全部插入完为止。插入排序方法主要有直接插入排序和希尔排序。

直接排序

一、排序原理



      核心思想：插入排序通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入 ，如此重复，直至完成序列排序。

（类似于扑克牌，打牌的时候，你拿一张牌，你要排一下顺序，看拿到的牌的大小，大的往后，小的直接插前面，但不同的是你拿到牌直接能看出来放哪，而在计算机里的排序，必须先比较，前面已经排好的数字，你才知道放哪），直接插入排序就是按这个思想来走的。

二、时间复杂度

 

1. 直接插入排序最好的时间复杂度为O(n)

2. 直接插入排序的最坏时间复杂度为O(n^2)

3. 因此直接插入排序总的平均时间复杂度为O(n^2)

注：具有稳定性

 

三、 动画演示



四、实现代码

// 直接插入排序(C++)
void InsertSort(vector<int> &vi)
{
    for(int i=1;i<vi.size();i++) 
    {
        int temp=vi[i];
        int j;
        for(j=i-1;j>=0&&temp<vi[j];j--)
        {
            vi[j+1]=vi[j]；     //将较大元素后移
        }

        vi[j+1]=temp;        //temp插入正确的位置

    }
}

五、算法分析： 


1. 从序列第一个元素开始，该元素可以认为已经被排序 

2. 取出下一个元素，设为待插入元素，在已经排序的元素序列中从后向前扫描，如果该元素（已排序）大于待插入元素，将该元素移到下一位置。 

3. 重复步骤2，直到找到已排序的元素小于或者等于待排序元素的位置，插入元素 

4. 重复2，3步骤，完成排序。