- ubuntu12.04环境下使用kvm ioctl接口实现最简单的虚拟机
- Ubuntu 通过无线网络安装Ubuntu Server启动系统后连接无线网络的方法
- 在Ubuntu上搭建网桥的方法
- ubuntu 虚拟机上网方式及相关配置详解
CFSDN坚持开源创造价值,我们致力于搭建一个资源共享平台,让每一个IT人在这里找到属于你的精彩世界.
这篇CFSDN的博客文章优化常见的java排序算法由作者收集整理,如果你对这篇文章有兴趣,记得点赞哟.
冒泡排序的思想:
每次让当前的元素和它的下一个元素比较大小、如果前一个的元素大于后一个元素的话,交换两个元素.
这样的话经历一次扫描之后能确保数组的最后一个元素一定是数组中最大的元素.
那么下次扫描的长度比上次少一个、因为数组的最后一个元素已经是最大的了、即最后一个元素已经有序了.
优化一: 优化的思路就是每一次扫描遍历一次数组、如果某次的扫描之后没有发生数组元素的交换的话、那么说明数组的元素已经是有序的了,就可以直接跳出循环、没有继续扫描的必要了.
优化二:如果数组的尾部已经局部有序的话、那么在经历一次扫描之后的话、就不需要在对尾部局部有序的部分进行扫描了。具体的做法就是记录上一次交换的位置,然后让下一次的扫描到上一次的记录的位置就好了、因为记录的位置后的元素已经有序了.
1
2
3
4
5
6
7
8
9
10
11
12
|
//常规的写法
public
static
void
bubbleSort1(
int
[] array) {
for
(
int
i =
0
; i < array.length; i++) {
for
(
int
j =
0
; j < array.length - i -
1
; j++) {
if
(array[j] > array[j +
1
]) {
int
tmp = array[j];
array[j] = array[j +
1
];
array[j +
1
] = tmp;
}
}
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
//优化一
public
static
void
bubbleSort2(
int
[] array) {
boolean
flag =
true
;
for
(
int
i =
0
; i < array.length; i++) {
for
(
int
j =
0
; j < array.length - i -
1
; j++) {
if
(array[j] > array[j +
1
]) {
int
tmp = array[j];
array[j] = array[j +
1
];
array[j +
1
] = tmp;
flag =
false
;
}
}
if
(flag)
break
;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
//优化二
public
static
void
bubbleSort3(
int
[] array) {
int
end = array.length-
1
;
for
(
int
i = end; i >
0
; i--) {
int
lastIndex =
1
;
for
(
int
j =
0
; j < end; j++) {
if
(array[j] > array[j +
1
]) {
int
tmp = array[j];
array[j] = array[j +
1
];
array[j +
1
] = tmp;
lastIndex = j +
1
;
}
}
end = lastIndex;
}
}
|
选择排序的思想也是类似与冒泡排序的思想。再一次扫描之后找打数组当中最大的元素、将最大的元素放在数组的末尾。第二次的扫描数组的时候比上次扫描的长度减一 。
当然也可以换种思路来实现选择排序—每次扫描数组、然后找出最小的元素、将最小的元素放在数组的首位、下次扫描的时候不在扫描数组的首位、将第二小的元素放在数组第二个位置即可.
1
2
3
4
5
6
7
8
9
10
11
12
13
|
public
static
void
selectSort1(
int
[] array) {
for
(
int
end = array.length -
1
; end >
0
; end--) {
int
maxIndex =
0
;
for
(
int
start =
0
; start <= end; start++) {
if
(array[maxIndex] < array[start]) {
maxIndex = start;
}
}
int
tmp = array[end];
array[end] = array[maxIndex];
array[maxIndex] = tmp;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
public
static
void
selectSort2(
int
[] array) {
for
(
int
start =
0
; start < array.length; start++) {
int
minIndex = start;
for
(
int
end = start; end < array.length; end++) {
if
(array[end] < array[minIndex]) {
minIndex = end;
}
}
int
tmp = array[minIndex];
array[minIndex] = array[start];
array[start] = tmp;
}
}
|
堆排可以看作是对选择排序的一种优化、将数组原地建成大堆、将最大的元素放在数组的最后一个位置、adjust使数组继续保持大根堆、下一次的交换是和数组的倒数第二个元素进行交换。思路和前面两种排序的算法的思路一致、也是找最值、和数组的首或尾交换、下次交换的时候忽略已经交换的元素.
当然也可以建立一个小堆。堆顶已经是最小的了,那么只需要比较堆顶的左孩子和右孩子的大小即可,左孩子大于右孩子的话、交换、让右孩子adjust保持小堆(因为交换后的右孩子可能不满足小堆)即可.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
public
static
void
heapSort1(
int
[] array) {
//建大堆
for
(
int
p = (array.length -
1
-
1
) /
2
; p >=
0
; p--) {
adjustDown(array, p, array.length);
}
//交换
int
end = array.length -
1
;
while
(end >
0
) {
int
tmp = array[
0
];
array[
0
] = array[end];
array[end] = tmp;
adjustDown(array,
0
, end);
end--;
}
}
public
static
void
adjustDown(
int
[] array,
int
p,
int
len) {
int
child = p *
2
+
1
;
while
(child < len) {
if
(child +
1
< len && array[child] < array[child +
1
]) {
child++;
}
if
(array[child] > array[p]) {
int
tmp = array[child];
array[child] = array[p];
array[p] = tmp;
p = child;
child = p *
2
+
1
;
}
else
{
break
;
}
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
|
public
static
void
adjustDown1(
int
[] array,
int
p,
int
len) {
int
child = p *
2
+
1
;
while
(child < len) {
if
(child +
1
< len && array[child] > array[child +
1
]) {
child++;
}
if
(array[child] < array[p]) {
int
tmp = array[child];
array[child] = array[p];
array[p] = tmp;
p = child;
child = p *
2
+
1
;
}
else
{
break
;
}
}
}
public
static
void
heapSort2(
int
[] array) {
//建小堆
for
(
int
p = (array.length -
1
-
1
) /
2
; p >=
0
; p--) {
adjustDown1(array, p, array.length);
}
//交换
int
startIndex =
1
;
while
(startIndex +
1
< array.length) {
if
(array[startIndex] > array[startIndex +
1
]) {
int
tmp = array[startIndex];
array[startIndex] = array[startIndex +
1
];
array[startIndex +
1
] = tmp;
adjustDown1(array,startIndex+
1
,array.length);
}
startIndex++;
}
}
|
插入排序的思想就是类似于打牌的时候,左手拿的排就是有序的、右手拿牌然后将牌与前面的牌进行比较、然后插入到合适位置.
优化一:
优化一的思路就是将比较变为移动,每次拿到元素的时候就要和前面的元素进行比较、数组的逆序对比较多的话、那么每次都要比较和交换、所以我们可以先记录下当前的元素的值、将该元素前面大于该元素的数字都后移一位、然后插入、这样的话比较的和交换的次数就减少了.
优化二
要在前面的有序的元素中找到当前元素要插入的位置、那么是不是可以使用二分查找来实现呢?所以我们可以使用二分查找来继续优化一下.
1
2
3
4
5
6
7
8
9
10
11
|
public
static
void
insertSort1(
int
[] array) {
for
(
int
start =
1
; start < array.length; start++) {
int
cur = start;
while
(cur >
0
&& array[cur] < array[cur -
1
]) {
int
tmp = array[cur];
array[cur] = array[cur -
1
];
array[cur -
1
] = tmp;
cur--;
}
}
}
|
1
2
3
4
5
6
7
8
9
10
11
|
public
static
void
insertSort2(
int
[] array){
for
(
int
start =
1
; start < array.length; start++) {
int
cur = start;
int
tmp = array[start];
while
(cur>
0
&& tmp < array[cur-
1
]){
array[cur] = array[cur-
1
];
cur--;
}
array[cur] = tmp;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
public
static
void
insertSort3(
int
[] array) {
for
(
int
start =
1
; start < array.length; start++) {
int
cur = array[start];
int
insertIndex = searchIndex(array, start);
for
(
int
i = start; i > insertIndex; i--) {
array[i] = array[i -
1
];
}
array[insertIndex] = cur;
}
}
public
static
int
searchIndex(
int
[] array,
int
index) {
int
start =
0
;
int
end = index;
while
(start < end) {
int
mid = (start + end) >>
1
;
if
(array[index] < array[mid]) {
end = mid;
}
else
{
start = mid +
1
;
}
}
return
start;
}
|
归并排序的思想就是—不断的将当前的序列平均分为2个子序列、直到子序列中的元素的个数为1的时候、然后不断地将2个子序列合并成一个有序的序列.
优化
可以看到每次归并的时候、申请的额外的数组的大小为左子序列的长度+右子序列的长度(end - start + 1)、归并之后将额外的数组的值赋值到原数组的对应的位置上.
那么我们可以做出优化、可以直接在原数组上进行操作、每次将左子序列的值拷贝出来、和右子序列的值比较、直接覆盖原来的值即可。这样每次申请的额外空间就比原来申请的空间减少一倍.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
|
public
static
void
mergerSortRec(
int
[] array) {
mergerRec(array,
0
, array.length -
1
);
}
public
static
void
mergerRec(
int
[] array,
int
start,
int
end) {
if
(start >= end)
return
;
int
mid = (start + end) >>
1
;
mergerRec(array, start, mid);
mergerRec(array, mid +
1
, end);
merger(array, start, mid, end);
}
private
static
void
merger(
int
[] array,
int
start,
int
mid,
int
end) {
int
[] tmpArray =
new
int
[end - start +
1
];
int
tmpArrayIndex =
0
;
int
leftStart = start;
int
leftEnd = mid;
int
rightStart = mid +
1
;
int
rightEnd = end;
while
(leftStart <= leftEnd && rightStart <= rightEnd) {
if
(array[leftStart] < array[rightStart]) {
tmpArray[tmpArrayIndex++] = array[leftStart++];
}
else
{
tmpArray[tmpArrayIndex++] = array[rightStart++];
}
}
while
(leftStart <= leftEnd) {
tmpArray[tmpArrayIndex++] = array[leftStart++];
}
while
(rightStart <= rightEnd) {
tmpArray[tmpArrayIndex++] = array[rightStart++];
}
for
(
int
i =
0
; i < tmpArray.length; i++) {
array[start + i] = tmpArray[i];
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
public
static
void
mergerSort(
int
[] array,
int
start,
int
end) {
if
(end - start <
2
)
return
;
int
mid = (start + end) >>
1
;
mergerSort(array, start, mid);
mergerSort(array, mid, end);
merger(array, start, mid, end);
}
private
static
void
merger(
int
[] array,
int
start,
int
mid,
int
end) {
int
[] tmpLeftArray =
new
int
[(end - start +
1
) >>
1
];
int
ls =
0
;
int
le = mid - start;
int
rs = mid;
int
re = end;
int
arrIndex = start;
for
(
int
i = ls; i < le; i++) {
tmpLeftArray[i] = array[start + i];
}
while
(ls < le) {
if
(rs < re && array[rs] < tmpLeftArray[ls]) {
array[arrIndex++] = array[rs++];
}
else
{
array[arrIndex++] = tmpLeftArray[ls++];
}
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
public
class
ThreadSortDemo {
public
static
void
main(String[] args) {
int
[] array = {
2
,
23
,
45
,
5
,
100
,
0
,
9
};
for
(
int
i =
0
; i < array.length; i++) {
new
ThreadSort(array[i]).start();
}
}
}
class
ThreadSort
extends
Thread {
private
int
val;
ThreadSort(
int
val) {
this
.val = val;
}
@Override
public
void
run() {
try
{
Thread.sleep(val);
System.out.print(val +
" "
);
}
catch
(InterruptedException e) {
e.printStackTrace();
}
}
}
|
计数排序:核心思想就是统计每个整数在序列中出现的次数、进而推导出每个整数在有序序列中的索引。具体的做法就是先找出序列中最大的元素、开辟出最大元素+1的数组空间、统计每个元素出现的次数counts[array[i]]++、然后遍历coutns数组、找出不为0的元素、输出对应的下标即可、也可以将下标重新放回到array数组中,也就是相当于array数组已经排好序了.
基数排序: 将所有元素统一为同样的数位长度, 数位较短的数前面补零。然后, 从最低位开始, 依次进行一次排序,这样从最低位排序一直到最高位排序完成以后, 原数组就变成一个有序序列.
桶排序:创建一定数量的桶、可以使用数组或者链表作为桶、按照一定的规则、将序列中的元素均匀的分配到对应的桶中、然后对每个桶中的元素进行单独的排序、最后将所有非空的桶的元素合并成有序序列.
本篇文章就到这里了,希望对你有帮助,也希望您能够多多关注我的更多内容! 。
原文链接:https://blog.csdn.net/qq_45859087/article/details/118298409 。
最后此篇关于优化常见的java排序算法的文章就讲到这里了,如果你想了解更多关于优化常见的java排序算法的内容请搜索CFSDN的文章或继续浏览相关文章,希望大家以后支持我的博客! 。
我正在尝试对每个条目有多个值的关联数组进行排序。 例如 [0] => stdClass Object ( [type] => node [sid] => 158 [score] => 0.059600
我在 mysql 中有“日期”列以这种格式保存日期 2014 年 9 月 17 日(日-月-年) 我需要对它们进行升序排序,所以我使用了这个命令: SELECT * FROM table ORDER
我目前正在将 MySQL 存储过程重写为 MS SQL 存储过程,但遇到了问题。 在 MySQL 存储过程中,有一个游标,它根据最近的日期 (effdate) 选择一个值并将其放入变量 (thestt
我想要 gwt r.QuestionId- 排序。但是我得到未排序的 QuestionId 尽管我提到了 QuestionId ASC 的顺序。 SELECT r.QuestionId,
我有一个关于在 scandir 函数中排序的基本问题。到目前为止,我阅读了 POSIX readdir 的手册页,但没有找到有关订购保证的具体信息。 但是当我遍历大目录(无法更改,只读)时,我在多个系
基本上我必须从 SQL 数据库中构建项目列表,但是用户可以选择对 7 个过滤器的任意组合进行过滤,也可以选择要排序的列以及按方向排序。 正如您可以想象的那样,这会以大量不同的组合进行编码,并且数据集非
我有两张 table 。想象第一个是一个目录,包含很多文件(第二个表)。 第二个表(文件)包含修改日期。 现在,我想选择所有目录并按修改日期 ASC 对它们进行排序(因此,最新的修改最上面)。我不想显
我想先根据用户的状态然后根据用户名来排序我的 sql 请求。该状态由 user_type 列设置: 1=活跃,2=不活跃,3=创始人。 我会使用此请求来执行此操作,但它不起作用,因为我想在“活跃”成员
在 C++ 中,我必须实现一个“类似 Excel/Access”(引用)的查询生成器,以允许对数据集进行自定义排序。如果您在 Excel 中使用查询构建器或 SQL 中的“ORDER BY a, b,
我面临这样的挑战: 检索按字段 A 排序的文档 如果字段 B 存在/不为空 . 否则 按字段排序 C. 在 SQL 世界中,我会做两个查询并创建一个 UNION SELECT,但我不知道如何从 Mon
我想对源列表执行以下操作: map 列表 排序 折叠 排序 展开 列表 其中一些方法(例如map和toList)是可链接的,因为它们返回非空对象。但是,sort 方法返回 void,因为它对 List
我制作了一个用于分析 Windows 日志消息编号的脚本。 uniq -c 数字的输出很难预测,因为根据数字的大小会有不同的空白。此时,我手动删除了空白。 这是对消息进行排序和计数的命令: cat n
我有以下词典: mydict1 = {1: 11, 2: 4, 5: 1, 6: 1} mydict2 = {1: 1, 5: 1} 对于它们中的每一个,我想首先按值(降序)排序,然后按键(升序)排序
我刚刚开始使用泛型,目前在对多个字段进行排序时遇到问题。 案例: 我有一个 PeopleList 作为 TObjectList我希望能够通过一次选择一个排序字段,但尽可能保留以前的排序来制作类似 Ex
有没有办法在 sql 中组合 ORDER BY 和 IS NULL 以便我可以在列不为空时按列排序,但如果它为null,按另一列排序? 最佳答案 类似于: ORDER BY CASE WHEN
我有一个包含 2 列“id”和“name”的表。 id 是常规的自动增量索引,name 只是 varchar。 id name 1 john 2 mary 3 pop 4 mary 5 j
场景 网站页面有一个带有分页、过滤、排序功能的表格 View 。 表中的数据是从REST API服务器获取的,数据包含数百万条记录。 数据库 REST API 服务器 Web 服务器 浏览器 问
假设我有一本字典,其中的键(单词)和值(分数)如下: GOD 8 DONG 16 DOG 8 XI 21 我想创建一个字典键(单词)的 NSArray,首先按分数排序,然后按字
如何在 sphinx 上通过 sql 命令选择前 20 行按标题 WEIGHT 排序,接下来 20 行按标题 ASC 排序(总共 40 个结果),但不要给出重复的标题输出。 我尝试了这个 sql 命令
我有一个奇怪的问题,当从 SQLite 数据库中选择信息并根据日期排序时,返回的结果无效。 我的SQL语句是这样的: Select pk from usersDates order by dateti
我是一名优秀的程序员,十分优秀!