java数组插入元素并快捷排序的方法
作者:WarmHope
时间:2023-04-28
浏览:2
1、从数组的第二个元素进行操作,如果发现其前面的元素比他大,就将其前面的元素往后挪,直到cur指向的元素大于或者等于他前一个元素,此时cur指向的位置就是待插入元素应该插入的位置。staticint[]insertSort2(int[]array){intlen=array.length;for(intbegin=1;begin0&&array[cur]1;if(array[index]
本文目录
1、从数组的第二个元素进行操作,如果发现其前面的元素比他大,就将其前面的元素往后挪,直到cur指向的元素大于或者等于他前一个元素,此时cur指向的位置就是待插入元素应该插入的位置。
static int[] insertSort2(int[] array){
int len = array.length;
for (int begin = 1; begin < len; begin++){
int cur = begin;
int tmp = array[cur];
while (cur > 0 && array[cur] < array[cur-1]){
array[cur] = array[cur-1];
cur--;
}
array[cur] = tmp;
}
return array;
}2、通过二分查找减少了比较次数,即cmp函数的调用,还减少了swap函数的调用。更快的找到了当前元素应该插入的位置,然后再进行挪动,提高了效率。
static int[] insertSort3(int[] array){
int len = array.length;
for (int begin = 1; begin < len; begin++){
int v = array[begin];
int insertIndex = search(array,begin);
// 将 [insertIndex, begin) 范围内的元素往右边挪动一个单位
for (int i = begin; i > insertIndex; i--){
array[i] = array[i-1];
}
array[insertIndex] = v;
}
return array;
}
static int search(int[] array, int index){
int begin = 0;
int end = index;
while(begin < end){
int mid = (begin+end) >> 1;
if (array[index] < array[mid]){
end = mid;
}else{
begin = mid+1;
}
}
return begin;
}
作者最新文章
漫蛙漫画官网首页登录入口
2026-10-28 19:02
mindmanager怎么使用 思维导图入门
2026-10-27 09:54
Word2016怎么移除文档空白页
2026-10-16 22:30
endnote怎么引用中文参考文献格式设置教程
2026-10-14 17:25
sql条件判断字符串不包含某个字符串的方法详解
2026-10-13 17:39
下一篇:
使用Java连接Redis的方法
热门文章
更多
精品专题
更多
Mac软件
更多
WINDOWS
更多

































