插入排序

插入排序（Insertion Sort）是一种简单有效的比较排序算法，属于原地排序。其核心思想是：在每次迭代过程中从输入序列中取出一个元素插入到一个有序序列中，形成新的有序序列。重复该过程，直到序列中所有元素都被取出。

C++

 1 #include<iostream>
 2 using namespace std;
 3 
 4 template<class T>
 5 int length(T& arr)
 6 {
 7     return sizeof(arr) / sizeof(arr[0]);
 8 }
 9 
10 void print(int * const src ,const int src_lenght)
11 {
12     for(int i = 0 ;i<src_lenght;i++)
13         cout<<src[i]<<"  ";
14 
15     cout<<endl;
16 }
17 
18 int * Insertion_sort(int * const src,const int src_lenght)
19 {
20 
21     for (int i = 1; i < src_lenght; i++)// 循环从第二个数组元素开始
22     {
23         //temp标记为未排序的第一个元素
24         int temp = src[i];
25         //将temp与已排序元素从大到小比较，寻找temp应插入的元素
26         while (i >= 0 && src[i - 1] > temp)
27         {
28             src[i] = src[i - 1];
29             i--;
30         }
31         src[i] = temp;
32     }
33 
34     return src;
35 }
36 
37 int main()
38 {
39     int a[6] = {6,-9,10,10,-3,11};
40     Insertion_sort(a,length(a));
41     print(a,length(a));
42 
43     return 0;
44 }

python

"""插入排序"""
def insertionSort(src):
    length = len(src)
    for i in range(1, length):
        x = src[i]
        for j in range(i, -1, -1):
            # j为当前位置，试探j-1位置
            if x < src[j - 1]:
                src[j] = src[j - 1]
            else:
                # 位置确定为j
                break
        src[j] = x
    return src


a = [6,8,1,0,3,6,4,5]
print(insertionSort(a))