插入排序

网上一查定义全都有。这里不做赘述。
我觉得最好的对插入排序的比喻就是斗地主的摸牌，摸一张看看顺序插入一下。
数组分两个部分，有序区，无序区。
你手牌就是有序区。堆着的那些牌就是无序区。

先看下经典的代码实现再来讲解注意点。
参考链接 Python Program for Insertion Sort

Python代码实现

"""  
方法1:利用while进行判断然后从后向前  
方法2:利用for进行判断从后向前  
"""  
def insertionSort(arr):    
    for i in range(1, len(arr)):    
        j = i     
        while j > 0:    
            if arr[j] < arr[j-1]:    
                arr[j-1], arr[j] = arr[j], arr[j-1]    
                j-=1  
            else:  
                break  
            # 已经最大无需对比所以加入了break这样最优时间复杂度为n   
    return arr    

arr = [ 5, 6,18,4,9,-5,3,11]     
print(insertionSort(arr))    

# result    
# [-5, 3, 4, 5, 6, 9, 11, 18]    

def insertionSort(arr):  
    for i in range(1, len(arr)):  
        for j in range(i,0,-1):  
            if arr[j] < arr[j-1]:  
                arr[j], arr[j-1] = arr[j-1], arr[j]  
    return arr  
arr = [66,4,8,90,13,6,-9]  
print(insertionSort(arr))  

# result    
# [-5, 3, 4, 5, 6, 9, 11, 18]

我来说一下几个点吧。
Q:为什么从1开始。
前面说了，玩扑克的时候你也是从摸第二张的时候才知道该插哪里吧。第1张不需要插入，属于默认的有序区。
拿着的第1张牌默认是排好的，所以从index为1开始，而不是0。
Q:i为什么赋值给了j
这代表有序区最大的index值
因为插入排序基本的观点就是从后向前扫。
Q:从后向前扫进行交换是什么意思？
从后: i赋值给了j这样就得到了后这个字的含义，得到最大的index才能向前啊！
从后向前:只要j还是大于0，那么就自减1。
交换不必说了。只要我比你小，那么我就接着向前走。

C语言辅助理解

接下来我贴一个C语言实现，其实我也不会C语言指针结构体太难的什么的。
只要上网花一天时间看一下基本的数据类型和语法结构，就这种程度就可以看懂。
如果你要去学习数据结构和算法，那么最好从C语言这种编译型的语言辅助你理解。

#include <math.h>   
#include <stdio.h>   

void insertionSort(int arr[], int n)   
{   
    int i, key, j;   
    for (i = 1; i < n; i++) {   
        key = arr[i];   
        j = i - 1;    
        while (j >= 0 && arr[j] > key) {   
            arr[j + 1] = arr[j];   
            j = j - 1;   
        }   
        arr[j + 1] = key;   
    }   
}   


void printArray(int arr[], int n)   
{   
    int i;   
    for (i = 0; i < n; i++)   
        printf("%d ", arr[i]);   
    printf("\n");   
}   

int main()   
{   
    int arr[] = { 12, 11, 13, 5, 6 };   
    int n = sizeof(arr) / sizeof(arr[0]);   

    insertionSort(arr, n);   
    printArray(arr, n);   

    return 0;   
}

『Insertion Sort』详解「插入排序」的Python实现

插入排序

Python代码实现

C语言辅助理解

『Selection Sort』详解「选择排序」的Python实现

『QuickSort』详解「快速排序」的Python实现

共有评论(0)

Chihokyo 旺财