作者:潘PanPanPq | 来源:互联网 | 2023-10-16 16:22
1直接排序 直接排序需要注意的是如何实现,是通过一次输入一个数字与已经排好的队伍进行比较1intinsertsort(intr[],intn){2for(inti2;i
1 直接排序
直接排序需要注意的是如何实现,是通过一次输入一个数字与已经排好的队伍进行比较
1 int insertsort(int r[],int n){
2 for(int i=2;i<=n;i++){//从第2个元素开始插入
3 r[0]=r[i];//储存到观察哨
4 int j=i-1;//r[0]与已经排好序的元素比较
5 while(r[0]<r[j]){
6 r[j+1]=r[j];
7 j--;
8 }
9 r[j+1]=r[0];//如果比当前数字小则交换插入数字和当前位置,否则存储当前数字进入序列
10
11
12
13 }
14
15
16 }
2折半搜索
二分法的思想是,比较a[i]与a[mid]的大小,若a[i]>a[mid],说明a[i]的位置应该在mid~high之间,将区间[low,high]缩短为[mid+1,high],令指针low=mid+1;若a[i]<=a[mid],说明a[i]的位置应该在low~mid之间,将区间压缩为[low,mid-1],令指针high=mid-1。每次折半之后,a[i]的位置应该在[low,high]之间。
如此循环,low与high渐渐靠近,直到low>high跳出循环,a[i]的位置找到,low即为a[i]应该放置的位置。
找到a[i]的位置之后进行插入,先将a[low]~a[i-1]这些元素向后平移一个元素的位置,然后将a[i]放到low位置。
void Sort(int *a,int n) //对int数组进行从小到大的排序
{
for(int i=1;i//开始 以a[0]作为有序序列,从a[1]开始找到当前元素a[i]应该放置的位置
{
int low=0,high = i-1,mid;//每次寻找a[i]的位置,都要更新这些数据
while(low<=high) //二分思想循环寻找a[i]的位置
{
mid = (low+high) / 2;
if(a[i]<=a[mid])
high = mid - 1; //high指针减小
else
low = mid + 1; //low指针增加
} //循环结束,low就是a[i]应该放置的位置
int temp = a[i];
for(int j=i;j>low;j--) //将元素向后平移
a[j] = a[j-1];
a[low] = temp; //将元素temp = a[i] 放置到low位置
}
} 3 希尔排序