使用python实现8大排序算法-插入排序

巴扎黑
Lepaskan: 2016-12-03 11:26:31
asal
1331 orang telah melayarinya

插入排序的基本思想:

每步将一个待排序的纪录,按其关键码值的大小插入前面已经排序的文件中适当位置上,直到全部插入完为止。

例:

       arr = [49,38,04,97,76,13,27,49,55,65],从第2个数为关键值,向前比较,如前一个数大,进行交换,

       arr = [38,49,04,97,76,13,27,49,55,65],然后再从第3个数为关键值,向前比较,前大则交换,

       arr = [38,04,49,97,76,13,27,49,55,65],再继续,arr = [04,38,49,97,76,13,27,49,55,65]

       备注:依次向前比较时,因为前面的阵列是有序的,所以当前一个数小于或等于key值时,可以跳出这个向前比较的循环,算法的速度有明显提升。

代码:

def insert_sort(lists):  
    #插入排序  
    count = len(lists)  
    for i in range(1,count):#从第2个数起遍历  
        key = lists[i]  
        j = i - 1  
        while j >= 0:  
            if lists[j] > key:  
                lists[j+1], lists[j] = lists[j], key  
            else: break  #当前一个数小于或等于key时,跳出循环  
            j -= 1  
    return lists
Salin selepas log masuk


Label berkaitan:
sumber:php.cn
Kenyataan Laman Web ini
Kandungan artikel ini disumbangkan secara sukarela oleh netizen, dan hak cipta adalah milik pengarang asal. Laman web ini tidak memikul tanggungjawab undang-undang yang sepadan. Jika anda menemui sebarang kandungan yang disyaki plagiarisme atau pelanggaran, sila hubungi admin@php.cn
Tutorial Popular
Lagi>
Muat turun terkini
Lagi>
kesan web
Kod sumber laman web
Bahan laman web
Templat hujung hadapan