新的家园

插入排序原理：_插入排序的工作方式像许多人排序一手扑克牌.开始时,我们的左手为空并且桌子上的牌面向下.然后,我们每次从桌子上拿走一张牌并将它插入左手中正确的位置.为了找到一张牌的正确位置,我们从右向左将它与已在手中的每张牌进行比较,拿在左手中的牌总是排序好的. _ INSERTION-SORT 伪代码：

for j = 1 to A.length
    key = A\[j\]
    //Insert A\[j\] into the sorted sequence A\[1...j-1\]
    i = j - 1
    while i > 0 and A\[i\] > key
        A\[i+1\] = A\[i\]
        i = i-1
    A\[i+1\] = key

代码实现：

void insertion_sort(int array[],int length, bool asc);

int main()
{
int array[10] = { 2,3,1,5,6,8,10,9,4 };
int length = sizeof(array) / sizeof(array[0]);

insertion_sort(array, length,true);
insertion_sort(array, length, false);

system("pause");
//return 0;

}

void insertion_sort(int array[],int length,bool asc)
{
for (int j = 1; j<length; j++) {
int key = array[j];
int i = j - 1;
if(asc)
{
while (i >= 0 && array[i] > key) {
array[i + 1] = array[i];
i = i - 1;
}
}
else
{
while (i >= 0 && array[i] < key) {
array[i + 1] = array[i];
i = i - 1;
}
}

    array\[i + 1\] = key;
}

for (int i = 0; i<length; i++) {
    cout << array\[i\] << endl;
}

}

插入排序的时间复杂度为 o(n^2)。 参考：算法导论（原书第3版）

---

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 xue_huashan@163.com