折半插入排序算法与直接插入排序算法的区别是什么?
时间: 2023-12-02 12:43:03 浏览: 67
折半插入排序算法与直接插入排序算法的区别如下:
1. 直接插入排序算法是将待排序的元素插入到已排序的序列中,而折半插入排序算法是利用二分查找的思想,找到待排序元素在已排序序列中的位置,再插入到该位置。
2. 直接插入排序算法的时间复杂度为O(n^2),而折半插入排序算法的时间复杂度为O(nlogn)。
3. 直接插入排序算法是稳定的,而折半插入排序算法不是稳定的。
以下是Java实现折半插入排序算法的示例代码:
```java
public static void binaryInsertSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
int left = 0;
int right = i - 1;
int temp = arr[i];
while (left <= right) {
int mid = (left + right) / 2;
if (arr[mid] > temp) {
right = mid - 1;
} else {
left = mid + 1;
}
}
for (int j = i - 1; j >= left; j--) {
arr[j + 1] = arr[j];
}
arr[left] = temp;
}
}
```
以下是Java实现直接插入排序算法的示例代码:
```java
public static void insertSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
int temp = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > temp) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = temp;
}
}
```