排序算法

前言

为了准备面试,前阵子将排序算法认认真真得刷了一遍,通过看书看视频,实践打代码,还有一部分的leetcode题,自己感觉也有点进步,现在做个小记录。

冒泡排序

  • 该排序就是一种像泡泡浮到水面以后,将其挑选,这种浮出来的前提是就是或者是小的/大的先露头,将/小的大的检索出来。(根据从大到小或者反过来)
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
package src.datastructure;

import java.util.Arrays;

/**
* @Author: yhy
* @Time: 23:49
*/
//时间复杂度O(n^2)
public class DubbleSort {
public static void main(String[] args) {
int[] abc = {1,9,-2,40,33};
int temp = 0;
boolean flag = false;
//第一轮for,n个数都要参与比较。
for (int i = 0; i <abc.length-1 ; i++) {
//第1个和其他的数进行比较。。再到第二个数与其他的
for (int j = 0; j < abc.length-1 ; j++) {
//这里是升序排序
if (abc[j] > abc[j+1]) {
flag = true;
temp = abc[j];
abc[j] = abc[j+1];
abc[j+1] = temp;
}

}
//这里优化了一些,减少了比较的次数,若排好序了,就直接跳出循环,输出结果
if (!flag) {
break;
}else {
flag = false;
}

}
System.out.println(Arrays.toString(abc));

}


}

选择排序

  • 先找个值假设作为最小值,进行该值以后的数与该值比较,小的就放在前面
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
package src.datastructure;

import java.util.Arrays;

/**
* @Author: yhy
* @Time: 15:30
* 选择排序
*/
public class SelectSort {
public static void main(String[] args) {
int[] abc = {1,9,-2,40,33};
// 选择排序:选择一开始为最小的,然后每一次开始排序
// 也有最小值还有最小值的索引
for (int i = 0; i < abc.length; i++) {
int min = abc[i];
int minIndex = i;
for (int j = i+1; j < abc.length; j++) {
if (min > abc[j]) {
min = abc[j];
minIndex = j;
abc[j] = abc[i];
}
// 关键判断;要将原来的索引与min比较,若发生了交换,就将相对小的数放在前面去
if (minIndex != i) {
abc[i] = min;

}
}

}
System.out.println(Arrays.toString(abc));

}


}

插入排序

插入意思就是从无序区找值插到有序区去,所以取第一个值为有序区,等到有序区长度为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
33
34
35
36
37
38
39
package src.datastructure;

import java.util.Arrays;

/**
* @Author: yhy
* @Time: 15:30
*/
public class InsertSort {
public static void main(String[] args) {
int[] abc = {1,9,-2,40,33};
// 插入排序,分为有序区,和无序区
// 和选择排序有那么一点相似,
// 这里是将一部分定义为有,然后比较再选择插入的位置等
for (int i = 1; i < abc.length ; i++) {
int insertIndex = i -1;
int insertValue = abc[i];
// 这里的数组下标是可以等于0
while (insertIndex >= 0 && insertValue < abc[insertIndex]){
// 将大的值往后移,直到找到合适的插入位置
abc[insertIndex+1] = abc[insertIndex];
insertIndex--;
}
// 退出循环后,就说明插入的位置找到了 加入判断,如果没有进去while的话,就不用赋值,插入位置不变
if (insertIndex + 1 != i) {
abc[insertIndex+1] = insertValue;

}


}
System.out.println(Arrays.toString(abc));


}



}

快速排序

  • 一种双指针移动的排序,找个基准值
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
package src.datastructure;

import java.util.Arrays;

/**
* @Author: yhy
* @Time: 12:05
* 采用指针交换来做
*/
public class QuickSort2 {
public static void quickSort(int[] arr, int startIndex, int endIndex) {
// 递归结束:startIndex 大于等于endIndex的时候
if (startIndex >= endIndex) {
return;

}
// 得到基准元素位置
int pivotIndex = partition(arr, startIndex, endIndex);
// 使用分治法递归数列的两部分
quickSort(arr, startIndex, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, endIndex);
}

public static int partition(int[] arr, int startIndex, int endIndex) {
// 这里的交换次数更少了
int pivot = arr[startIndex];
int left = startIndex;
int right = endIndex;
// 退出循环的时候,说明已经检索到中间位置了
while (left != right){
// 分别去找到左边和右边停止的指针
while (left < right && arr[right] > pivot){
right--;
}
while (left < right && arr[left] <= pivot){
left++;
}
// 然后进行交换
if (left < right) {
int p = arr[left];
arr[left] = arr[right];
arr[right] = p;
}
}
// 一轮交换已经结束
// pivot和指针重合点交换
// 将基准值放到所对应的位置
int p = arr[left];
arr[left] = arr[startIndex];
arr[startIndex] = p;
return left;

}
public static void main(String[] args) {
int[] arr = new int[]{4,2,3,6,15,7,1,9};
quickSort(arr,0,arr.length-1);
System.out.println(Arrays.toString(arr));
}

}

希尔排序

  • 希尔排序就是分组排序,将取一个间隔gap作为每次分的组数。
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
package src.datastructure;

import java.util.Arrays;

/**
* @Author: yhy
* @Time: 15:30
* 希尔排序
*/
public class ShellSort {
public static void main(String[] args) {
int[] abc = {1,9,-2,40,33};
// 希尔排序,要进行分组排序,同时依据是gap长度除2,每一次进行交换
// 用到了插入排序和冒泡排序的感觉
// 这是分组
for (int gap = abc.length/2; gap > 0; gap /= 2) {
// 这个for循环写法要注意
for (int i = gap; i < abc.length; i++) {
int j = i;
int temp = abc[j];
if (abc[j] < abc[j-gap]) {
while (j - gap >= 0 && temp < abc[j-gap]){
abc[j] = abc[j-gap];
j -= gap;
}
//将相对小索引的值变为一开始的
abc[j] = temp;
}

}

}
System.out.println(Arrays.toString(abc));


}


}

归并排序

  • 利用了分治的思想,先分再合来排序。降低问题的难度,逐一突破。
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
61
62
63
64
65
66
67
package src.datastructure;

import java.util.Arrays;

/**
* @Author: yhy
* @Time: 0:06
*/
public class MergeSort {
public static void main(String[] args) {
// 自顶向下的归并排序
int[] abc = {1, 9, -2, 40, 33, 6, 5};
int[] temp = new int[abc.length];
mergeSort(abc, 0, abc.length - 1, temp);
System.out.println(Arrays.toString(abc));


}

// 分加合
public static void mergeSort(int[] arr, int left, int right, int[] temp) {
if (left < right) {
int mid = (left + right) / 2; //中间索引
//向左递归进行分解
mergeSort(arr, left, mid, temp);
//向右递归进行分解
mergeSort(arr, mid + 1, right, temp);
//合并
merge(arr, left, mid, right, temp);

}

}

// 合方法
public static void merge(int[] arr, int left, int mid, int right, int[] temp) {
int leftStart = left;
int rightStart = mid + 1;
int i = 0;
// 这里注意可以等于
while (leftStart <= mid && rightStart <= right) {
if (arr[leftStart] >= arr[rightStart]) {
temp[i++] = arr[rightStart++];
} else {
temp[i++] = arr[leftStart++];
}
}
while (leftStart <= mid) {
temp[i++] = arr[leftStart++];
}

while (rightStart <= right) {
temp[i++] = arr[rightStart++];
}


// copy array
i = 0;
int tempLeft = left;
while (tempLeft <= right) {
arr[tempLeft++] = temp[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
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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
package com.atguigu.sort;

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

public class RadixSort {

public static void main(String[] args) {
int arr[] = { 53, 3, 542, 748, 14, 214};

// 80000000 * 11 * 4 / 1024 / 1024 / 1024 =3.3G
// int[] arr = new int[8000000];
// for (int i = 0; i < 8000000; i++) {
// arr[i] = (int) (Math.random() * 8000000); // 生成一个[0, 8000000) 数
// }

radixSort(arr);
System.out.println("基数排序后 " + Arrays.toString(arr));

}

//基数排序方法
public static void radixSort(int[] arr) {

//根据前面的推导过程,我们可以得到最终的基数排序代码

//1. 得到数组中最大的数的位数
int max = arr[0]; //假设第一数就是最大数
for(int i = 1; i < arr.length; i++) {
if (arr[i] > max) {
max = arr[i];
}
}
//得到最大数是几位数
int maxLength = (max + "").length();


//定义一个二维数组,表示10个桶, 每个桶就是一个一维数组
//说明
//1. 二维数组包含10个一维数组
//2. 为了防止在放入数的时候,数据溢出,则每个一维数组(桶),大小定为arr.length
//3. 名明确,基数排序是使用空间换时间的经典算法
int[][] bucket = new int[10][arr.length];

//为了记录每个桶中,实际存放了多少个数据,我们定义一个一维数组来记录各个桶的每次放入的数据个数
//可以这里理解
//比如:bucketElementCounts[0] , 记录的就是 bucket[0] 桶的放入数据个数
int[] bucketElementCounts = new int[10];


//这里我们使用循环将代码处理

for(int i = 0 , n = 1; i < maxLength; i++, n *= 10) {
//(针对每个元素的对应位进行排序处理), 第一次是个位,第二次是十位,第三次是百位..
for(int j = 0; j < arr.length; j++) {
//取出每个元素的对应位的值
int digitOfElement = arr[j] / n % 10;
//放入到对应的桶中
bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
bucketElementCounts[digitOfElement]++;
}
//按照这个桶的顺序(一维数组的下标依次取出数据,放入原来数组)
int index = 0;
//遍历每一桶,并将桶中是数据,放入到原数组
for(int k = 0; k < bucketElementCounts.length; k++) {
//如果桶中,有数据,我们才放入到原数组
if(bucketElementCounts[k] != 0) {
//循环该桶即第k个桶(即第k个一维数组), 放入
for(int l = 0; l < bucketElementCounts[k]; l++) {
//取出元素放入到arr
arr[index++] = bucket[k][l];
}
}
//第i+1轮处理后,需要将每个 bucketElementCounts[k] = 0 !!!!
bucketElementCounts[k] = 0;

}

}


}
}
  • leetcode 347题
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
package src.datastructure;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
* @Author: yhy
* @Time: 14:37
* leetcode #347
* 用到了桶排序的思想
*/
public class BucketSort {
// Given [1,1,1,2,2,3] and k = 2, return [1,2].
public static void main(String[] args) {
int[] arr = new int[]{1, 1, 1, 2, 2, 3};
int[] a = bucketsort(arr);
System.out.println(Arrays.toString(a));
System.out.println(maxReturn(a,2));
}
// 传入数组,返回数组
public static int[] bucketsort(int[] arr){
// 定义一个桶
int[] bucket = new int[10];
for (int val: arr ) {
bucket[val]++;
}
return bucket;
}
private static List maxReturn(int[] arr,int k){
int max = arr[0];
List<Integer> list = new ArrayList<>();
while (k >0) {
for (int i = 1; i < arr.length; i++) {
if (max < arr[i]) {
max = arr[i];
arr[i] = 0;
list.add(i);
}
}
max = 0;
k--;
}
return list;
}


}

堆排序

不稳定,线性复杂度,完全二叉树。

大顶堆

结点大于两边子树,arr[i]>arr[2i+1]&&a[i]>a[2i+2],升序使用这个

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
package src.datastructure.sort;

import java.util.Arrays;

/**
* @Author: yhy
* @Date: 2020/3/19
* @Time: 12:30
*/
public class HeapSort {
public static void main(String[] args) {
int[] arr = {12, 3, 63, 6, 8};
heapsort(arr);
}

public static void heapsort(int[] arr) {
int temp = 0;
System.out.println("堆排序");
//找到第一个大顶堆结构,然后才可以进行下面的代码
for (int i = arr.length / 2 - 1; i >= 0; i--) {
adjustHeap(arr, i, arr.length);
}
System.out.println(Arrays.toString(arr));
//交换数据,数组排序 调整堆结构+交换堆顶元素与末尾元素
for (int i = arr.length - 1; i > 0; i--) {
temp = arr[i];
arr[i] = arr[0];
arr[0] = temp;
adjustHeap(arr, 0, i);
}
System.out.println("排序后的" + Arrays.toString(arr));

}

public static void adjustHeap(int[] arr, int i, int length) {
//不断调整,弄个大顶堆
//后面要进行交换
int temp = arr[i];
//寻找非叶子节点 最后的条件表示左子节点还可以往下寻找
for (int j = i * 2 + 1; j < length; j = j * 2 + 1) {
//左右节点的比较
if (j + 1 < length && arr[j] < arr[j + 1]) {
j++;
}
if (arr[j] > temp) {
arr[i] = arr[j];
i = j;
} else {
break;
}

}

arr[i] = temp;


}


}

小顶堆

结点小于两边子树

思想(借助树的结构完成排序)

  1. 将待排序序列构造成一个大顶堆
  2. 此时序列的最大值就是堆顶的根节点
  3. 将其与数组末尾元素交换,这样构造数组的最大值在右边
  4. 再将n-1个元素重新构造一个堆,这样就会得到n个元素的次小值,反复进行就可以得到一个有序的数组,完成排序