- 插入排序思想：每次將一個(gè)待排序的記錄拯辙，按照值的大小插入到已排序好的數(shù)組中的適當(dāng)位置，知道全部記錄插入完畢
- 插入排序是穩(wěn)定的妒茬，時(shí)間復(fù)雜度為O(n2)
#import <iostream>
using namespace std;
void insertSort(int nums[], int n) {
int i, j;
for (i = 1; i < n; i++) { //nums[0]自成一個(gè)序列轰豆，從nums[1]開始插入
if (nums[i] < nums[i - 1]) { //nums[i]符合插入條件
int temp = nums[i];
for (j = i - 1; j >= 0 && nums[j] > temp; j--) {
nums[j + 1] = nums[j];
}
nums[j + 1] = temp;
}
}
}
int main() {
int n;
cin>>n;
int nums[n];
for (int i = 0; i < n; i++) { //輸入未排序的數(shù)
cin>>nums[i];
}
insertSort(nums, n);
for (int i = 0; i < n; i++) { //輸出排序完畢的序列
cout<<nums[i]<<" ";
}
cout<<endl;
return 0;
}
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
