剑指 Offer 40. 最小的k个数
剑指 Offer 40. 最小的k个数
剑指 Offer 40. 最小的k个数
链接
思路
一、库函数
二、冒泡排序
三、折半插入排序
四、插入排序
五、选择排序
六、选择排序变形
代码
一、库函数
二、冒泡排序
三、折半插入排序
四、插入排序
五、选择排序
六、选择排序变形
链接
剑指 Offer 40. 最小的k个数
排序相关算法
思路
一、库函数
直接调用 Java util 包里的Arrays中的排序方法，将数组进行排序，并输出前k个数
二、冒泡排序
用冒泡排序对数组进行排序，输出前k个数（是真的慢）
三、折半插入排序
用折半插入排序对数组进行排序，输出前k个数
四、插入排序
用直接插入排序对数组进行排序，输出前k个数
五、选择排序
用选择排序对数组进行排序，输出前k个数
六、选择排序变形
在选择排序的基础上进行双向选择，提升排序效率
代码
一、库函数
class Solution {
public int[] getLeastNumbers(int[] arr, int k)
{
Arrays.sort(arr);
int[] ret = new int[k];
System.arraycopy(arr, 0, ret, 0, k);
return ret;
}
}
1
2
3
4
5
6
7
8
9
二、冒泡排序
class Solution {
public int[] getLeastNumbers(int[] arr, int k)
{
bubbleSort(arr);
int[] ret = new int[k];
System.arraycopy(arr, 0, ret, 0, k);
return ret;
}
private void bubbleSort(int[] arr)
{
boolean flag = true; //如果没有进行交换，则说明数组已经有序
//冒泡次数
for (int i = 0; i < arr.length - 1; i++)
{
for (int j = 0; j < arr.length - 1; j++)
{
if (arr[j] > arr[j + 1])
{
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
flag = false;
}
}
if (flag)
{
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
三、折半插入排序
class Solution {
public int[] getLeastNumbers(int[] arr, int k)
{
//排序
//Arrays.sort(arr);
//bubbleSort(arr);
bsInsertSort(arr);
int[] ret = new int[k];
System.arraycopy(arr, 0, ret, 0, k);
return ret;
}
private void bsInsertSort(int[] arr)
{
for (int i = 1; i < arr.length; i++)
{
int v = arr[i];
int left = 0, right = i;
while (left < right)
{
int m = (left + right) / 2;
if (v >= arr[m])
{
left = m + 1;
} else
{
right = m;
}
}
for (int j = i; j > left; j--)
{
arr[j] = arr[j - 1];
}
arr[left] = v;
}
}
}
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
35
36
37
38
39
四、插入排序
class Solution {
public int[] getLeastNumbers(int[] arr, int k)
{
//排序
//Arrays.sort(arr);
//bubbleSort(arr);
//bsInsertSort(arr);
insertSort(arr);
int[] ret = new int[k];
System.arraycopy(arr, 0, ret, 0, k);
return ret;
}
private void insertSort(int[] arr)
{
for (int i = 0; i < arr.length - 1; i++)
{
int temp = arr[i + 1];
int j;
for (j = i; j >= 0; j--)
{
if (temp < arr[j])
{
arr[j + 1] = arr[j];
} else
{
break;
}
}
arr[j + 1] = temp;
}
}
}
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
五、选择排序
class Solution {
public int[] getLeastNumbers(int[] arr, int k)
{
//排序
//Arrays.sort(arr);
//bubbleSort(arr);
//bsInsertSort(arr);
//insertSort(arr);
selectSort(arr);
int[] ret = new int[k];
System.arraycopy(arr, 0, ret, 0, k);
return ret;
}
private void selectSort(int[] arr)
{
for (int i = arr.length - 1; i >= 0; i--)
{
int max = arr[0];
int index = 0;
for (int j = 0; j <= i; j++) //找最大数
{
if (max < arr[j])
{
max = arr[j];
index = j;
}
}
arr[index] = arr[i]; //交换
arr[i] = max;
}
}
}
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
35
36
六、选择排序变形
class Solution {
public int[] getLeastNumbers(int[] arr, int k)
{
//排序
//Arrays.sort(arr);
//bubbleSort(arr);
//bsInsertSort(arr);
//insertSort(arr);
//selectSort(arr);
selectSortDeformation(arr);
int[] ret = new int[k];
System.arraycopy(arr, 0, ret, 0, k);
return ret;
}
private void selectSortDeformation(int[] arr)
{
for (int i = arr.length - 1, k = 0; i >= 0 && k < arr.length && k < i; i--, k++)
{
int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;
int index = 0;
for (int j = k; j <= i; j++)
{
if (max < arr[j])
{
max = arr[j];
index = j;
}
}
arr[index] = arr[i]; //交换
arr[i] = max;
for (int j = k; j <= i - 1; j++)
{
if (min > arr[j])
{
min = arr[j];
index = j;
}
}
arr[index] = arr[k];
arr[k] = min;
}
}
}
————————————————
版权声明：本文为CSDN博主「枳洛淮南✘」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/weixin_43520256/article/details/115917383