// // Created by tangs on 2018/11/16. // #include using namespace std; // 书上的折半插入排序, 与直接插入排序的区别,就是在查找插入位置时,使用了 // 二分法,除此之外思想也是一样的。 void InsertSort(int A[], int n) { int i, j, low, high, mid; for (i = 2; i < n; i++) { A[0] = A[i]; low = 1; high = i - 1; while (low <= high) { mid = (low + high) / 2; if (A[mid] > A[0]) { high = mid - 1; } else { low = mid + 1; } } for (j = i - 1; j >= high + 1; --j) { A[j + 1] = A[j]; } A[high + 1] = A[0]; } } // 自己实现 void InsertSortBySelf(int A[], int n) { int i, j, low, high, mid = 0, temp; for (i = 1; i < n; i++) { if (A[i] > A[i - 1]) { continue; } temp = A[i]; low = 0, high = i - 1; while (low <= high) { mid = (low + high) / 2; if (A[mid] > temp) { high = mid - 1; } else { low = mid + 1; } } for (j = i - 1; j >= mid; --j) { A[j + 1] = A[j]; } A[j + 1] = temp; } } int main() { int A1[] = {6, 1, 5, 2, 1, 9, 10, 24, 7, 0}; InsertSort(A1, 10); // print: // 0 0 1 1 2 5 7 9 10 24 for (int i = 0; i < 10; i++) { cout << A1[i] << " "; } cout << endl; int A2[] = {6, 1, 5, 2, 1, 9, 10, 24, 7, 0}; InsertSortBySelf(A2, 10); // print: // 0 0 1 1 2 5 7 9 10 24 for (int i = 0; i < 10; i++) { cout << A1[i] << " "; } cout << endl; return 0; }