3.插入排序(小样本,基本有序时最快;稳定)
插入排序在工业和实际中应用比较多,当样本量小于60且基本有序时使用;
使用插入排序,可以保证排序数组的稳定性.经常在归并排序和快排中子数组规模小时使用.
普通插入排序:
//插入排序(相对冒泡和选择较好,但时间复杂仍为n**2,空间为1,稳定) //思想:同打牌,将新摸到的牌插入到已排好的牌面上 //操作:每次将后面的数插入到前面已排好的数组中 static void insertionSort(int[] a ){ //NK for(int j=1;j<a.length;j++) { //N for (int i = j; i > 0; i--) { //k if (a[i] < a[i - 1]) swap(a, i, i - 1); } }
折半插入(优化:运用二分查找思想找到插入位置)
static void halfInSort(int[] a ){ //定义边界和中间值 int left,mid,right; //定义一个中间变量存待插入的值 int temp; for(int j=1;j<a.length;j++) { //将各个值初始化 temp=a[j]; left=0; right=j-1; //用二分查找 找到需要插入的位置下标 while(left<=right) { //适当优化,当left,right过大时,不会超过int范围 mid=left+((right-left)>>1); //如果要插入值比a[mid]小,说明在mid左边, // 将上边界缩小为mid-1 if(temp<a[mid]){ right=mid-1; }else{ //否则就是temp比中间值大,在右边区域 //将下边界调大为mid+1 left=mid+1; } } //当跳出循环时,已找到将要插入的位置,即下标值为left的地方 //将插入位置的数依次向后移动,并将temp插入 for (int i = j; i > left; i--) { a[i]=a[i-1]; } a[left]=temp; }
pairInsert(优化:一次插入两个)
思想:减少了二分查找的次数
1.将待插入两个数比较大小,通过二分找到较小数应插入的位置;
2.将较小数插入;
3.再从较小数位置到最后找到较大数应插入位置,插入较大数.
拓展:二分查找(有序数组查找)
因为插入排序的优化中,使用了二分的思想,所以可以顺便撸出二分查找代码.
前提:数组已排序,查找数字在数组中的位置,不存在返回-1
static int halfSearch(int[] a,int num){ //left为左边界,right为右边界,mid为中间值,index为查找数在数组的位置 //初始化 int left=0; int right=a.length-1; int index=-1; int mid=-1; //核心比较代码 while (left<=right){ mid=left+((right-left)>>1); //等于则赋值返回 if(a[mid]==num){ index = mid; break; }else if (a[mid]<num){//大于a[mid],在右边区域 left=mid+1;//左边界移动 }else{//小于a[mid],在左边区域 right=mid-1;//右边界移动 } } //返回index return index; }