插入排序

原理

将要排序的元素分为有序和无序两个部分，选择无序部分的第一个元素与有序部分中的元素进行逐个比较，插入对应位置选择剩余无序部分的第一个元素，重复上一个步骤，直至无序部分的元素个数为0 // 交换两个数字 #define SWAP(a, b) \ { \ a = a ^ b; \ b = a ^ b; \ a = a ^ b; \ } // 直接插入排序 void insertSort(int *arr, int size) { int i, j; for (i = 1; i < size; ++i) { for (j = i; j > 0; --j) { if (*(arr + j) < *(arr + j - 1)) { SWAP(*(arr + j), *(arr + j - 1)); } } } } void moveElement(int *arr, int left, int right) { while (--right > left) { SWAP(*(arr + right), *(arr + right + 1)); } } // 折半插入排序 // 原理与插入排序类似，不过在插入环节，先使用二分法找到具体插入位置之后，在对元素进行整体偏移 void halfInsertSort(int *arr, int size) { int i, left, right, middle, j, tmp; for (i = 1; i < size; ++i) { left = 0; right = i; tmp = *(arr + i); while (left < right) { middle = (left + right) >> 1; if (tmp < *(arr + middle)) { if (tmp >= *(arr + middle - 1)) { moveElement(arr, middle, i); *(arr + middle) = tmp; break; } right = middle - 1; } else { if (tmp <= *(arr + middle + 1)) { moveElement(arr, middle + 1, i); *(arr + middle + 1) = tmp; break; } left = middle + 1; } } if (left == right) { if (tmp < *(arr + left)) { moveElement(arr, left, i); *(arr + left) = tmp; } } } }