网页设计作业保护动物_模板网线_电脑优化是什么意思_十大基本营销方式

直接插入排序中寻找插入位置的操作可以通过折半查找来实现。据此写一个改进的插入排序的算法。

#include<iostream>
using namespace std;
void StraightSort (int r[ ], int n)
{
    int i,j,low,high,mid,flag,k;
    for(i=2; i<n; i++)
    {
        r[0]=r[i];        low=1;        high=i-1;        flag=1;
        while (low<=high && flag)
        {
            mid=(low+high)/2;
            if(r[0]<r[mid]) high=mid-1;
            else if(r[0] >r[mid]) low=mid+1;
            else flag=0;
        }
        if(flag==1)k=low;else k=mid+1;

//用flag区分找到和没找到两种情况；k=low也可以写成k=high+1;
        for (j=i-1; j>=k; j--)
            r[j+1]=r[j];
        r[k]=r[0];
    }
}

int main()
{
    int d[10]= {0,2,5,3,8,7,6,9,4,1};
    StraightSort(d, 10);
    for (int j=1; j<10; j++)
        cout<<d[j]<<"   ";
    cout<<endl;
    return 0;
}