admin 管理员组

文章数量: 887031


2024年2月7日发(作者:玳瑁真的能活1500岁)

基于比较的排序算法有哪些

七种排序算法[1]分别是:

四种基本排序算法:冒泡排序,选择排序,插入排序,希尔排序。

三种高级排序算法:归并排序,快速排序,堆排序。

这七种排序算法都是比较排序算法,这种算法的特点顾名思义就是排序是依赖于元素间两两比较的结果[2]。

任何比较算法在最坏的情况下都要经过Ω(nlgn)次比较。

1. 冒泡排序

顾名思义,冒泡排序的整个过程就像碳酸饮料 中的小气泡,慢慢浮到最上面。只不过在冒泡排序中浮上去的是最大的数而已。

简要思路: 遍历数组,每次比较相邻的两个元素 arr[i],

arr[i + 1],如果 arr[i + 1] < arr[i] ,就把 arr[i + 1]

和 arr[i] 调换位置。

冒泡排序有这样的排序特性:

每次都只排好一个元素。

最坏情况时间复杂度为O(n^2)。

平均情况时间复杂度为O(n^2)。

需要额外空间O(1)。

所需时间与输入数组的初始状态无关。

算法示例

public static void bubbleSort(int[] arr) {

int n = ;

// 每一次循环,都把最大的元素冒泡到对应的位置

for (int i = 0; i < n - 1; ++i) {

for (int j = 0; j < n - i - 1; ++j) {

// 如果后一个比前一个小,那么就把大的放后面

if (less(arr, j + 1, j)) exch(arr, j, j +

1);

}

}

}

2. 选择排序

其实选择排序,直观上来说和冒泡排序差不多,只不过么有了相邻元素频繁交换的操作,但是却保留了冒泡排序频繁访问数组的特点。

简要思路:对于每一个循环,我们在剩余的未排序数中找到最小数对应的下标,遍历一次后再把对应的数放到合适的位置。

选择排序有这样的排序特性:

每次循环都只排好一个元素。

最坏情况时间复杂度为Theta (n^2)。

平均情况时间复杂度为Theta (n^2)。

需要额外空间为O(1)。

所需时间和输入数组的初始状态无关。

算法示例

public static void selectionSort(int[] arr) {

int n = ;

// 每一次循环,都会把剩余未排数组的最小值放到对应的位置上去

for (int i = 0; i < n; ++i) {

int min = i;

for (int j = i + 1; j < n; ++j) {

if (less(arr, j, min)) min = j;

}

exch(arr, min, i);

}

}

3. 插入排序

插入排序和前面两个基本排序算法有相似性质,多了的一条就是对输入的数组的随机性有了一定关系,加入输入数组已经基本有序,时间复杂度会降为O(n)。

简单思路:类似于打牌的时候整理自己手里的扑克牌。一次选择一张卡,并将其插入先前订购的卡的正确位置。

插入排序有这样的排序特性:

每次排好一个元素。

最坏情况时间复杂度为Theta (n^2)。

平均情况时间复杂度为Theta (n^2)。

需要额外空间为O(1)。

所需时间与输入数组的初始状态有关。

算法示例

public static void insertSort(int[] arr) {

int n = ;

for (int i = 1; i < n; ++i) {

// [0, i - 1] 已经有序了,然后把 arr[i] 插入到

[0, i - 1] 中合适位置就好了

// 放好之后,就可以停止遍历了,因为前面的也一定是排好序的

for (int j = i; j > 0 && less(arr, j, j - 1);

--j) {

exch(arr, j, j - 1);

}

}

}

4. 希尔排序

Hill排序本质上是插入排序的改进版本,其性能依赖于主观参数的调整。到目前为止,彻底分析Hill排序的排序性能仍然具有挑战性(不完整),所以这里主要分析算法的特点。

简要思路: 在插入排序中,每一次只移动了一个元素嘛,所以在希尔排序中,为了加快排序速度改进了交换步长。通过交换不相邻的元素对数组进行局部排序,并在小的分组中使用插入排序来完成。

希尔排序的排序特性:

性能依赖于参数 h (步长)的设置,而 h 的设置又依赖于 h 序列的性质 ……

算法示例

public static void shellSort(int[] arr) {

int n = ;

int h = 1; // 这就是传说中的那个步长

while (h < n / 3) h = 3 * h + 1; // 1, 4, 13, 40...

while (h >= 1) {

for (int i = h; i < n; ++i) {

// 插入排序,从原来的 [j, j - 1] 变成了 [j,

j - h]

for (int j = i; j >= h && less(arr, j, j -

h); j -= h) exch(arr, j, j - h);

}

h /= 3;

}

}

5. 归并排序

有意思的来了, 归并排序顾名思义依赖于归并这个操作,详细来说就是将两个有序数组进行归并。

简要思路: 将一个大数组排序,可以先将其切分成两个小数组分别排序,对于两个小数组,又可以分别将两个小数组切分成两个小小数组进行排序……各自完成排序后,向上归并,那么整体就有序了。

归并排序算法特性:

任意长的数组n,排序时间和nlgn成正比。

最坏情况时间复杂度Theta (nlgn)。

平均情况时间复杂度Theta (nlgn)。

需要额外空间为O(n)。

小规模应使用插入排序,避免过度调用递归。

算法示例

public static void mergeSort(int[] arr) {

mergeSort(arr, 0, - 1, new

int[]);

}

private static void mergeSort(int[] arr, int left, int

right, int[] aux) {

if (left >= right) return;

// 找到切分中点位置

int mid = left + (right - left) / 2;

mergeSort(arr, left, mid, aux); // 排序左边

mergeSort(arr, mid + 1, right, aux); // 排序右边

merge(arr, left, mid, right, aux); // 归并最后的结果

}

// 归并函数

private static void merge(int[] arr, int left, int mid,

int right, int[] aux) {

for (int k = left; k <= right; ++k) aux[k] =

arr[k];

int i = left, j = mid + 1;

for (int k = left; k <= right; ++k) {

if (i > mid) arr[k] = aux[j++]; // 如果左半部分已经放完了,那么就只放右边的

else if (j > right) arr[k] = aux[i++]; // 同样的,如果右半部分已经都放进去了,就只放左边的

else if (less(aux, i, j)) arr[k] = aux[i++];

// 否则的话,捡着小的放

else arr[k] = aux[j++];

}

}

6. 快速排序

更有意思的来了! 快速排序是目前应用最广,最有意思的一个排序算法,速度快,空间利用率高,名副其实是理想中最快的算法了。

简要思路: 快速排序和归并排序正好互补,归并排序是将两个有序子数组进行归并后,整个子数组就有序了,而快速排序是当两个子数组都有序的时候,整个数组也就有序了。

与归并排序的不同:

归并排序的递归发生在处理整个数组前,快速排序的递归发生在处理整个数组后。

归并排序是将数组切分为两个长度一致(或差一个)的子数组,快速排序的切分结果依赖于 partition 函数的结果,也就是依赖于数组的内容。

快速排序算法特性:

时间复杂度和空间复杂度都很优秀,就像是上一节课的学霸。学好体育也不错。

最坏情况时间复杂度为Theta (n^2)。

平均情况时间复杂度为Theta (nlgn)。

空间复杂度O(1)。

只有当原始数组完全随机化才会达到理论上最优情况,那么相反的,如果数组原来就有序,这时候就成了快速排序的最差情况。

对于小数组,最好插入sort。

public static void quickSort(int[] arr) {

quickSort(arr, 0, - 1);

}

private static void quickSort(int[] arr, int left, int

right) {

if (left > right) return;

int mid = partition(arr, left, right);

quickSort(arr, left, mid - 1);

quickSort(arr, mid + 1, right);

}

private static int partition(int[] arr, int left, int

right) {

int val = arr[left];

int lo = left, hi = right + 1;

while (true) {

while (arr[++lo] <= val) if (lo >= right)

break;

while (arr[--hi] >= val) if (hi <= left) break;

if (lo >= hi) break;

exch(arr, lo, hi);

}

exch(arr, left, hi);

return hi;

}

7. 堆排序

最有意思的来了!堆排序其实是一个意外收获,因为一开始就是利用堆的数据结构。后来大家伙发现可以用来排序,就有了现在的堆排序。

简要思路: 在堆的构建阶段,将数据从数组中逐个放到堆中。在排序结果的获取阶段,将数据再从堆中挨个放到数组中。

堆排序算法特性:

取决于堆的基本特征,例如浮动和下沉操作。

最坏情况时间复杂度为O(nlgn)。

现代设备中很少使用它,因为元素很少和相邻的其他元素作比较,因此缓存未命中的次数要远远高于其他对相邻元素作比较的算法。

经常使用堆实现的优先级队列。

public static void heapSort(int[] arr) {

int n = ;

int[] heap = new int[n + 1];

int idx = 0;

// 将元素挨个入堆,并上浮

for (int num : arr) {

heap[++idx] = num;

swim(heap, idx);

}

// 构建排序结果

for (int i = 0; i < n; ++i) arr[i] =

deleteMin(heap, idx--);

}

// 删除堆中的最小元素,并重新调整堆

private static int deleteMin(int[] arr, int idx) {

int ret = arr[1];

exch(arr, 1, idx--);

arr[idx + 1] = 0;

sink(arr, 1, idx);

return ret;

}

// 堆的下沉操作

private static void sink(int[] arr, int k, int idx) {

while (2 * k <= idx) {

int j = 2 * k;

if (j < idx && less(arr, j + 1, j)) ++j;

if (!less(arr, j, k)) break;

exch(arr, j, k);

k = j;

}

}

// 堆的上浮操作

private static void swim(int[] arr, int idx) {

while (idx > 1 && less(arr, idx, idx / 2)) {

exch(arr, idx, idx / 2);

idx /= 2;

}

}

对于前面四种基本算法,优化的空间就不是很大了,但是对于后面的三种基本算法plus,还是有很多优化的空间的,不过呢,整体思路都是一样的。

洗洗睡洗洗睡了 ,(⊙o⊙),差点忘了继续记录,这周力扣爬到了1,322。

参考资料

[1]

《算法》第四版:

第二章:排序

[2]

《算法导论》第三版:

第二部分:排序和顺序统计量


本文标签: 排序 数组 算法 归并 元素