数据结构与算法之排序

用户头像
shirley
关注
发布于: 8 小时前

排序算法分析

  1. 执行效率:从时间复杂度角度衡量。

  2. 内存消耗:从空间复杂度角度衡量。原地排序算法,指空间复杂度为O(1)的算法。

  3. 稳定性:如果待排序的序列中存在值相等的元素,经过排序之后,相等元素之间原有的先后顺序不变



比如说,我们现在要给电商交易系统中的“订单”排序。订单有两个属性,一个是下单时间,另一个是订单金额。如果我们现在有 10 万条订单数据,我们希望按照金额从小到大对订单数据排序。对于金额相同的订单,我们希望按照下单时间从早到晚有序。



冒泡排序(Bubble Sort)

原地排序、稳定、时间复杂度O(n^2)

冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较,看是否满足大小关系要求。如果不满足就让它俩互换。一次冒泡会让至少一个元素移动到它应该在的位置,重复 n 次,就完成了 n 个数据的排序工作。



/**
* 冒泡排序改进:在每一轮排序后记录最后一次元素交换的位置,作为下次比较的边界,
* 对于边界外的元素在下次循环中无需比较.
*/
public void bubbleSort(int[] a, int n) {
if (n <= 1) return;
// 最后一次交换的位置
int lastExchange = 0;
// 无序数据的边界,每次只需要比较到这里即可退出
int sortBorder = n - 1;
for (int i = 0; i < n; i++) {
// 提前退出标志位
boolean flag = false;
for (int j = 0; j < sortBorder; j++) {
if (a[j] > a[j + 1]) {
int tmp = a[j];
a[j] = a[j + 1];
a[j + 1] = tmp;
// 此次冒泡有数据交换
flag = true;
// 更新最后一次交换的位置
lastExchange = j;
}
}
sortBorder = lastExchange;
if (!flag) break; // 没有数据交换,提前退出
}
}



插入排序(Insertion Sort)

原地排序、稳定、时间复杂度O(n^2)

将数组中的数据分为两个区间,已排序区间和未排序区间。初始已排序区间只有一个元素,就是数组的第一个元素。插入算法的核心思想是取未排序区间中的元素,在已排序区间中找到合适的插入位置将其插入,并保证已排序区间数据一直有序。重复这个过程,直到未排序区间中元素为空,算法结束。

未排序中选择第一位 值为 value,与已排序中数据从后往前进行比较,已排序比value大的往后移位,直到已排序中没有大于value,将value插入

// 插入排序,a表示数组,n表示数组大小
public void insertionSort(int[] a, int n) {
if (n <= 1) return;
for (int i = 1; i < n; ++i) {
int value = a[i];
int j = i - 1;
// 查找插入的位置
for (; j >= 0; --j) {
if (a[j] > value) {
a[j+1] = a[j]; // 数据移动
} else {
break;
}
}
a[j+1] = value; // 插入数据
}
}



选择排序(Selection Sort)

原地排序、不稳定、时间复杂度O(n^2)

选择排序算法的实现思路有点类似插入排序,也分已排序区间和未排序区间。但是选择排序每次会从未排序区间中找到最小的元素,将其放到已排序区间的末尾。

未排序中两两比较,取最小值,与未排序第一位交换。

// 选择排序,a表示数组,n表示数组大小
public void selectionSort(int[] a, int n) {
if (n <= 1) return;
for (int i = 0; i < n - 1; ++i) {
// 查找最小值
int minIndex = i;
for (int j = i + 1; j < n; ++j) {
if (a[j] < a[minIndex]) {
minIndex = j;
}
}
// 交换
int tmp = a[i];
a[i] = a[minIndex];
a[minIndex] = tmp;
}
}



归并排序(Merge Sort)

非原地排序,空间复杂度O(n)、稳定、时间复杂度O(nlogn)

先把数组从中间分成前后两部分,然后对前后两部分分别排序,再将排好序的两部分合并在一起,这样整个数组就都有序了。



// 归并排序算法, A是数组,n表示数组大小
merge_sort(A, n) {
merge_sort_c(A, 0, n-1)
}
// 递归调用函数
merge_sort_c(A, p, r) {
// 递归终止条件
if p >= r then return
// 取p到r之间的中间位置q
q = (p+r) / 2
// 分治递归
merge_sort_c(A, p, q)
merge_sort_c(A, q+1, r)
// 将A[p...q]和A[q+1...r]合并为A[p...r]
merge(A[p...r], A[p...q], A[q+1...r])
}



merge(A[p...r], A[p...q], A[q+1...r]) {
var i := p,j := q+1,k := 0 // 初始化变量i, j, k
var tmp := new array[0...r-p] // 申请一个大小跟A[p...r]一样的临时数组
while i<=q AND j<=r do {
if A[i] <= A[j] {
tmp[k++] = A[i++] // i++等于i:=i+1
} else {
tmp[k++] = A[j++]
}
}
// 判断哪个子数组中有剩余的数据
var start := i,end := q
if j<=r then start := j, end:=r
// 将剩余的数据拷贝到临时数组tmp
while start <= end do {
tmp[k++] = A[start++]
}
// 将tmp中的数组拷贝回A[p...r]
for i:=0 to r-p do {
A[p+i] = tmp[i]
}
}

空间复杂度:尽管每次合并操作都需要申请额外的内存空间,但在合并完成之后,临时开辟的内存空间就被释放掉了。在任意时刻,CPU 只会有一个函数在执行,也就只会有一个临时的内存空间在使用。临时内存空间最大也不会超过 n 个数据的大小,所以空间复杂度是 O(n)。



快速排序(Quick Sort)

原地排序、不稳定、时间复杂度O(nlogn)

如果要排序数组中下标从 p 到 r 之间的一组数据,我们选择 p 到 r 之间的任意一个数据作为 pivot(分区点)。遍历 p 到 r 之间的数据,将小于 pivot 的放到左边,大于 pivot 的放到右边,pivot 放到中间。根据分治、递归的处理思想,我们可以用递归排序下标从 p 到 q-1 之间的数据和下标从 q+1 到 r 之间的数据,直到区间缩小为 1,就说明所有的数据都有序了。







// 快速排序,A是数组,n表示数组的大小
quick_sort(A, n) {
quick_sort_c(A, 0, n-1)
}
// 快速排序递归函数,p,r为下标
quick_sort_c(A, p, r) {
if p >= r then return
q = partition(A, p, r) // 获取分区点
quick_sort_c(A, p, q-1)
quick_sort_c(A, q+1, r)
}
partition(A, p, r) {
pivot := A[r]
i := p
for j := p to r-1 do {
if A[j] < pivot {
swap A[i] with A[j]
i := i+1
}
}
swap A[i] with A[r]
return i

快速排序优化

如果数据原来就是有序的或者接近有序的,每次分区点都选择最后一个数据,那快速排序时间复杂度就会退化为 O(n^2)。实际上,这种 O(n^2) 时间复杂度出现的主要原因还是因为我们分区点选得不够合理。



最理想的分区点是:被分区点分开的两个分区中,数据的数量差不多。

三数取中法

从区间的首、尾、中间,分别取出一个数,然后对比大小,取这 3 个数的中间值作为分区点。这样每间隔某个固定的长度,取数据出来比较,将中间值作为分区点的分区算法,肯定要比单纯取某一个数据更好。但是,如果要排序的数组比较大,那“三数取中”可能就不够了,可能要“五数取中”或者“十数取中”。



堆排序(Heap)

原地排序、不稳定、时间复杂度O(nlogn)

堆概念

堆是一种特殊的树,满足如下两点,它就是一个堆:

  • 堆是一个完全二叉树;

  • 堆中每一个节点的值都必须大于等于(或小于等于)其子树中每个节点的值。



对于每个节点的值都大于等于其子树中每个节点值的堆,我们叫做“大顶堆”。对于每个节点的值都小于等于其子树中每个节点值的堆,我们叫做“小顶堆”。



堆是一种完全二叉树,比较适合用数组来存储,不需要存储左右子节点的指针,单纯地通过数组的下标,就可以找到一个节点的左右子节点和父节点。



如果从 1 开始存储,数组中下标为 i 的节点,左子节点是下标为 i*2 的节点,右子节点就是下标为 i*2+1 的节点,父节点就是下标为 i/2 的节点。

如果从 0 开始存储,节点的下标是 i,那左子节点的下标就是 2*i+1,右子节点的下标就是 2*i+2,父节点的下标就是 (i-1)/2。



堆中比较重要的两个操作是插入一个数据和删除堆顶元素。这两个操作都要用到堆化。

  • 插入一个数据时,把新插入的数据放到数组的最后,然后从下往上堆化

  • 删除堆顶数据时,把数组中的最后一个元素放到堆顶,然后从上往下堆化



一个包含 n 个节点的完全二叉树树的高度不会超过 logn。堆化的过程是顺着节点所在路径比较交换的,所以堆化的时间复杂度跟树的高度成正比,也就是 O(logn)。插入数据和删除堆顶元素的主要逻辑就是堆化,所以,往堆中插入一个元素和删除堆顶元素的时间复杂度都是 O(logn)

堆排序

堆排序包含两个过程,建堆和排序。我们将下标从 n/2​ 到 1 的节点,依次进行从上到下的堆化操作,然后就可以将数组中的数据组织成堆这种数据结构。接下来,我们迭代地将堆顶的元素放到堆的末尾,并将堆的大小减一,然后再堆化,重复这个过程,直到堆中只剩下一个元素,整个数组中的数据就都有序排列了。

建堆

对下标从 n/2​ 到 1 的数据进行堆化,下标是 n/2​+1 到 n 的节点是叶子节点,不需要堆化。

private static void buildHeap(int[] a, int n) {
for (int i = n/2; i >= 1; --i) {
heapify(a, n, i);
}
}
private static void heapify(int[] a, int n, int i) {
while (true) {
int maxPos = i;
if (i*2 <= n && a[i] < a[i*2]) maxPos = i*2;
if (i*2+1 <= n && a[maxPos] < a[i*2+1]) maxPos = i*2+1;
if (maxPos == i) break;
swap(a, i, maxPos);
i = maxPos;
}
}
排序



// n表示数据的个数,数组a中的数据从下标1到n的位置。
public static void sort(int[] a, int n) {
buildHeap(a, n);
int k = n;
while (k > 1) {
swap(a, 1, k);
--k;
heapify(a, k, 1);
}
}

堆的应用

  1. 优先级队列:队列是先进先出,不过,在优先级队列中,数据的出队顺序不是先进先出,而是按照优先级来,优先级最高的,最先出队。

譬如:合并有序小文件、高效定时器

  1. Top K

  2. 求中位数



用户头像

shirley

关注

还未添加个人签名 2019.04.02 加入

还未添加个人简介

评论

发布
暂无评论
数据结构与算法之排序