首页 > 排序
头像
著名美食品鉴师
编辑于 2020-07-16 14:26
+ 关注

排序

作者：冠状病毒biss
链接：https://www.nowcoder.com/discuss/361165
来源：牛客网

本来想最近出一个全网最好的MySQL基础和高级总结 无奈昨天学校说我天天搞java不能毕业 最近可能不能学啥东西了
毕设是虚拟现实那块的 今天查论文也有用到mysql交互数据库 应该还是可以学学..尽量过年的时候发出来吧
排序也不太会 瞎总结的 像我这种新手可以学学

总体比较

在这里插入图片描述

排序接口

1
2
3
4
5
6
publicinterfaceSort {
voidsort(int[] arr);
voidbetterSort(int[] arr);
}

测试类

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
40
41
42
43
44
45
46 
publicint[] createArray(){
//定义数组长度
int[] arr=newint[10];
//随机赋值
Random random =newRandom();
intmax=100;
for(inti=0;i<arr.length;i++)
arr[i]=random.nextInt(max);
returnarr;
}

//测试
publicvoidtestSort(String className)throwsException {
int[] arr =createArray();
Class<Sort> aClass = (Class<Sort>) Class.forName(className);
Sort sortObject = aClass.newInstance();
System.out.println(className);
System.out.println("排序前");
System.out.println(Arrays.toString(arr));
System.out.println("排序后");
sortObject.sort(arr);
System.out.println(Arrays.toString(arr));

arr=createArray();
System.out.println("排序前");
System.out.println(Arrays.toString(arr));
System.out.println("优化排序后");
sortObject.sort(arr);
System.out.println(Arrays.toString(arr));

//排序10000000次比较两种排序算法的性能
longt1 = System.currentTimeMillis();
for(inti=0;i<10000000;i++){
arr=newint[]{50,31,93,68,37,70,15,10,21,39};
sortObject.sort(arr);
}
longt2 = System.currentTimeMillis();
System.out.println("优化前的排序1000万次花费时间："+(t2-t1)+"ms");
longt3 = System.currentTimeMillis();
for(inti=0;i<10000000;i++){
arr=newint[]{50,31,93,68,37,70,15,10,21,39};
sortObject.betterSort(arr);
}
longt4 = System.currentTimeMillis();
System.out.println("优化后的排序1000万次花费时间："+(t4-t3)+"ms");
}

稳定的排序

1 插入排序——直接插入排序

直接插入排序

  • 原理：
    假设前n-1个数是已经排好序的，将第n个数插入前面已经排好序的数列中，重复此过程直到插入完所有数。
  • 时间复杂度 O(n²)
  • 适用场景
    n较小时以及元素基本有序时，可用来做其他排序的优化
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//直接插入排序
publicvoidsort(int[] arr){
//从第二个数开始插入
for(intindex=1;index<arr.length;index++){
//保存目前的数
inttemp=arr[index];
//寻找要插入的位置,从当前数的前一个开始，直到数列开头
inti;
for(i=index-1;i>=0&&arr[i]>temp;i--){
//每当目前遍历到的数比temp大，就让它往后挪一个，腾出位置
arr[i+1]=arr[i];
}
arr[i+1]=temp;
}
}

优化的直接插入排序：折半插入

  • 原理：
    直接插入并没有利用到要插入的数列已经有序的特点，可以通过二分查找找到要插入的位置i，将i+1到目前遍历到的索引index的之间的元素全部后移后插入。
  • 时间复杂度 O(nlogn)
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
//优化的插入排序：折半插入
publicvoidbetterSort(int[] arr){
//从第二个数开始插入
for(intindex=1;index<arr.length;index++){
//保存目前的数
inttemp=arr[index];
//寻找要插入的位置
intinsertIndex = -1;
intstart=0;
intend=index-1;
while(start<=end){
//中间索引
intmid=start+(end-start)/2;
//如果比temp小，从中间往后面部分找
if(arr[mid]<temp)
start=mid+1;
//如果比temp大，从中间往前面部分找
elseif(arr[mid]>temp)
end=mid-1;
else
//出现相同元素时保证排序稳定性
insertIndex= mid+1;
break;
}
if(insertIndex==-1)
insertIndex=start;
//将插入位置开始直到目前有序数列长度的数全部后移一个腾出位置
for(inti=index;i>insertIndex;i--)
arr[i]=arr[i-1];
arr[insertIndex]=temp;
}
}

测试及性能比较

结果：可以看到优化后的插入排序性能更好

sort.InsertSort
排序前
[11, 43, 90, 65, 79, 36, 47, 37, 67, 77]
排序后
[11, 36, 37, 43, 47, 65, 67, 77, 79, 90]
排序前
[32, 1, 5, 60, 20, 67, 94, 22, 51, 21]
优化排序后
[1, 5, 20, 21, 22, 32, 51, 60, 67, 94]
优化前的排序1000万次花费时间：405ms
优化后的排序1000万次花费时间：355ms

2 交换排序——冒泡排序

冒泡排序

  • 原理：
    比较相邻的元素，如果第一个比第二个大，就交换他们两个。
    对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。
    针对所有的元素重复以上的步骤，除了最后一个，直到没有任何一对数字需要比较。
  • 时间复杂度 O(n²)
  • 适用场景
    元素基本有序时
1
2
3
4
5
6
7
8
9
10
11
12
13
14
publicvoidsort(int[] arr) {
//对于n个元素的数组需要执行n-1次
for(inti=0;i<arr.length-1;i++){
//由于最后一个就是最大元素，所以不需要比较到最后一个
for(intindex=0;index<arr.length-1-i;index++){
//如果比后面的元素大则交换
if(arr[index]>arr[index+1]){
inttemp=arr[index];
arr[index]=arr[index+1];
arr[index+1]=temp;
}
}
}
}

优化后的冒泡排序

  • 原理：
    例如结束排序前元素序列为1，2，3，4，5，6，7，8，此时数列已经有序，但仍会进行不必要的比较，因此可以设置一个标志位falg，记录是否有元素交换，如果没有直接结束比较。
    例如要对1，4，7，3，8，9，10，11这种前一半无序后一半有序的数列进行排序，为了减少不必要的比较，可以再加上一个临时变量记录最后一次元素交换的位置，作为下次比较的最大边界。
  • 时间复杂度 O(n²)
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
publicvoidbetterSort(int[] arr) {
//记录数列是否有序
booleanflag=true;
//记录最后一次交换的数组下标
intlastIndex =-1;
//记录数组无序边界,初始为末尾
intbound=arr.length-1;
//对于n个元素的数组需要执行n-1次
for(inti=0;i<arr.length-1;i++){
for(intindex=0;index<bound;index++){
//如果比后面的元素大则交换
if(arr[index]>arr[index+1]){
inttemp=arr[index];
arr[index]=arr[index+1];
arr[index+1]=temp;
lastIndex=index;
flag=false;//有元素交换，说明数列无序
}
}
//更新边界值
bound=lastIndex;
//如果数列已有序，结束排序
if(flag)
break;;
}
}

测试及性能比较

结果：

sort.BubbleSort
排序前
[12, 59, 38, 95, 31, 88, 48, 12, 4, 51]
排序后
[4, 12, 12, 31, 38, 48, 51, 59, 88, 95]
排序前
[57, 85, 32, 43, 65, 58, 65, 67, 97, 79]
优化排序后
[32, 43, 57, 58, 65, 65, 67, 79, 85, 97]
优化前的排序1000万次花费时间：492ms
优化后的排序1000万次花费时间：462ms

3 归并排序

Arrays.sort是利用归并排序实现的

归并排序

  • 原理
    将数组分成两半，对每部分递归应用归并排序，在两部分都排好序后，对其进行合并。

  • 时间复杂度 O(nlogn)

  • 适用场景
    数据量大，并且对稳定性有要求的情况

    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
    40
    41
    42
    43
    44
    //辅助数组 长度和原数组相同
    privateint[] help;
    publicvoidsort(int[] arr) {
    help=newint[arr.length];
    sort(arr,0,arr.length-1);
    }
    //排序
    privatevoidsort(int[] arr,intstart,intend){
    if(start==end)
    return;
    //防止溢出
    intmid=start+(end-start)/2;
    //对前一半排序
    sort(arr,start,mid);
    //对后一半排序
    sort(arr,mid+1,end);
    //合并
    merge(arr,start,mid,end);
    }
    //
    privatevoidmerge(int[] arr,intstart,intmid,intend){
    //将待排序序列arr[low...high]拷贝到辅助数组的相同位置
    for(inti=start;i<=end;i++){
    help[i]=arr[i];
    }
    intp=start;//用于遍历前半部分数列的索引
    intq=mid+1;//用于遍历后半部分数列的索引
    intindex=start;//遍历arr数组的索引
    while(p<=mid&&q<=end){
    //用较小的那一个更新数组
    if(help[p]<help[q])
    arr[index++]=help[p++];
    else
    arr[index++]=help[q++];
    }
    //如果还有剩余的则依次全部存入，以下两个while只会执行一个
    while(p<=mid)
    arr[index++]=help[p++];
    while(q<=end)
    arr[index++]=help[q++];
    }

优化的归并排序

  • 原理
    由于排序后的左右部分已有序，所以如果下标为mid的元素小于下标为mid+1的元素就不再需要合并。
    同时，当元素个数足够少的时候，我们可以使用直接插入排序。
  • 时间复杂度 O(nlogn)
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
publicvoidbetterSort(int[] arr) {
help=newint[arr.length];
betterSort(arr,0,arr.length-1);
}
//优化排序
privatevoidbetterSort(int[] arr,intstart,intend) {
//数列小于5时用插入排序优化
if(end-start<5){
InsSort(arr);
return;
}
//防止溢出
intmid=start+(end-start)/2;
//对前一半排序
betterSort(arr,start,mid);
//对后一半排序
betterSort(arr,mid+1,end);
//减少不必要的归并，由于前后均有序，若mid<mid+1,不必合并
if(arr[mid]>arr[mid+1])
merge(arr,start,mid,end);
}
publicvoidInsSort(int[] arr){
//从第二个数开始插入
for(intindex=1;index<arr.length;index++){
//保存目前的数
inttemp=arr[index];
//寻找要插入的位置,从当前数的前一个开始，直到数列开头
inti;
for(i=index-1;i>=0&&arr[i]>temp;i--){
//每当目前遍历到的数比temp大，就让它往后挪一个，腾出位置
arr[i+1]=arr[i];
}
arr[i+1]=temp;
}
}

测试及性能比较

结果：

sort.MergeSort
排序前
[78, 69, 13, 93, 47, 91, 30, 59, 33, 59]
排序后
[13, 30, 33, 47, 59, 59, 69, 78, 91, 93]
排序前
[85, 75, 57, 32, 79, 17, 63, 58, 77, 55]
优化排序后
[17, 32, 55, 57, 58, 63, 75, 77, 79, 85]
优化前的排序1000万次花费时间：1779ms
优化后的排序1000万次花费时间：628ms

不稳定的排序

1 插入排序——希尔排序

希尔排序

  • 原理
    先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录"基本有序"时，再对全体记录进行依次直接插入排序。
  • 时间复杂度 O(n^（1.3—2）)
  • 适用场景
    希尔排序是对直接插入排序的一种优化，可以用于大型的数组，希尔排序比插入排序和选择排序要快的多，并且数组越大，优势越大。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    //希尔排序
    publicvoidsort(int[] arr) {
    //初始增量为数组长度的1/2
    for(intgap=arr.length/2;gap>0;gap/=2){
    //循环直到增量gap为1时结束
    for(intindex=gap;index<arr.length;index++){
    //保存目前的数
    inttemp=arr[index];
    //寻找要插入的位置,从当前数的前gap个开始，直到数列开头
    inti;
    for(i=index-gap;i>=0&&temp<arr[i];i-=gap){
    //每当目前遍历到的数比temp大，就让它往后挪gap个，腾出位置
    arr[i+gap]=arr[i];
    }
    arr[i+gap]=temp;
    }
    }
    }
    由于希尔排序也是对直接插入排序的优化，所以两者的代码十分相似，和下面的直接插入排序比较，可以发现只是将间隔从1设置为了gap变量，并增加了一个控制gap变量的循环结构。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//直接插入排序
publicvoidsort(int[] arr){
//从第二个数开始插入
for(intindex=1;index<arr.length;index++){
//保存目前的数
inttemp=arr[index];
//寻找要插入的位置,从当前数的前一个开始，直到数列开头
inti;
for(i=index-1;i>=0&&arr[i]>temp;i--){
//每当目前遍历到的数比temp大，就让它往后挪一个，腾出位置
arr[i+1]=arr[i];
}
arr[i+1]=temp;
}
}

优化的希尔排序

  • 原理：
    使用以下的序列，使性能提高 20%-40% 。1、5、19、41、109、209、505、929、2161、3905、8929、16001、36289、64769、146305、260609（这是通过 9×4k-9×2k+1(k=1,2,3,4,5…) 和 4k-3×2k+1(k=2,3,4,5,6…) 综合得到的）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
publicvoidbetterSort(int[] arr) {
intlength = arr.length;
intgap =1;
while(gap < length /19) {
gap =19* gap +1; // 、5、19、41、109、209、505、929、2161、3905、8929、16001、36289、64769、146305、260609
}
while(gap>=1){
//循环直到增量gap为1时结束
for(intindex=gap;index<arr.length;index++){
//保存目前的数
inttemp=arr[index];
//寻找要插入的位置,从当前数的前gap个开始，直到数列开头
inti;
for(i=index-gap;i>=0&&temp<arr[i];i-=gap){
//每当目前遍历到的数比temp大，就让它往后挪gap个，腾出位置
arr[i+gap]=arr[i];
}
arr[i+gap]=temp;
}
gap/=3;
}
}

测试及性能比较

为了测试此处增加测试数据长度，其余测试时使用最开头的长度为10的数组。

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
40
41
42
@Test
publicvoidtest()throwsException {
testSort("sort.ShellSort");
}
//测试
publicvoidtestSort(String className)throwsException {
int[] arr =createArray();
Class<Sort> aClass = (Class<Sort>) Class.forName(className);
Sort sortObject = aClass.newInstance();
System.out.println(className);
System.out.println("排序前");
System.out.println(Arrays.toString(arr));
System.out.println("排序后");
sortObject.sort(arr);
System.out.println(Arrays.toString(arr));
arr=createArray();
System.out.println("排序前");
System.out.println(Arrays.toString(arr));
System.out.println("优化排序后");
sortObject.sort(arr);
System.out.println(Arrays.toString(arr));
//排序10000000次比较两种排序算法的性能
longt1 = System.currentTimeMillis();
for(inti=0;i<10000000;i++){
arr=newint[]{50,31,93,68,37,70,15,10,21,39,72,4,9,2,1,5,54,70,35,65,23,65,34,67,23,54,34,25,76,52,23,26,43
,4,55,2,42,65,4,24,56,74,35,745,35,36,75,73,56,45,24,75,45,7,87,24,26};
sortObject.sort(arr);
}
longt2 = System.currentTimeMillis();
System.out.println("优化前的排序1000万次花费时间："+(t2-t1)+"ms");
longt3 = System.currentTimeMillis();
for(inti=0;i<10000000;i++){
arr=newint[]{50,31,93,68,37,70,15,10,21,39,72,4,9,2,1,5,54,70,35,65,23,65,34,67,23,54,34,25,76,52,23,26,43
,4,55,2,42,65,4,24,56,74,35,745,35,36,75,73,56,45,24,75,45,7,87,24,26};
sortObject.betterSort(arr);
}
longt4 = System.currentTimeMillis();
System.out.println("优化后的排序1000万次花费时间："+(t4-t3)+"ms");
}

结果：

sort.ShellSort
排序前
[39, 31, 24, 58, 63, 83, 49, 68, 80, 55]
排序后
[24, 31, 39, 49, 55, 58, 63, 68, 80, 83]
排序前
[9, 41, 47, 70, 81, 24, 53, 43, 72, 57]
优化排序后
[9, 24, 41, 43, 47, 53, 57, 70, 72, 81]
优化前的排序1000万次花费时间：3815ms
优化后的排序1000万次花费时间：2997ms

2 选择排序——直接选择排序

直接选择排序

  • 原理：
    首先在未排序序列中找到最小元素，存放到排序序列的起始位置。
    再从剩余未排序元素中继续寻找最小元素，然后放到已排序序列的末尾。
    重复直到所有元素均排序完毕。
  • 时间复杂度 O(n²)
  • 适用场景
    数据量不大，并且对稳定性没有要求的情况
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
publicvoidsort(int[] arr) {
//存储最小元素下标
intminIndex;
for(intindex=0;index<arr.length-1;index++){
minIndex=index;
//寻找最小元素,用其下标更新minIndex
for(inti=index+1;i<arr.length;i++){
if(arr[i]<arr[minIndex])
minIndex=i;
}
//如果最小元素不是当前元素，交换两者位置
if(index!=minIndex){
inttemp=arr[minIndex];
arr[minIndex]=arr[index];
arr[index]=temp;
}
}
}

优化后的选择排序

  • 原理：
    同时在未排序数列中找到最小元素和最大元素，分别存放在数列头部和尾部。
    重复直到所有元素均排序完毕。
  • 时间复杂度 O(n²)
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
publicvoidbetterSort(int[] arr) {
//存储最小元素下标
intminIndex;
//存储最大元素下标
intmaxIndex;
intstart;
intend=arr.length-1;
for(start=0;start<end;start++,end--){
minIndex=start;
maxIndex=end;
//寻找最小元素,用其下标更新minIndex
//寻找最大元素,用其下标更新maxIndex
for(inti=start;i<=end;i++){
if(arr[i]<arr[minIndex])
minIndex=i;
if(arr[i]>arr[maxIndex])
maxIndex=i;
}
//如果最小元素不是当前起始元素，交换两者位置
if(start!=minIndex){
inttemp=arr[minIndex];
arr[minIndex]=arr[start];
arr[start]=temp;
}
//如果最大元素不是当前末尾元素，交换两者位置
if(end!=maxIndex){
inttemp=arr[maxIndex];
arr[maxIndex]=arr[end];
arr[end]=temp;
}
}
}

测试及性能比较

1
2
3
4
@Test
publicvoidtest()throwsException {
testSort("sort.SelectSort");
}

结果：由于同时找到了最小和最大元素，几乎节约一半时间

sort.SelectSort
排序前
[93, 93, 48, 71, 94, 15, 74, 56, 45, 5]
排序后
[5, 15, 45, 48, 56, 71, 74, 93, 93, 94]
排序前
[66, 26, 59, 5, 6, 78, 9, 93, 2, 2]
优化排序后
[2, 2, 5, 6, 9, 26, 59, 66, 78, 93]
优化前的排序1000万次花费时间：934ms
优化后的排序1000万次花费时间：640ms

3 选择排序——堆排序

堆排序

  • 原理
    堆排序是将数据看成是完全二叉树、根据完全二叉树的特性来进行排序的一种算法。
    最大堆要求节点的元素都要不小于其孩子，最小堆要求节点元素都不大于其左右孩子。
    那么处于最大堆的根节点的元素一定是这个堆中的最大值。
  • 时间复杂度 O(nlogn)
  • 适用场景 数据较多时
  • 给堆添加结点的思路
    将最后一个结点作为当前结点
    while(当前结点＞它的父结点){
    将当前结点和它的父结点交换
    现在当前结点往上面进了一个层次
    }
  • 给堆移除结点的思路
    移除根结点
    将最后一个结点作为根结点
    将根结点作为当前结点
    while(当前结点具有子结点且小于它的子结点){
    将当前结点和较大的子结点交换
    现在当前结点往下面进了一个层次
    }

用集合实现

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
privateArrayList<Integer> list=newArrayList<>();
//建堆
privatevoidadd(intnum){
list.add(num);
//获取当前索引
intcurIndex=list.size()-1;
while(curIndex>0){
//获取父索引
intparIndex=(curIndex-1)/2;//例如二叉树0，1，2 1和2的父索引都是0
//如果当前索引的数值比父索引的数值大则交换，否则由于按序插入可直接结束
if(list.get(parIndex)<list.get(curIndex)){
inttemp=list.get(parIndex);
list.set(parIndex,list.get(curIndex));
list.set(curIndex,temp);
}elsebreak;
curIndex=parIndex;//如果交换，让当前索引=父索引，继续判断
}
}
//移除堆中最大元素
privateintremove(){
//获取当前list中最大元素，由于是大根堆，所以是第一个
intrem=list.get(0);
//重建大根堆
list.set(0,list.get(list.size()-1));//让最后一个结点取代根结点
list.remove(list.size()-1);//移除最后一个结点
intcurIndex=0;//让根结点成为当前结点
while(curIndex<list.size()){
intleftIndex=curIndex*2+1;//左孩子结点索引
intrightIndex=curIndex*2+2;//右孩子结点索引
if(leftIndex>=list.size())break;//到达末尾
//寻找最大孩子结点索引
intmaxIndex=leftIndex;
if(rightIndex<list.size()){//如果右孩子结点存在
if(list.get(maxIndex)<list.get(rightIndex))
maxIndex=rightIndex;
}
//如果最大孩子结点值大于当前结点，则交换
inttemp=list.get(curIndex);
if(list.get(curIndex)<list.get(maxIndex)){
list.set(curIndex,list.get(maxIndex));
list.set(maxIndex,temp);
}
elsebreak;
curIndex=maxIndex;
}
//返回最大值
returnrem;
}
publicvoidsort(int[] arr) {
//依次添加元素，即建堆
for(intvalue : arr) add(value);
//依次移除最大元素并赋值排序
for(inti=arr.length-1;i>=0;i--)
arr[i]=remove();
}

优化的堆排序

  • 原理
    整体思路不变，用数组取代集合
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
40
41
42
43
44
45
46
47
48
49
50
51
publicvoidbetterSort(int[] arr) {
int[] nums=newint[arr.length];
inti=0;
intsize=arr.length;
for(intvalue : arr)
badd(nums,i++,value);
for(intindex=arr.length-1;index>=0;index--)
arr[index]=bremove(nums,size--);
}
privatevoidbadd(int[] nums,inti,intnum){
nums[i]=num;
intcurIndex=i;
while(curIndex>0){
intparIndex=(curIndex-1)/2;
if(nums[parIndex]<nums[curIndex]){
inttemp=nums[curIndex];
nums[curIndex]=nums[parIndex];
nums[parIndex]=temp;
}elsebreak;
curIndex=parIndex;
}
}
privateintbremove(int[] nums,intsize){
intrem=nums[0];
nums[0]=nums[size-1];
intcurIndex=0;
while(true){
intleftIndex=curIndex*2+1;
intrightIndex=curIndex*2+2;
if(leftIndex>=size)break;
intmaxIndex=leftIndex;
if(rightIndex<size){
if(nums[maxIndex]<nums[rightIndex])
maxIndex=rightIndex;
}
inttemp=nums[curIndex];
if(nums[curIndex]<nums[maxIndex]){
nums[curIndex]=nums[maxIndex];
nums[maxIndex]=temp;
}
else{
break;}
curIndex=maxIndex;
}
//返回最大值
returnrem;
}

测试及性能比较

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
40
@Test
publicvoidtest()throwsException {
testSort("sort.HeapSort");
}
//测试
publicvoidtestSort(String className)throwsException {
int[] arr=newint[]{3,5,1,19,11,22,88};
Class<Sort> aClass = (Class<Sort>) Class.forName(className);
Sort sortObject = aClass.newInstance();
System.out.println(className);
System.out.println("排序前");
System.out.println(Arrays.toString(arr));
System.out.println("排序后");
sortObject.sort(arr);
System.out.println(Arrays.toString(arr));
arr=newint[]{3,5,1,19,11,22,88};
System.out.println("排序前");
System.out.println(Arrays.toString(arr));
System.out.println("优化排序后");
sortObject.betterSort(arr);
System.out.println(Arrays.toString(arr));
//排序10000000次比较两种排序算法的性能
longt1 = System.currentTimeMillis();
for(inti=0;i<10000000;i++){
arr=newint[]{3,5,1,19,11,22,88};
sortObject.sort(arr);
}
longt2 = System.currentTimeMillis();
System.out.println("优化前的排序1000万次花费时间："+(t2-t1)+"ms");
longt3 = System.currentTimeMillis();
for(inti=0;i<10000000;i++){
arr=newint[]{3,5,1,19,11,22,88};
sortObject.betterSort(arr);
}
longt4 = System.currentTimeMillis();
System.out.println("优化后的排序1000万次花费时间："+(t4-t3)+"ms");
}

结果：

sort.HeapSort
排序前
[3, 5, 1, 19, 11, 22, 88]
排序后
[1, 3, 5, 11, 19, 22, 88]
排序前
[3, 5, 1, 19, 11, 22, 88]
优化排序后
[1, 3, 5, 11, 19, 22, 88]
优化前的排序1000万次花费时间：1449ms
优化后的排序1000万次花费时间：486ms

4 交换排序——快速排序

快速排序

  • 原理：
    对冒泡排序的优化。
    该算法在数组中选择一个基准（pivot）元素，将数组分为两部分，使得第一部分的元素都小于等于基准元素，第二部分的所有元素都大于基准元素，对第一部分和第二部分分别递归应用快速排序算法。
  • 时间复杂度 O(nlogn)
  • 适用场景
    数据量大的情况
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
40
41
42
publicvoidsort(int[] arr) {
quickSort(arr,0, arr.length-1);
}
publicvoidquickSort(int[] arr,intstart,intend){
//递归条件
if(start<end){
//排序并获得基准元素的下标
intpivotIndex=getPivotIndex(arr,start,end);
//分别对基准元素的前后部分排序
quickSort(arr,start,pivotIndex-1);
quickSort(arr,pivotIndex+1,end);
}
}
privateintgetPivotIndex(int[] arr,intstart,intend) {
//默认选择第一个作为基准
intpivot=arr[start];
inti=start;
intj=end;
while(i<j){//循环条件
//从左起找到第一个大于pivot的元素
while(i<=j&&arr[i]<=pivot)
i++;
//从右起找到第一个小于等于pivot的元素
while(i<=j&&arr[j]>pivot)
j--;
//如果左边元素大于右边则交换
if(i<j){
swap(arr,i,j);
}
}
swap(arr,start,j);
returnj;
}
publicstaticvoidswap(int[] arr,intx,inty){
inttemp;
temp  = arr[x];
arr[x] = arr[y];
arr[y] = 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
publicvoidbetterSort(int[] arr) {
bquickSort(arr,0, arr.length-1);
}
publicvoidbquickSort(int[] arr,intstart,intend){
//递归条件
if(end-start<5){
InsSort(arr);
}
//排序并获得基准元素的下标
intpivotIndex=getPivotIndex(arr,start,end);
//分别对基准元素的前后部分排序
quickSort(arr,start,pivotIndex-1);
quickSort(arr,pivotIndex+1,end);
}
publicvoidInsSort(int[] arr){
//从第二个数开始插入
for(intindex=1;index<arr.length;index++){
//保存目前的数
inttemp=arr[index];
//寻找要插入的位置,从当前数的前一个开始，直到数列开头
inti;
for(i=index-1;i>=0&&arr[i]>temp;i--){
//每当目前遍历到的数比temp大，就让它往后挪一个，腾出位置
arr[i+1]=arr[i];
}
arr[i+1]=temp;
}
}

测试及性能比较

sort.QuickSort
排序前
[0, 89, 27, 27, 66, 83, 21, 53, 74, 52]
排序后
[0, 21, 27, 27, 52, 53, 66, 74, 83, 89]
排序前
[81, 0, 83, 5, 86, 39, 7, 61, 43, 88]
优化排序后
[0, 5, 7, 39, 43, 61, 81, 83, 86, 88]
优化前的排序1000万次花费时间：621ms
优化后的排序1000万次花费时间：495ms

2024最新求职资料大礼包领取
真题
历年笔试真题附答案
4399游戏校招游戏开发岗
博世23年秋招软件工程师
深信服23届秋招测试开发A卷
全部 >
面经
面试常考问题整理
管理类双非硕的23秋招记录＆反思
2022考研失败春招选手的群面攻略（适用于菜鸡互啄型）
腾讯三面已上岸
全部 >
内推
员工内推码获取
【美团】校招社招内推，所有岗位，进度可查
【内推】蚂蚁集团-测试开发工程师/专家-杭州
科大讯飞2025年飞星计划校园招聘-岗位内推
全部 >
大家都在关注
校招日程表 笔试日历 ai模拟面试 面试宝典 剑指offer 知识点专项练习

全部评论

(0) 回帖
加载中...
话题 回帖
博文推荐

推荐话题

相关热帖

近期热帖

近期精华帖

热门推荐

牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”