JavaScript实现各种排序

- 日理万妓 2024-04-19 00:04 3阅读 0赞

### 快速排序： ###

思路：

（1）在数组中，选择一个元素作为基准值（pivot）。

（2）所有小于基准值的元素，都移到基准值的左边；所有大于基准值的元素，都移到基准值的右边。

（3）对基准值左边和右边的两个子集，不断递归地进行排序，直到所有子集只剩下一个元素为止。

总结：

（1）冒泡排序是对相邻元素进行比较，做一次交换只能消除一个逆序。快速排序采用分治的策略通过交换两个不相邻的元素，能消除多个逆序，可以加快排序速度。

（2）快速排序的时间复杂度主要取决于基准值的选择。最差情况下，以第一个元素或最后一个元素为基准值，时间复杂度为O(n2)。平均情况下，以中间元素作为基准值，时间复杂度为O(nlog2n)。因为需要lon2n个辅助空间，所以快排的空间复杂度为O(log2n)。

### 选择排序： ###

思路：

（1）从第一个元素开始，将后面n - 1个元素与第一个元素进行比较，找到最小的元素与第一个元素进行交换。

（2）从第二个元素开始，将后面n - 2个元素与第二个元素进行比较，找到最小的元素与第二个元素进行交换。

（3）第三个元素开始依次类推。

### 冒泡排序： ###

（1）第1趟：比较第一个元素和第二个元素，如果逆序，则交换。再比较第二个元素和第三个元素，如果逆序，则交换。经过第一趟的比较和交换，最大的元素必然沉为最后一个元素。

（2）第2趟：比较前n - 1个元素，经过第二趟的比较和交换，第二大的数必然沉为倒数第二个元素。

（3）第3趟依次类推。总共比较n - 1趟。

### **改进后的冒泡排序：** ###

如果一趟排序下来之后，没有发现一个逆序，说明已排好序，就可以结束排序过程。通过设置一个flag,标志是否进行排序操作。

### 归并排序： ###

思路：

归并排序采用的是分治的思想，首先是“分”，将一个数组反复二分为两个小数组，直到每个数组只有一个元素；其次是“治”，从最小的数组开始，两两按大小顺序合并，直到合并为原始数组的大小。图解更清晰：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpc2h1bmRp_size_16_color_FFFFFF_t_70][]

代码如下：

分析：

（1）在归并排序中，递归深度为O(log2n)，关键字的比较次数是O(nlog2n)，总的时间复杂度为O(nlog2n)。因为需要一个辅助数组存放待排序元素，所以为O(n)。

（2）缺点：占用附加存储空间较多，需要一个与原数组同样大小的辅助数组。数据量大时不适合用归并排序。

（3）与快速排序和堆排序相比，归并排序的最大特点是稳定的。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpc2h1bmRp_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/59d30e2bab1e4673aa58585273e3ee2c.png

JavaScript实现各种排序

发表评论取消回复

还没有评论，来说两句吧...

相关阅读

相关 JavaScript实现各种排序

相关 scala实现各种排序算法

相关 C++实现各种排序算法

相关数据结构:JavaScript实现各种排序

相关 javascript实现快速排序

相关各种常见排序算法实现

相关各种排序算法的python实现

相关 javascript实现选择排序

相关 JavaScript实现表格排序

相关 JavaScript实现排序算法