从后往前比较，把后面的元素作为哨兵
#include<iostream> using namespace std; #include<vector> void InsertSort(vector<int> &q) { for(int i = 1 ; i < q.size(); i++) { int t = q[i]; int j; for(j = i - 1 ; j >=0 ; j--) { if(q[j] > t) { q[j+1] = q[j]; } else { break; } } q[j+1] = t; } } void DirectInsertSort(int a[],int n) { for(int i = 1 ; i < n ; i++) { int t = a[i]; int j; for(j = i - 1 ; j >= 0 ; j--) { if(a[j] > t) { a[j+1] = a[j]; } else { break; } } a[j+1] = t; } } void InsertSort2(int a[],int n) //baike's solution { int j; for(int i = 1 ; i < n ; i++) { if(a[i] < a[i-1]) { int temp = a[i]; for(j = i - 1; j >= 0 && a[j] > temp ; j--) { a[j+1] = a[j]; } a[j+1] = temp; } } } void InsertSort_lts(vector<int> &q) { for(int i = 1 ; i < q.size(); i++) { int t = q[i]; int j; for(j = i - 1 ; j >=0 ; j--) { if(q[j] < t) { q[j+1] = q[j]; } else { break; } } q[j+1] = t; } } void DirectInsertSort_lts(int a[],int n) { for(int i = 1 ; i < n ; i++) { int t = a[i]; int j; for(j = i - 1 ; j >= 0 ; j--) { if(a[j] < t) { a[j+1] = a[j]; } else { break; } } a[j+1] = t; } } void InsertSort2_lts(int a[],int n) { int j; for(int i = 1 ; i < n ; i++) { if(a[i] > a[i-1]) { int temp = a[i]; for(j = i - 1; j >= 0 && a[j] < temp ; j--) { a[j+1] = a[j]; } a[j+1] = temp; } } } int main() { int *arr = new int[10]{49,38,65,97,76,13,27,49}; int n = sizeof(arr); //int arr[] = {49,38,65,97,76,13,27,49}; //int n = sizeof(arr) / sizeof(arr[0]); vector<int> a; for(int i = 0 ; i < n ; i++) { a.push_back(arr[i]); } InsertSort(a); for(auto i : a) { cout<<i<<" "; } cout<<endl; cout<<n<<endl; DirectInsertSort(arr,n); for(int i = 0 ; i < n ; i++) { cout<<arr[i]<<" "; } cout<<endl; int b[] = {8,6,4,9,7,1,2,5,0}; int len = sizeof(b) / sizeof(b[0]); cout<<len<<endl; InsertSort2(b,len); for(int i = 0 ; i < len ; i++) { cout<<b[i]<<" "; } cout<<endl; InsertSort_lts(a); for(auto i : a) { cout<<i<<" "; } cout<<endl; DirectInsertSort_lts(arr,n); for(int i = 0 ; i < n ; i++) { cout<<arr[i]<<" "; } cout<<endl; InsertSort2_lts(b,len); for(int i = 0 ; i < len ; i++) { cout<<b[i]<<" "; } cout<<endl; system("pause"); return 0; }