將一個數組,按當前元素的大小,插入到前面已經排好序的數據中的適當位置中,
依次直到全入插入完全.
下面是一個數組在經過插入排序時的變化情況(t表次數times)
Init---{7, 4, 3, 2, 5, 6, 1}? 初始
t=1----{4, 7, 3, 2, 5, 6, 1}? 將第1個元素按其大小插到前面排好序的數列的相應位置
t=2----{3, 4, 7, 2, 5, 6, 1}? 將第2個元素按其大小插到前面排好序的數列的相應位置
t=3----{2, 3, 4, 7, 5, 6, 1}? ...
t=4----{2, 3, 4, 5, 7, 6, 1}? ...
t=5----{2, 3, 4, 5, 6, 7, 1}? ...
t=6----{1, 2, 3, 4, 5, 6, 7}? 將第t個元素按其大小插到前面排好序的數列的相應位置
C++實現如下:
#include<iostream>using namespace std;void StraightInsertionSort(int arr[], int n){int tmp = 0,prev = 0; // Previous Elementfor(int t=1; t<n; t++) // t for times{tmp = arr[t]; // 取出當前元素prev = t - 1; // 前一個元素// 當前元素小于前一個且沒越界,執行替換while( (prev >= 0) && (tmp < arr[prev]) ){arr[prev + 1] = arr[prev]; // 把前一個元素賦值給當前prev--; // 再向前移動一個位置}arr[prev+1] = tmp;}}// 在主函數中測試下...void main(){int arr1[] = {7, 4, 3, 2, 5, 6, 1};StraightInsertionSort(arr1, 7);for(int i=0; i<7; i++)cout<< arr1[i] << " ";cout<<endl;}
?
在網上有段很不錯的插入排序舞蹈,可以看看:
)
)
