C++、C#、java算法学习日记04----二分插入排序
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了C++、C#、java算法学习日记04----二分插入排序,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含3194字,纯文字阅读大概需要5分钟。
内容图文
经过上几篇对排序算法的了解,我们发现,所谓的排序也就是确定一个数组中每个元素的位置,然后对号入座,其过程也就是找到该元素的位置。确定位置,使用二分法可以达到很高的效率,我们将他应用到插入排序中就算是对上篇中排序的一种优化,能提高效率。
基本思想:
与上篇中的插入排序类似分已排序和未排序部分,然后将未排序 部分元素逐个插入,但是插入的过程不同,需要每次求一个 中间位置,和中间位置元素比较大小,然后根据大小情况,将高位 左移或者将低位右移,再求中间元素比较,直到找到合适位置 (也就是说使用二分法确定插入位置)后 将其部分元素后移为待插入元素腾出空间,再插入该序列即可。
C++实例:
#include<iostream> using namespace std; void HalfSort(int *array,int Length) {//定义最低,最高,中间值,待插入数据,插入位置 int low,high,middle,temp,index,i,j; for(i=1;i<Length;i++) //控制插入的元素,第一次从下标为1的元素开始 { //,将前面array[0]的当成已经排好序的数列,然后逐个插入 low=0; high=i-1; temp=array[i]; index=i; if(array[0]<temp&&array[i-1]>temp) //与头尾相比较如果没在范围类省略循环 { while(low<=high) //二分法查找插入位置 { middle=(low+high)/2; if(array[middle]>temp) { high=middle-1; } else low=middle+1; } //最后确定位置index index=low; } if(array[0]>=temp) //如果比第一个元素还小就直接插到第一个位置 { index=0;} if(array[i-1]<=temp) //如果比最后一个元素还大直接插到最后一个位置 { index=i;} //向后移位腾出插入空间 for(j=i-1;j>=index;j--) { array[j+1]=array[j];} array[index]=temp; //插入 } //输出 for(i=0;i<Length;i++) { cout<<array[i] <<" "; } cout<<endl; } void main() { int array[]={63,4,24,1,3,15}; int Length=sizeof(array)/sizeof(array[0]);//计算长度 HalfSort(array,Length); }
C#实例:
using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace HalfSort2 { class Sort { public void halfSort(int[] array) { int low,high,middle,temp,index,i; for (i = 1; i < array.Length; i++) { low = 0; high = i - 1; temp = array[i]; index = i; if (array[0] < temp && array[i - 1] > temp) { while (low <= high) //二分法查找插入位置 { middle = (low + high) / 2; if (array[middle] > temp) { high = middle - 1; } else low = middle + 1; } index = low; } if (array[0] >= temp) //如果比第一个元素还小就直接插到第一个位置 { index = 0; } if (array[i - 1] <= temp) //如果比最后一个元素还大直接插到最后一个位置 { index = i; } //向后移位腾出插入空间 for (int j = i - 1; j >= index; j--) { array[j + 1] = array[j]; } array[index] = temp; //插入 } foreach (int j in array) { Console.Write(j + " "); } Console.WriteLine(); } static void Main(string[] args) { int[] array = new int[] {63,4,24,1,3,15}; Sort sorter = new Sort(); sorter.halfSort(array); } } }
以上结果为:
java实例:
package Sort; public class Sort { public void halfsort(int[] array){ int low,high,middle,temp,index,i; for(i=1;i<array.length;i++){ low = 0; high = i - 1; temp = array[i]; index = i; if(array[0]<temp&&array[i-1]>temp){ while(low<=high){ middle=(low+high)/2; if(array[middle]>temp){ high=middle-1; } else{ low=middle+1; } } index=low; } if(array[0]>=temp){ index=0; } if(array[i-1]<=temp){ index=i; } for(int j =i-1;j>=index;j--){ array[j+1]=array[j]; } array[index]=temp; } for(int j:array){ System.out.print(j+" "); } } public static void main(String[] args) { int[] array = new int[]{63,4,24,1,3,15}; Sort sorter = new Sort(); sorter.halfsort(array); } }
结果:
其实关于二分法排序,我查阅资料的时候代码中并没有 if(array[0]<temp&&array[i-1]>temp) ,if(array[0]>=temp),if(array[i-1]<=temp) 这样的判断语句,这是我自己加上的,因为如果没有这些判断语句的话,当让你排序的数列已经是有序数列的时候程序还是会经历一些不必要的循环,反倒不如上一篇中的直接插入排序了。
以上代码中有什么需要改进的欢迎留言^_^
版权声明:本文为博主原创文章,未经博主允许不得转载。
原文:http://blog.csdn.net/hc666/article/details/49514385
内容总结
以上是互联网集市为您收集整理的C++、C#、java算法学习日记04----二分插入排序全部内容,希望文章能够帮你解决C++、C#、java算法学习日记04----二分插入排序所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。