折半插入排序
时间: 2023-07-02 20:10:13 浏览: 60
折半插入排序是插入排序的一种变体,它通过减少比较次数来提高排序效率。具体步骤如下:
1.将第一个元素看做已排好序的序列。
2.从第二个元素开始,将其插入到已排好序的序列中,找到插入位置时使用折半查找的方式来确定插入位置。
3.重复步骤2,直到所有元素都被插入到已排序序列中。
代码如下:
```python
def binary_insertion_sort(arr):
for i in range(1, len(arr)):
# 用折半查找确定插入位置
left, right = 0, i - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] > arr[i]:
right = mid - 1
else:
left = mid + 1
# 将arr[i]插入到已排序序列中
for j in range(i - 1, left - 1, -1):
arr[j + 1], arr[j] = arr[j], arr[j + 1]
return arr
```
在最坏情况下,折半插入排序的时间复杂度为 O(n²),但在平均情况下,它的时间复杂度为 O(nlogn)。
相关问题
折半插入排序 c语言
折半插入排序是一种插入排序算法,它通过减少比较次数来提高排序效率。下面是C语言的折半插入排序代码:
```c
#include <stdio.h>
void binaryInsertionSort(int arr[], int n) {
int i, j, left, right, mid, key;
for (i = 1; i < n; ++i) {
key = arr[i];
left = 0;
right = i - 1;
while (left <= right) {
mid = (left + right) / 2;
if (arr[mid] > key) {
right = mid - 1;
} else {
left = mid + 1;
}
}
for (j = i - 1; j >= left; --j) {
arr[j + 1] = arr[j];
}
arr[left] = key;
}
}
int main() {
int n;
scanf("%d", &n);
int arr[n];
int i;
for (i = 0; i < n; ++i) {
scanf("%d", &arr[i]);
}
binaryInsertionSort(arr, n);
for (i = 0; i < n; ++i) {
printf("%d ", arr[i]);
}
return 0;
}
```
折半插入排序实验
好的,折半插入排序是一种优化的插入排序算法。它的基本思想是将待排序的序列分成两个部分:有序部分和无序部分。初始时,有序部分只包含一个元素,无序部分包含除该元素外的所有元素。接着,每次从无序部分取出第一个元素,使用二分查找算法找到该元素在有序部分应该插入的位置,然后将该元素插入到有序部分的相应位置,直到无序部分中的所有元素都被插入到有序部分中。以下是 Python 代码实现折半插入排序算法的过程:
```python
def binary_insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
left, right = 0, i - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] > key:
right = mid - 1
else:
left = mid + 1
for j in range(i-1, left-1, -1):
arr[j+1] = arr[j]
arr[left] = key
return arr
```
我们可以使用以下代码来测试折半插入排序算法的效率:
```python
import random
import time
arr = [random.randint(0, 1000) for i in range(10000)]
start_time = time.time()
sorted_arr = binary_insertion_sort(arr)
end_time = time.time()
print(f"Time taken to sort the array: {end_time - start_time:.6f} seconds")
```
这样就可以得到折半插入排序算法的执行时间了。