溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務(wù)條款》
您好，登錄后才能下訂單哦！
Python中怎樣實現(xiàn)插入排序，很多新手對此不是很清楚，為了幫助大家解決這個難題，下面小編將為大家詳細講解，有這方面需求的人可以來學習下，希望你能有所收獲。
插入排序
插入排序（Insertion Sort）的算法時間復(fù)雜度也是O(n^2)，但思路與冒泡排序以及選擇排序截然不同
插入排序有點類似于日常生活中的“打撲克牌”
插入排序思路：維持好一個已排序好的子列表，其位置始終在列表的前部，然后逐步擴大這個子列表直到全表
簡單來說：對于一個輸入的無序表，分成兩個部分，前部分是已排序子列表，后部分是待排序數(shù)據(jù)。每一趟插入排序都從后面的數(shù)據(jù)找一個插入到前面已排序的子列表中（要找到其合適位置），最后完成全部數(shù)據(jù)排序
步驟：
第一趟插入排序：前面的子列表僅包含一個元素，待插入數(shù)據(jù)從第二個元素開始。將第二個元素插入到子列表的合適位置，完成兩個元素的排列
第二趟插入排序：將第三個元素插入到子列表合適位置，完成前三個數(shù)據(jù)項的排序
……
第n-1趟插入排序：最后一個數(shù)據(jù)插入到子列表合適位置，完成所有元素排序
插入排序的數(shù)據(jù)比對主要在于尋找待插入元素的合適位置
最差情況：比對要與子列表所有元素發(fā)送——O(n^2)
最好情況：每一趟插入排序只需發(fā)生一次比對——O(n)
找到“合適位置
插入排序找到合適位置的具體思路：
將待插入元素取出（存儲在一個變量中）空出這個位置（記錄這個位置），將這個取出的元素與子列表從后向前的元素逐個比對，若待插入元素小，則將子列表元素向后移動一位……直到整個子列表比對完或者待插入元素大于當前子列表元素則停止循環(huán)。將待插入元素插入當前位置
看完上述內(nèi)容是否對您有幫助呢？如果還想對相關(guān)知識有進一步的了解或閱讀更多相關(guān)文章，請關(guān)注億速云行業(yè)資訊頻道，感謝您對億速云的支持。
免責聲明：本站發(fā)布的內(nèi)容（圖片、視頻和文字）以原創(chuàng)、轉(zhuǎn)載和分享為主，文章觀點不代表本網(wǎng)站立場，如果涉及侵權(quán)請聯(lián)系站長郵箱：is@yisu.com進行舉報，并提供相關(guān)證據(jù)，一經(jīng)查實，將立刻刪除涉嫌侵權(quán)內(nèi)容。
億速云公眾號
手機網(wǎng)站二維碼
