首页二分法插入 void BiInsertion(int a[],int n,int type)如何实现

二分法插入 void BiInsertion(int a[],int n,int type)如何实现

时间: 2023-12-23 18:06:32 浏览: 72

二分法插入（Binary Insertion Sort）是一种排序算法，它是插入排序的改进版，通过二分查找的方式找到插入位置，减少了比较次数，提高了排序效率。以下是实现二分法插入的代码： ```c++ void BiInsertion(int a[], int n, int type){ for(int i = 1; i < n; i++){ int left = 0, right = i - 1; int tmp = a[i]; while(left <= right){ int mid = (left + right) / 2; if(a[mid] > tmp){ right = mid - 1; } else{ left = mid + 1; } } for(int j = i - 1; j >= left; j--){ a[j + 1] = a[j]; } a[left] = tmp; } if(type == 1){ for(int i = 0; i < n; i++){ cout << a[i] << " "; } cout << endl; } } ``` 参数说明： - a[]：待排序的数组 - n：数组的长度 - type：排序方式，1表示升序，0表示降序代码实现过程： - 从第二个元素开始遍历数组，将其视为要插入的元素； - 在已排序的数组中使用二分查找法找到要插入的位置； - 将要插入位置后面的元素全部后移一位； - 将要插入的元素插入到空出的位置。最后，根据 type 的值，输出升序或降序排列的数组。注意事项： - 二分查找法要保证数组是有序的； - 在将要插入位置后面的元素全部后移一位时，要从后往前遍历数组，否则会覆盖掉未移动的元素； - 要确保数组下标不越界。

阅读全文