算法基础-常用排序算法总结

写在前面

  以前的自己怕是个假的准“程序员”,基础的排序算法忘的一干二净,更别说手写快排。赶紧抓紧时间去又去学习了常用的排序算法,加深理解,


概述

排序方法 平均情况 最好情况 最坏情况 辅助空间
冒泡排序 O(n²) O(n) O(n²) O(1)
简单选择排序 O(n²) O(n²) O(n²) O(1)
直接插入排序 O(n²) O(n) O(n²) O(1)
希尔排序 O(nlogn)~O(n²) O(n^1.3) O(n²) O(1)
堆排序 O(nlogn) O(nlogn) O(nlogn) O(1)
归并排序 O(nlogn) O(nlogn) O(nlogn) O(n)
快速排序 O(nlogn) O(nlogn) O(n²) O(logn)~O(n)

时间复杂度:

在计算机科学中,算法的时间复杂度是一个函数,它定量描述了该算法的运行时间。这是一个关于代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述,不包括这个函数的低阶项和首项系数。

空间复杂度:

空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度,记做S(n)=O(f(n))。比如直接插入排序的[时间复杂度是O(n^2),空间复杂度是O(1) 。

时间复杂度和空间复杂度:

对于一个算法,其时间复杂度和空间复杂度往往是相互影响的。当追求一个较好的时间复杂度时,可能会使空间复杂度的性能变差,即可能导致占用较多的存储空间;反之,当追求一个较好的空间复杂度时,可能会使时间复杂度的性能变差,即可能导致占用较长的运行时间。另外,算法的所有性能之间都存在着或多或少的相互影响。因此,当设计一个算法(特别是大型算法)时,要综合考虑算法的各项性能,算法的使用频率,算法处理的数据量的大小,算法描述语言的特性,算法运行的机器系统环境等各方面因素,才能够设计出比较好的算法。算法的时间复杂度和空间复杂度合称为算法的复杂度。

排序算法稳定性:

排序算法稳定性的简单形式化定义为:如果Ai = Aj,排序前Ai在Aj之前,排序后Ai还在Aj之前,则称这种排序算法是稳定的。通俗地讲就是保证排序前后两个相等的数的相对顺序不变。

以上,摘自网络。


冒泡排序

算法思路

  1. 比较相邻的两个元素,如果前一个比后一个大,则交换
  2. 一轮比较交换后,最后的元素则是最大的数
  3. 经过多轮比较交换,直到排序完毕

算法实现

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 class BubbleSort {

public static void exch(int[] n, int i, int j) {
int temp = n[i];
n[i] = n[j];
n[j] = temp;
}

public static void show(int[] n) {
for (int i = 0; i < n.length; i++) {
System.out.print(n[i] + " ");
}
}

public static void main(String[] args) {
int[] n = {1, 5, 8, 9, 10, 6, 3};
int length = n.length;
for (int i = 0; i < length - 1; i++) {
for (int j = 0; j < length - 1 - i; j++) {
if (n[j] > n[j+1]) exch(n, j, j+1); //如果前一个比后一个大,则交换
}
}
show(n);
}
}

简单选择排序

算法思路

  1. 找到数组中最小的那个元素
  2. 将它和数组的第一个元素交换位置,如果第一个元素就是最小元素那么它就和自己交换
  3. 在剩下的元素中找到最小的元素,与数组第二个元素交换位置。一直重复,知道整个数组排序

算法实现

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
public class SelectionSort {
public static void exch(int[] n, int i, int j) {
int temp = n[i];
n[i] = n[j];
n[j] = temp;
}

public static void show(int[] n) {
for (int i = 0; i < n.length; i++) {
System.out.print(n[i] + " ");
}
}

public static void main(String[] args) {
int[] n = {1, 5, 8, 9, 10, 6, 3};
int length = n.length;
for (int i = 0; i < length; i++) {
int min = i;
for (int j = i + 1; j < length; j++) {
if (n[j] < n[min]) min = j;
}
exch(n, i, min);
}
show(n);
}
}

直接插入排序

算法思路

  1. 从第一个元素开始,该元素可以认为已经被排序
  2. 取出下一个元素,在已经排序的元素序列中从后向前扫描
  3. 如果已排序元素大于新元素,则将已排序的这个元素向后移动一位
  4. 一直重复第三步,直到已排序元素小于等于新元素
  5. 将新元素插入该位置
  6. 重复2-5步

算法实现

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 class InsertionSort {

public static void exch(int[] n, int i, int j) {
int temp = n[i];
n[i] = n[j];
n[j] = temp;
}

public static void show(int[] n) {
for (int i = 0; i < n.length; i++) {
System.out.print(n[i] + " ");
}
}

public static void main(String[] args) {
int[] n = {1, 5, 8, 9, 10, 6, 3};
int length = n.length;
for (int i = 1; i < length; i++) {
for (int j = i; j > 0 && n[j] < n[j-1]; j--) {
exch(n, j, j-1);
}
}
show(n);
}
}

希尔排序

  希尔排序是基于插入排序的快速的排序算法,可以交换不相邻的元素以对数组的局部进行排序,并最终用插入排序将局部有序的数组排序。

算法思路

  使数组中间隔为h的元素都是有序的,将全部元素分为几个区域来提升插入排序的性能,可以使一个元素向它的最终位置前进一大步。然后再取越小的步长h进行排序,最后一步是普通的插入排序,这个时候需要排序的数据几乎使已经排序好了,所以这个时候插入排序会很快。


算法实现

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
public class ShellSort {
public static void exch(int[] n, int i, int j) {
int temp = n[i];
n[i] = n[j];
n[j] = temp;
}

public static void show(int[] n) {
for (int i = 0; i < n.length; i++) {
System.out.print(n[i] + " ");
}
}

public static void main(String[] args) {
int[] n = {1, 5, 8, 9, 10, 6, 3};
int length = n.length;
int h = 0;
while (h <= length) h = 3 * h + 1;
while (h >= 1) {
for (int i = h; i < length; i++) {
for (int j = i; j >= h && n[j] < n[j-h]; j-=h) {
exch(n, j, j-h);
}
}
h = (h - 1) / 3;
}
show(n);
}
}

归并排序

  归并排序是创建在归并操作上的一种有效的排序算法,效率为O(nlogn),1945年由冯·诺伊曼首次提出。

算法实现

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
public class MergeSort {
private int[] aux;
public int[] mergeSort(int[] A, int n) {
aux = new int[n];
sort(A, 0, n - 1);
return A;
}
public void sort(int[] nums, int left, int right) {
if (left >= right) return;
int mid = left + (right - left) / 2;
sort(nums, left, mid);
sort(nums, mid + 1, right);
merge(nums, left, mid, right);
}
public void merge(int[] nums, int left, int mid, int right) {
int i = left;
int j = mid + 1;
for (int k = left; k <= right; k++) {
aux[k] = nums[k];
}
for (int k = left; k <= right; k++) {
if (i > mid) nums[k] = aux[j++];
else if (j > right) nums[k] = aux[i++];
else if (aux[i] > aux[j]) nums[k] = aux[j++];
else nums[k] = aux[i++];
}
}
}

堆排序

  堆排序是指利用堆这种数据结构所设计的一种选择排序算法。堆是一种近似完全二叉树的结构(通常堆是通过一维数组来实现的),并满足性质:以最大堆(也叫大根堆、大顶堆)为例,其中父结点的值总是大于它的孩子节点。

算法思路  

  1. 由输入的无序数组构造一个最大堆,作为初始的无序区
  2. 把堆顶元素(最大值)和堆尾元素互换
  3. 把堆(无序区)的尺寸缩小1,并调用heapify(A, 0)从新的堆顶元素开始进行堆调整
  4. 重复步骤2,直到堆的尺寸为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
35
36
37
38
39
40
public class HeapSort {
public int[] heapSort(int[] A, int n) {
int heapSize = buildHeap(A, n);
while (heapSize > 1) {
swap(A, 0, --heapSize);
heapify(A, 0, heapSize);
}
return A;
}

public void heapify(int[] A, int i, int size) {
int left = 2 * i + 1;
int right = 2 * i + 2;
int max = i;
if (left < size && A[left] > A[max]) {
max = left;
}
if (right < size && A[right] > A[max]) {
max = right;
}
if (max != i) {
swap(A, i, max);
heapify(A, max, size);
}
}

public int buildHeap(int[] A, int n) {
int heapSize = n;
for (int i = heapSize / 2 - 1; i >= 0; i--) {
heapify(A, i, heapSize);
}
return heapSize;
}

public void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}

快速排序

  快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序n个元素要O(nlogn)次比较。在最坏状况下则需要O(n^2)次比较,但这种状况并不常见。事实上,快速排序通常明显比其他O(nlogn)算法更快,因为它的内部循环可以在大部分的架构上很有效率地被实现出来。

算法思路

  快速排序是使用分治策略来把一个序列分为两个子序列,两个子序列有序了,整个序列也就有序了。

  1. 随机选取一个元素,与序列最后一个元素交换
  2. 将比该元素小的放到前面,大的放到后面,该步骤叫做分区操作
  3. 一直递归,直到整个序列有序

算法实现

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
public class QuickSort {
public int[] quickSort(int[] A, int n) {
sort(A, 0, n - 1);
return A;
}

private void sort(int[] nums, int lo, int hi) {
if (lo >= hi) return;
int mid = partition(nums, lo, hi);
sort(nums, lo, mid - 1);
sort(nums, mid + 1, hi);
}
private int partition(int[] nums, int lo, int hi) {
int random = lo + (int) (Math.random() * (hi - lo + 1));
swap(nums, hi, random);
int preArray = lo - 1;
int index = lo;
while (index <= hi) {
if (nums[index] <= nums[hi]) {
swap(nums, index, ++preArray);
}
index++;
}
return preArray;
}
private void swap(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}

小结

  记录一下常用的排序算法,方便自己以后查看。更详细的介绍可以到参考资料中查看。


参考资料

  • 《算法》第四版
Author: HowieLi
Link: https://www.howieli.cn/posts/common-sort-algorithm.html
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.