java插入排序算法伪代码
时间: 2023-10-26 09:21:56 浏览: 110
以下是Java插入排序算法的伪代码:
```
for i = 1 to n-1
key = array[i]
j = i - 1
while j >= 0 and array[j] > key
array[j+1] = array[j]
j = j - 1
end while
array[j+1] = key
end for
```
其中,`n`表示待排序数组的长度,`array`表示待排序的数组。该算法的时间复杂度为O(n^2)。
相关问题
java代码设待排表中有9个元素,其关键字序列为{8,9,10,4,5,6,20,1,2},使用折半插入排序法进行排序,写出排序算法
折半插入排序(也称为二分查找插入排序)是一种改进版的插入排序算法,它通过每次将元素定位到已排序部分的合适位置,而不是从头开始搜索。对于给定的关键字序列 {8, 9, 10, 4, 5, 6, 20, 1, 2},我们可以按照以下步骤进行排序:
1. 假设第一个元素8已经就绪,后续元素作为未排序的。
2. 对于每个未排序的元素:
- 找到该元素应该插入的位置,通过二分查找找到目标值的正确位置。比如查找4时,先找到中间值(通常是序列长度的一半)5,因为4小于5,所以应在4和5之间继续查找。
- 如果中间值大于等于要插入的元素,则向左半部分递归查找;如果中间值小于要插入的元素,则向右半部分递归查找,直到找到合适的插入位置。
- 将找到的插入位置后的元素依次向右移动一位,腾出空间插入当前元素。
3. 当所有元素都插入就绪后,列表即为排序完成。
以下是折半插入排序的伪代码描述:
```java
void halfInsertionSort(int[] arr, int size) {
for (int i = 1; i < size; i++) {
int key = arr[i]; // 待排序的元素
int low = 0;
int high = i - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (arr[mid] >= key) {
high = mid - 1;
} else {
low = mid + 1;
}
}
// 将key插入到正确的位置
for (int j = i; j > low; j--) {
arr[j] = arr[j - 1];
}
arr[low] = key;
}
}
```
阅读全文
相关推荐














