排序算法之——插入排序

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了排序算法之——插入排序，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1044字，纯文字阅读大概需要2分钟。

内容图文

插入排序思想：将插入的元素记录，与前面的元素进行比较大小，查询到插入的位置，然后再将比它大的元素向后面移动，空出插入的位置，将元素插入。

剩下的和②步骤一样。。。

代码这里给出了3种，从基础到优化

//1
void InsertSort(int* a, int n)
{
    for (int i = 1; i < n; ++i)
    {
        if (a[i] < a[i - 1])
        {
            int temp = a[i];
            for (int j = 0; j < i; ++j)
            {
                if (temp < a[j])
                {
                    for (int k = i; k > j; k--)
                        a[k] = a[k - 1];
                    a[j] = temp;
                    break;
                }
            }
        }
    }
}

//2
void InsertSort(int* a, int n)
{
    int i, j;
    for ( i = 1; i < n; i++)
    {
        if (a[i] < a[i - 1])
        {
            int temp = a[i];
            for (j = i; j >= 0 && a[j-1] > temp; j--)
            {
                a[j] = a[j - 1];
            }
            a[j] = temp;
        }
    }
}

//3
void InsertSort(int* a, int n)
{
    int temp;
    for (int i = 1; i < n; i++)
    {
         int low = 0, high = i - 1;
         temp = a[i];
         while (low <= high)
         {
             int mid = (low + high) / 2;
             if (temp < a[mid])
                 high = mid - 1;
             else
                 low = mid + 1;
         }
         for (int j = i; j > low; --j)
         {
             a[j] = a[j - 1];
         }
         a[low] = temp;
    }
}

主方法：

int main()
{
    int arr[] = { 9,2,3,1,5,4,7,8,6 };
    int n = sizeof(arr) / sizeof(int);

    InsertSort(arr, n); //插入排序

    for (int i = 0; i < n; i++)
    {
        cout << arr[i] << " ";
    }
    cout << endl;
    return 0;
}

 

内容总结

以上是互联网集市为您收集整理的排序算法之——插入排序全部内容，希望文章能够帮你解决排序算法之——插入排序所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---