插入法（直接/二分/希尔）

news/2024/5/20 10:50:35

//稳定耗时： 双向冒泡，可指定最大最小值个数MaxMinNum<n=sizeof(Arr)/sizeof(Arr[0]),
void BiBubbleSort(int Arr[],int n，int MaxMinNum){int left=0,right=n-1;int i;bool notDone= true;int temp;int  minPos;while(left<right&&notDone  ){        notDone= false;for(i=left;i<right;i++){if(Arr[i]>Arr[i+1]){//swap(Arr[i],Arr[i+1]);temp=Arr[i];Arr[i]=Arr[i+1];Arr[i+1]=temp;notDone= true;//}// if(Arr[i]<Arr[left])//minPos=i; //最小值//	{//		  temp=Arr[left];//		  Arr[left]=Arr[minPos];// 		  Arr[minPos]=temp;//	}}right--;//右边界增加一个最大值for(i=right-1;i>=left;i--){if(Arr[i]>Arr[i+1]){//swap(Arr[i],Arr[i+1]);temp=Arr[i];Arr[i]=Arr[i+1];Arr[i+1]=temp;notDone= true;}}left++;//左边界增加一个最小值if(MaxMinNum>0){MaxMinNum--;if(MaxMinNum==0)return;}}
}

直接插入

void InsertSort(int* arr, int n)
{for (int i = 0; i < n - 1; ++i){int end = i;//记录有序序列最后一个元素的下标int tem = arr[end + 1];//待插入的元素//单趟排while (end >= 0){//比插入的数大就向后移if (tem < arr[end]){arr[end + 1] = arr[end];end--;}//比插入的数小，跳出循环else{break;}}//tem放到比插入的数小的数的后面arr[end  + 1] = tem;//代码执行到此位置有两种情况://1.待插入元素找到应插入位置（break跳出循环到此）//2.待插入元素比当前有序序列中的所有元素都小（while循环结束后到此）}
}

二分插入法直接插入上改进(n<1024),明显减少数据比较次数，快速定位,n过大不如直接插入快；

a[] 有序：type为 0 时排序从小到大，为 1 时排序从大到小,n=sizeof(a)/sizeof(a[0]);
void InsertSort_binary(int a[],int n)//,int type)
{for ( int i = 1; i < n; i++){int temp=a[i];  //临时待插入值int left=0;  //左侧边界值int right=i-1;  //右侧边界值while (left <= right){// int mid = (left+right) / 2;  //中间值 可能溢出INT_MAX；int mid = left + ( right - left) / 2;if(a[mid] > temp)//if(type == 0 ? (a[mid] > temp) : (a[mid] < temp)){right = mid - 1;   //把右侧边界缩小，在中间值得左边进行寻找}else {left = mid + 1;  //把左侧边界加大，在中间值得右边进行寻找}            }for ( int j = i-1; j >= left; j--)  //将left到i-1之间的数都往后移动一个位置//如果j<left 或j=0,将不会有数进行位置的移动{a[j+1] = a[j];}a[left] = temp;      //将要插入的数值插入到合适位置       }    
}

希尔非稳定排序，最高效接近快排；

void ShellSort(int* arr, int size)
{int gap = size;while (gap > 1){gap = gap / 3 + 1;	//调整希尔增量int i = 0;for (i = 0; i < size - gap; i++)	//从0遍历到size-gap-1{int end = i;int temp = arr[end + gap];while (end >= 0){if (arr[end] > temp){arr[end + gap] = arr[end];end -= gap;}else{break;}}arr[end + gap] = temp;	//以 end+gap 作为插入位置}}
}

n=10000 时间对比