排序算法小结

排序算法经常会忘记,记录下来,方便以后快速查看

定义排序接口


1
2
3
public interface ISort {
public void sort(int[] array);
}

冒泡排序


排序思想

1. 相邻的元素,前面的比后面大,交换位置
2. 每对相邻元素做同样处理,从第一对到结尾的最后一对
3. 针对所有的元素重复以上的步骤,除去上一趟排序的最后一个
4. 重复上面的步骤,直到只剩第一个数字

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class BubbleSort implements ISort {

@Override
public void sort(int[] array) {
for (int i = array.length - 2; i > 0; i--) {
for (int j = 0; j <= i; j++) {
if (array[j] > array[j + 1]) {
int temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
}
}
}
}
}



快速排序


排序思想(一趟排序)

1. 设置两个变量i、j,排序开始的时候:i=0,j=N-1
2. 以第一个数组元素作为关键数据,赋值给key,即key=A[0]
3. 从j开始向前搜索,即由后开始向前搜索(j--),找到第一个小于key的值A[j]
4. 从i开始向后搜索,即由前开始向后搜索(i++),找到第一个大于key的A[i],将A[i]和A[j]交换
5. 重复第3、4步,直到i=j

算法实现

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 class QuickSort implements ISort {
@Override
public void sort(int[] array) {
quickSort(array, 0, array.length - 1);
}

private void quickSort(int[] array, int left, int right) {
if (left > right) {
return;
}
int i = left, j = right;
int flag = array[left];
while (i < j) {
while (j > i && array[j] >= flag) {
j--;
}
while (i < j && array[i] < flag) {
i++;
}
if (i < j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
if (array[i] < array[left]) {
int temp = array[left];
array[left] = array[i];
array[i] = temp;
}
quickSort(array, left, i - 1);
quickSort(array, i + 1, right);
}
}



堆排序


算法思想

1. 创建最大堆(Build Max Heap),使得子节点永远小于父节点
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
public class HeepSort implements ISort {
@Override
public void sort(int[] array) {
heepSort(array);
}

private void heepSort(int[] array) {
for (int i = array.length - 1; i > 0; i--) {
heepUp(array, i);
}
for (int i = array.length - 1; i > 0; i--) {
int tmp = array[0];
array[0] = array[i];
array[i] = tmp;
heepDown(array, i - 1, 0);
}
}

private void heepUp(int[] array, int pos) {
while (pos > 0) {
int father = (pos - 1) / 2;
if (array[pos] > array[father]) {
int tmp = array[pos];
array[pos] = array[father];
array[father] = tmp;
}
pos = father;
}
}

private void heepDown(int[] array, int size, int root) {
int large = root;
int left = root * 2 + 1;
int right = root * 2 + 2;
if (left <= size && array[large] < array[left]) {
large = left;
}
if (right <= size && array[large] < array[right]) {
large = right;
}
if (large != root) {
int tmp = array[root];
array[root] = array[large];
array[large] = tmp;
heepDown(array, size, large);
}
}
}



排序测试



  • 计时辅助工具类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
* 记录一段时间间隔
*/
public class TimeDelta {

private long time;

public TimeDelta() {
this.time = System.currentTimeMillis();
}

public long getDelta() {
return System.currentTimeMillis() - time;
}

public void renew() {
time = System.currentTimeMillis();
}
}



  • 测试代码

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
/**
* 随机生成 n 个数, 分别使用以上实现算法排序,记录耗时
*/
public class SortTest {

public static void main(String[] args) {
int size = 10000;

int[] array = new int[size];
Random random = new Random(System.currentTimeMillis());
TimeDelta timeDelta = new TimeDelta();
ISort sort;

for (int i = 0; i < size; i++) {
array[i] = random.nextInt(100) + 1;
}
sort = new BubbleSort();
timeDelta.renew();
sort.sort(array);
System.out.println(String.format("冒泡耗时(size:%s): %s", size, timeDelta.getDelta()));

for (int i = 0; i < size; i++) {
array[i] = random.nextInt(100) + 1;
}
sort = new QuickSort();
timeDelta.renew();
sort.sort(array);
System.out.println(String.format("快排耗时(size:%s): %s", size, timeDelta.getDelta()));

for (int i = 0; i < size; i++) {
array[i] = random.nextInt(100) + 1;
}
sort = new HeepSort();
timeDelta.renew();
sort.sort(array);
System.out.println(String.format("堆排耗时(size:%s): %s", size, timeDelta.getDelta()));
}
}



  • 测试输出

1
2
3
冒泡耗时(size:100): 1
快排耗时(size:100): 0
堆排耗时(size:100): 0
1
2
3
冒泡耗时(size:1000): 3
快排耗时(size:1000): 0
堆排耗时(size:1000): 0
1
2
3
冒泡耗时(size:10000): 131
快排耗时(size:10000): 4
堆排耗时(size:10000): 5
1
2
3
冒泡耗时(size:100000): 16252
快排耗时(size:100000): 32
堆排耗时(size:100000): 16



  • 结论(数组随机生成)

1. 冒泡排序耗时最久
2. 快速排序在数据量小的时候略优于堆排序,数据量大的时候性能不如堆排序



以上排序算法复杂度


排序算法 时间复杂度 空间复杂度
冒泡排序 O(n^2) O(1)
快速排序 O(n^2) O(1)
堆排序 O(n*log(n)) O(1)






文章目录
  1. 1. 定义排序接口
  2. 2. 冒泡排序
  3. 3. 快速排序
  4. 4. 堆排序
  5. 5. 排序测试
  6. 6. 以上排序算法复杂度