0%

数据结构与算法之排序算法

排序算法是面试中算法考察中的重点,本文总结了各排序算法的实现原理,代码实现和复杂度分析。面试官重点考察快速排序、堆排序和归并排序以及冒泡排序的变型

排序算法总结

排序算法术语说明

稳定:如果a原本在b之前,a=b,排序之后a仍位于b之前;

不稳定:如果a原本在b之前,a=b,排序之后a可能位于b之后;

内排序:所有的排序操作都在内存中完成;

外排序:由于数据太大,数据放在磁盘中,排序通过磁盘和内存的数据传输才能进行;

时间复杂度:一个算法执行消耗的时间;

空间复杂度:运行完一个程序需要的内存大小;

排序算法复杂度总结

排序算法 平均时间复杂度 最好情况 最坏情况 空间复杂度 排序方式 稳定性
冒泡排序 In-place 稳定
选择排序 In-place 不稳定
插入排序 In-place 稳定
希尔排序 In-place 不稳定
归并排序 Out-place 稳定
快速排序 In-place 不稳定
堆排序 In-place 不稳定
桶排序 Out-place 稳定
计数排序 Out-place 稳定
基数排序 Out-place 稳定

名词解释:

​ n:数据规模

​ k:桶的个数

​ In-place:占用常数内存,不占用额外内存

​ Out-place:占用额外内存

排序算法分析

冒泡排序

选择排序

插入排序

希尔排序

归并排序

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。归并排序是一种稳定的排序方法。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为2-路归并。

算法描述

  • 把长度为n的输入序列分为两个长度为(start+end)/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
public class MergeSort {
public static void main(String[] args) {
int[] array = { 9, 6, 3, 1, 2, 8, 7, 5, 4 };
mergeSort(array, 0, array.length - 1);
System.out.println(Arrays.toString(array));
}

//拆分子序列
public static void mergeSort(int[] array, int start, int end) {
if (start < end) {
int mid = (start + end) / 2;
mergeSort(array, start, mid);
mergeSort(array, mid + 1, end);
merge(array, start, mid, end);
}
}

//合并
public static void merge(int[] array, int start, int mid, int end) {
int[] temp = new int[end - start + 1];
int p = start, q = mid + 1, k = 0;
while (p <= mid && q <= end) {
if (array[p] <= array[q]) {
temp[k++] = array[p++];
} else {
temp[k++] = array[q++];
}
}
while (p <= mid) {
temp[k++] = array[p++];
}
while (q <= end) {
temp[k++] = array[q++];
}
k = 0;
for (int i = start; i <= end; i++) {
array[i] = temp[k++];
}
}
}

时间复杂度分析

最佳情况:T(n) = O(n) 最差情况:T(n) = O(nlogn) 平均情况:T(n) = O(nlogn)

快速排序

快速排序的基本思想:通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序。

算法描述

  • 从数列中挑出一个元素,称为“基准”(pivot);
  • 重新排序数列,所有比基准值小的摆放在基准前面,所有比基准值大的元素放在基准后边,返回基准值的下标。分区操作(partition);
  • 递归地把小于基准值元素的子序列和大于基准值元素的子序列排序;

动图演示

快速排序

代码实现

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
public class QuickSort {
public static void main(String[] args) {
int[] array = { 9, 6, 3, 1, 2, 8, 7, 5, 4 };
quickSort(array, 0, array.length - 1);
System.out.println(Arrays.toString(array));
}

public static void quickSort(int[] array, int low, int high) {
if (low >= high)
return;
else {
int position = sortOnce(array, low, high);
quickSort(array, low, position - 1);
quickSort(array, position + 1, high);
}
}

public static int sortOnce(int[] array, int low, int high) {
int povit = array[low];
while (low < high) {
while (low < high && array[high] >= povit) {
high--;
}
if (low < high) {
swap(array, low, high);
low++;
}
while (low < high && array[low] < povit) {
low++;
}
if (low < high) {
swap(array, low, high);
low++;
}
}
return low;
}

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

时间复杂度分析

最佳情况:T(n) = O(nlogn) 最差情况:T(n) = O(n2) 平均情况:T(n) = O(nlogn) 

堆排序

堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。

算法描述

  • 将初始待排序序列构建成大顶堆,此堆为初始的无序区;
  • 将堆顶元素与最后一个元素交换,得到新的无序区和新的有序区;
  • 重新调整元素,使无序区保持一个大顶堆,重复步骤二,直到排序完成;

动图演示

堆排序

代码实现

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
public class HeapSort {
public static void main(String[] args) {
int[] array = { 9, 6, 3, 1, 2, 8, 7, 5, 4 };
heapSort(array);
System.out.println(Arrays.toString(array));
}

public static void heapSort(int[] arr) {
// 1.构建大顶堆
for (int i = arr.length / 2 - 1; i >= 0; i--) {
// 从第一个非叶子结点从下至上,从右至左调整结构
adjustHeap(arr, i, arr.length);
}
// 2.调整堆结构+交换堆顶元素与末尾元素
for (int j = arr.length - 1; j > 0; j--) {
swap(arr, 0, j);// 将堆顶元素与末尾元素进行交换
adjustHeap(arr, 0, j);// 重新对堆进行调整
}

}

/**
* 调整大顶堆(仅是调整过程,建立在大顶堆已构建的基础上)
*/
public static void adjustHeap(int[] arr, int i, int length) {
int temp = arr[i];// 先取出当前元素i
for (int k = i * 2 + 1; k < length; k = k * 2 + 1) {// 从i结点的左子结点开始,也就是2i+1处开始
if (k + 1 < length && arr[k] < arr[k + 1]) {// 如果左子结点小于右子结点,k指向右子结点
k++;
}
if (arr[k] > temp) {// 如果子节点大于父节点,将子节点值赋给父节点(不用进行交换)
arr[i] = arr[k];
i = k;
} else {
break;
}
}
arr[i] = temp;// 将temp值放到最终的位置
}

/**
* 交换元素
*/
public static void swap(int[] arr, int a, int b) {
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
}
-------------本文结束感谢您的阅读-------------
坚持原创技术分享,您的支持将鼓励我继续创作!

本文标题:数据结构与算法之排序算法

文章作者:Cheng Dong

发布时间:2019年11月26日 - 10:21

最后更新:2019年11月26日 - 15:39

原始链接:https://www.dchengsd.com/posts/d1255ec9/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。