-
归并排序、堆排序等排序方法的思想概述
2019-02-21 21:44:13在这篇文档中将介绍几种...不稳定:如果a原本在b的前面,而a=b,排序之后 a 可能会出现在 b 的后面。 时间复杂度:对排序数据的总的操作次数。反映当n变化时,操作次数呈现什么规律。 空间复杂度:是指算法在计...在这篇文档中将介绍几种排序法,冒泡排序和简单选择排序已经在前面博客中提过,在此不再赘述。
排序算法分类:
以下是几种排序法的比较:
稳定:如果a原本在b前面,而a=b,排序之后a仍然在b的前面。
不稳定:如果a原本在b的前面,而a=b,排序之后 a 可能会出现在 b 的后面。
时间复杂度:对排序数据的总的操作次数。反映当n变化时,操作次数呈现什么规律。
空间复杂度:是指算法在计算机内执行时所需存储空间的度量,它也是数据规模n的函数。
八种排序法对比:
序列长度较短时 序列长度较长时
选择排序法 快速排序法
插入排序法 堆排序法
冒泡排序法 归并排序法
1.堆排序法(Heapsort)堆排序的基本思想是:将待排序序列构造成一个大顶堆,此时,整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换,此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆,这样会得到n个元素的次小值。如此反复执行,便能得到一个有序序列了
var len; // 因为声明的多个函数都需要数据长度,所以把len设置成为全局变量 function buildMaxHeap(arr) { // 建立大顶堆 len = arr.length; for (var i = Math.floor(len/2); i >= 0; i--) { heapify(arr, i); } } function heapify(arr, i) { // 堆调整 var left = 2 * i + 1, right = 2 * i + 2, largest = i; if (left < len && arr[left] > arr[largest]) { largest = left; } if (right < len && arr[right] > arr[largest]) { largest = right; } if (largest != i) { swap(arr, i, largest); heapify(arr, largest); } } function swap(arr, i, j) { var temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } function heapSort(arr) { buildMaxHeap(arr); for (var i = arr.length - 1; i > 0; i--) { swap(arr, 0, i); len--; heapify(arr, 0); } return arr; }
2.归并排序是将一组无序数列分组比较再排序的方法。
然后将两组排好序的数列合并排序。
最后结果如下:
归并排序是稳定排序,它也是一种十分高效的排序,能利用完全二叉树特性的排序一般性能都不会太差。java中Arrays.sort()采用了一种名为TimSort的排序算法,就是归并排序的优化版本。从上文的图中可看出,每次合并操作的平均时间复杂度为O(n),而完全二叉树的深度为|log2n|。总的平均时间复杂度为O(nlogn)。而且,归并排序的最好,最坏,平均时间复杂度均为O(nlogn)。
3.插入排序法
插入排序(Insertion-Sort)的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。
一般来说,插入排序都采用in-place在数组上实现。具体算法描述如下:
- 从第一个元素开始,该元素可以认为已经被排序;
- 取出下一个元素,在已经排序的元素序列中从后向前扫描;
- 如果该元素(已排序)大于新元素,将该元素移到下一位置;
- 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置;
- 将新元素插入到该位置后;
- 重复步骤2~5。
function insertionSort(arr) { var len = arr.length; var preIndex, current; for (var i = 1; i < len; i++) { preIndex = i - 1; current = arr[i]; while (preIndex >= 0 && arr[preIndex] > current) { arr[preIndex + 1] = arr[preIndex]; preIndex--; } arr[preIndex + 1] = current; } return arr; }
4.希尔排序:希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止。
-
总结 JS 中数组排序的常见方法:
2020-06-01 13:58:08这篇文章是对于 JS 中数组排序的常见方法的一个总结 : 前置知识 : 排序大的分类可以分为两种:内排序和外排序。在排序过程中,全部记录存放在内存,则称为内排序,如果排序过程中需要使用外... 不稳定:选择排...这篇文章是对于 JS 中 数组排序 的常见方法的一个总结 :
前置知识 :
排序大的分类可以分为两种:内排序 和 外排序。在排序过程中,全部记录存放在内存,则称为内排序,如果排序过程中需要使用外存,则称为外排序。下面讲的排序都是属于内排序。
内排序有可以分为以下几类:
- 插入排序:直接插入排序、二分法插入排序、希尔排序。
- 选择排序:直接选择排序、堆排序。
- 交换排序:冒泡排序、快速排序。
- 归并排序
- 基数排序
稳定性
- 稳定:归并排序、冒泡排序、插入排序,基数排序。
- 不稳定:选择排序、快速排序、希尔排序、堆排序。
时间复杂度
最基础的四个算法:冒泡、选择、插入、快排 中,快排的 时间复杂度 最小 O(n*log2n),其他都是O(n2)。
排序在 JS 中 :(基础的四个算法:冒泡、选择、插入、快排)
- sort 方法 (a-b正向 b-a 反向)
内部原理:冒泡排序。
JavaScript
中数组的sort()
方法主要用于对数组的元素进行排序。其中,sort()
方法有一个可选参数。但是,此参数必须是函数。 数组在调用sort()
方法时,如果没有传参将按字母顺序(字符编码顺序)对数组中的元素进行排序,如果想按照其他标准进行排序,就需要进行传一个参数且为函数,该函数要比较两个值,并且会返回一个用于说明这两个值的相对顺序的数字。let arr=[3,1,5,8,28] //正向 a-b var arr1=arr.sort(function (a,b) { return a-b; }) console.log(arr1) //[1,3,5,8,28]; //反向 b-a var arr2=arr.sort(function (a,b) { return b-a; }) console.log(arr2) //[28,8,5,3,1]
- 冒泡排序
比较相邻的元素。如果第一个比第二个大,就交换他们两个。对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大的数。针对所有的元素重复以上的步骤,除了最后一个。
function sortArr(arr){ for(let i=0; i<arr.length; i++){ //arr.length-i 保证每次比较都会少比较一位(因为最大的一位已经找出,放在了最后) for(let j=0; j<arr.length-i; j++){ if(arr[j] > arr[j+1]){ let temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; } } } }
- 快速排序 (一拆为二)
首先任意选取一个数据(通常选用数组的第一个数)作为关键数据,然后将所有比它小的数都放到它前面,所有比它大的数都放到它后面,然后对左右部分递归。
function quickSort(arr){ //如果数组长度小于等于1,则返回数组本身 if(arr.length<=1){ return arr; } //定义中间值的索引 var index = Math.floor(arr.length/2); //取到中间值 var center = arr.splice(index,1); //定义左右部分数组 var left = []; var right = []; for(var i=0;i<arr.length;i++){ //如果元素比中间值小,那么放在左边,否则放右边 if(arr[i]<center){ left.push(arr[i]); }else{ right.push(arr[i]); } } return quickSort(left).concat(center,quickSort(right)); }
- 选择排序
每一趟从待排序的数据元素中选出最小(或最大)的一个元素,顺序放在已排好序的数列的最后,直到全部待排序的数据元素排完。
function selectSort(arr){ for(var i=0;i<arr.length;i++){ //设置当前范围最小值和索引 var min = arr[i]; var minIndex = i; //在该范围选出最小值 for(var j=i+1;j<arr.length;j++){ if(min>arr[j]){ min = arr[j]; minIndex = j; } } //将最小值插入 arr.splice(i,0,min); //将原来位置的最小值删除 arr.splice(minIndex+1,1); } }
- 插入排序
假设第 0 元素是有序序列,第 1 元素之后是无序的序列。从第 1 元素开始依次将无序序列的元素插入到有序序列中。
function insertSort(arr){ //假设第0元素是有序序列,第1元素之后是无序的序列。从第1元素开始依次将无序序列的元素插入到有序序列中 for(var i=1; i<arr.length;i++){ if(arr[i]<arr[i-1]){ //取出无序序列中需要插入的第i个元素 var temp = arr[i]; //定义有序中的最后一个位置 var j = i-1; arr[i] = arr[j]; //比较大小,找到插入的位置 while(j>=0&&temp<arr[j]){ arr[j+1] = arr[j]; j--; }; //插入 arr[j+1] = temp; } } }
这里只是简单的总结了下自己常用的几种,如果想了解更多,请参考下方链接:
https://blog.csdn.net/weixin_41725746/article/details/93080926
-
堆排序的基本原理和实现方法(Java)
2019-10-27 12:21:09堆排序是利用堆这种数据结构而设计的一种排序算法,堆排序是一种选择排序,它的最坏,最好,平均时间复杂度均为O(nlogn),它也是不稳定排序。 堆是具有以下性质的完全二叉树:每个结点的值都大于或等于其左右孩子...堆排序的基本原理:
堆排序是利用堆这种数据结构而设计的一种排序算法,堆排序是一种选择排序,它的最坏,最好,平均时间复杂度均为O(nlogn),它也是不稳定排序。
堆是具有以下性质的完全二叉树:每个结点的值都大于或等于其左右孩子结点的值,称为大顶堆, 注意 : 没有要求结点的左孩子的值和右孩子的值的大小关系。
每个结点的值都小于或等于其左右孩子结点的值,称为小顶堆
大顶堆举例说明:
我们对堆中的结点按层进行编号,映射到数组中就是下面这个样子:
堆排序的算法分析:
①、将待排序序列构造成一个大顶堆
②、此时,整个序列的最大值就是堆顶的根节点。
③、将其与末尾元素进行交换,此时末尾就为最大值。
④、然后将剩余n-1个元素重新构造成一个堆,这样会得到n个元素的次小值。如此反复执行,便能得到一个有序序列了。
(可以看到在构建大顶堆的过程中,元素的个数逐渐减少,最后就得到一个有序序列了)堆排序算法图解:
步骤一 构造初始堆。将给定无序序列构造成一个大顶堆(一般升序采用大顶堆,降序采用小顶堆)。
a.假设给定无序序列结构如下
2.此时我们从最后一个非叶子结点开始(叶结点自然不用调整,第一个非叶子结点 arr.length/2-1=5/2-1=1,也就是下面的6结点),从左至右,从下至上进行调整。
4.找到第二个非叶节点4,由于[4,9,8]中9元素最大,4和9交换。
这时,交换导致了子根[4,5,6]结构混乱,继续调整,[4,5,6]中6最大,交换4和6。
此时,我们就将一个无需序列构造成了一个大顶堆。步骤二 将堆顶元素与末尾元素进行交换,使末尾元素最大。然后继续调整堆,再将堆顶元素与末尾元素交换,得到第二大元素。如此反复进行交换、重建、交换。
a.将堆顶元素9和末尾元素4进行交换
b.重新调整结构,使其继续满足堆定义
c.再将堆顶元素8与末尾元素5进行交换,得到第二大元素8.
后续过程,继续进行调整,交换,如此反复进行,最终使得整个序列有序
再简单总结下堆排序的基本思路:a.将无需序列构建成一个堆,根据升序降序需求选择大顶堆或小顶堆;
b.将堆顶元素与末尾元素交换,将最大元素"沉"到数组末端;
c.重新调整结构,使其满足堆定义,然后继续交换堆顶元素与当前末尾元素,反复执行调整+交换步骤,直到整个序列有序。
图片转载自详细代码:
package Tree; import java.util.Arrays; /** * @ClassName: HeapSort * @Description: 对数组进行升序排序 * @author Golven * @date 2019年10月27日 * */ public class HeapSort { public static void main(String[] args) { int[] arr = { 4, 6, 8, 5, 9 }; heapSort(arr); } public static void heapSort(int[] arr) { int temp =0; System.out.println("堆排序:"); for(int i = arr.length/2-1;i>=0;i--) { adjustHeap(arr, i, arr.length); } for(int j = arr.length-1;j>0;j--) { temp = arr[j]; arr[j] = arr[0]; arr[0] = temp; //再从0开始调整,相当于将余下的数再次进行堆排序,顶上元素最大 adjustHeap(arr, 0, j); } System.out.println(Arrays.toString(arr)); } /** * * @Title: adjustHeap * @Description: 完成将以i对应的节点的非叶子节点的树调整为大顶堆 * @param @param i 表示非叶子节点在数组中的索引 * @param @param arr 待调整的数组 * @param @param length 对多少个元素进行调整,length时逐渐减小的 * @return void 返回类型 * 举例:int arr[]={ 4, 6, 8, 5, 9}==>i=1==>adjustHeap==>{4,9,8,5,6}==> 再次调用adjustHeap==>i=0==>{9,6,8,5,4} */ public static void adjustHeap(int[] arr,int i,int length) { //定义辅助变量将arr[i]的值赋给它 int temp =arr[i]; //k=2*i+1表示从i的左节点开始调整 for(int k = 2*i+1;k<length;k=2*k+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; } } }
-
冒泡排序和选择排序算法的实现
2018-12-05 10:53:03这是一种不稳定的排序方法。比冒泡排序快。 二 冒泡排序: 冒泡排序重复访问要排序的元素,依次比较两个相邻的元素。如果前一个元素大于后一个,或者小于,就把它们交换过来。重复的进行直到没有相邻元素需要交换...一 选择排序:
选择排序的工作原理是从 待排序的元素中选出最小或者最大的一个元素,存放在序列的起始位置,直到全部待排序的元素排完。这是一种不稳定的排序方法。比冒泡排序快。
二 冒泡排序:
冒泡排序重复访问要排序的元素,依次比较两个相邻的元素。如果前一个元素大于后一个,或者小于,就把它们交换过来。重复的进行直到没有相邻元素需要交换,说明冒泡排序已经完成。时间复杂度为o(n2)。
以下是代码实现(c++):
#include <iostream> using namespace std; //选择排序 void selectSort(int (&a)[10]) { for (int i = 0; i < 10; i++) { //从下一个数开始 for (int j = i + 1; j < 10; j++) { //交换 if (a[i]>a[j]) { int temp = a[i]; a[i] = a[j]; a[j] = temp; } } } } //冒泡排序 void bubbleSort(int(&a)[10]) { for (int i = 0; i < 10;i++) { for (int j = 0; j < 10 - i - 1;j++) { //交换 if (a[j]>a[j + 1]) { int temp = a[j]; a[j] = a[j+1]; a[j+1] = temp; } } } } //主函数 int main() { int array[10] = {10,8,6,19,3,41,4,7,98,1}; cout << "排序前:"; for (int i = 0; i < sizeof(array) / sizeof(array[0]); i++) { cout << array[i] << " "; } //selectSort(array); bubbleSort(array); cout << "排序后:"; for (int i = 0; i < sizeof(array) / sizeof(array[0]); i++) { cout << array[i] << " "; } return 0; }
-
常见的八大排序算法
2020-11-09 19:58:44概念 我们平常说的排序,通常都是按照从小到大的顺序,而且指的是原地排序(in place sort)。 排序又分内部排序和外部...比较快速判断是否稳定的方法:如果在排序过程中没有发生跳跃式交换(隔几个数地去交换),就是稳 -
排序的选择问题
2017-08-17 12:17:32希望用最快的速度从一个无序数组中挑选出其中前十个最大的元素,在以下的排序方法中(B) 快速排序 堆排序 归并排序 基数排序题目不在乎空间只要速度,没记错应该是基数排序最快且稳定。 如果结合实际(顾及空间... -
插入排序——希尔排序
2017-04-22 15:08:26希尔排序是不稳定的排序算法。 希尔排序是基于插入排序的以下两点性质而提出改进方法的: 插入排序在对几乎已经排好序的数据操作时,效率高,即可以达到线性排序的效率但插入排序一般来说是低效的,因为插入... -
排序算法总结
2018-05-17 08:32:09从以下几个方面来比较...不稳定排序方法: 选择排序、谢尔排序、快速排序、堆积排序是不稳定排序算法。算法复杂度比较:各种内排序算法的时间、空间复杂度排序方法平均时间最坏情况辅助空间插入排序O(n*n)O(n*n)O(... -
排序算法之选择排序
2015-01-16 19:20:59不稳定的排序方法。 算法: 排序算法即解决以下问题的算法: 输入:n个数的序列。 输出:原序列的一个重排;,使得a1* 排序算法有很多,包括插入排序,冒泡排序,堆排序,归并排序,选择排序,计数... -
C语言排序之希尔排序篇
2017-08-06 20:24:37希尔排序是不稳定的排序算法。 希尔排序是基于插入排序的以下两点性质而提出改进方法的: · 插入排序在对几乎已经排好序的数据操作时,效率高,即可以达到线性排序的效率 · 但插入排序一般来说是低效的,因为... -
八大排序学习之五归并排序
2016-11-02 09:17:19同时也是分治法的典型应用,先把问题细分,再整合,听说Windows系统上的文件排序也是采用了归并排序的方法,归并排序是一种稳定的排序方法,因为相同元素的前后顺序在排序后跟原来不变,原因是相同的不做操作。... -
选择排序
2017-03-25 17:07:39选择排序 选择排序(Selection sort... 选择排序是不稳定的排序方法(比如序列[5, 5, 3]第一次就将第一个[5]与[3]交换,导致第一个5挪动到第二个5后面)。 基本选择排序 排序算法即解决以下问题的算法: -
排序算法---希尔排序
2018-09-20 20:02:43希尔排序是不稳定的排序算法。 希尔排序是基于插入排序的以下两点性质而提出改进方法的: 插入排序在对几乎已经排好序的数据操作时,效率高,即可以达到线性排序的效率 但插入排序一般来说是低效的,因为插入排序... -
排序算法小结
2015-04-27 10:21:06从以下几个方面来比较排序算法: 1. 算法的时间和空间复杂度 2. 排序的稳定性 ...不稳定排序方法: 选择排序、谢尔排序、快速排序、堆积排序是不稳定排序算法。 算法复杂度比较: -
【排序算法】希尔排序算法原理
2020-06-17 00:16:57希尔排序(递减增量排序)希尔排序是基于插入排序的以下两点性质而提出改进方法的:原理算法描述伪代码代码Donald Shell增量其他增量希尔排序是不稳定的排序算法。复杂度 希尔排序是基于插入排序的以下两点性质而... -
基数排序
2016-09-17 19:18:36基数排序是一种与之前几种排序不同的排序方法,之前的排序是基于关键字排序算法。基数排序属于分配式排序,而且基数排序是稳定排序。以下是基数排序的步骤:假设在一个数组为例,数据中的数据项均小于1000(位数最多... -
希尔排序
2017-09-14 11:23:58希尔排序是基于插入排序的以下两点性质而提出改进方法的: 1)插入排序在对几乎已经排好序的数据操作时,效率高,即可以达到线性排序的效率; 2)插入排序是低效的, 因为插入排序每次只能将数据移动一位。(2)... -
【排序算法总结】内排序算法原理
2020-06-17 00:19:18代码~原理伪代码代码稳定性复杂度算法描述:二分查找:代码希尔排序是基于插入排序的以下两点性质而提出改进方法的:原理算法描述伪代码代码Donald Shell增量其他增量希尔排序是不稳定的排序算法。复杂度堆的概念... -
内排序算法小结
2014-08-31 16:06:05从以下几个方面来比较排序算法: 1. 算法的时间和空间复杂度 2. 排序的稳定性 ...不稳定排序方法: 选择排序、谢尔排序、快速排序、堆积排序是不稳定排序算法。 算法复杂度比较: -
软考系列——排序算法盘点
2015-10-09 18:58:33所谓排序,就是按照关键字递增或递减次序排列起来。本文将会从四个方面来分析各个排序方法:逻辑、时间复杂度、稳定性...不稳定的:若具有相同关键字的记录之间的相对次序发生变化,则称其为不稳定的。 下面是一张 -
插入排序-----希尔排序
2016-12-03 21:32:00希尔排序是不稳定的排序算法。 希尔排序是基于插入排序的以下两点性质而提出改进方法的: 插入排序在对几乎已经排好序的数据操作时,效率高,即可以达到线性排序的效率 但插入排序一般来说是低效的,因为插入... -
[学习笔记]排序算法之选择排序
2016-04-16 13:37:30不稳定的排序方法。 算法: 排序算法即解决以下问题的算法: 输入:n个数的序列。 输出:原序列的一个重排;,使得a1* 排序算法有很多,包括插入排序,冒泡排序,堆排序,归并排序,选择排序,计数... -
c语言产生随机数并排序_选择排序展示(java)
2020-12-26 10:50:34(以下为百度)选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理是:第一次从待排序的数据元素中选出最小(或最大)的一个...选择排序是不稳定的排序方法。博客地址:http://www.coderframe.com/Info/in... -
Java算法排序之--选择排序
2013-02-20 10:28:03选择排序是不稳定的排序方法。 排序简介 排序算法即解决以下问题的算法: 输入:n个数的序列。 输出:原序列的一个重排;,使得a1* 排序算法有很多,包括插入排序,冒泡排序,堆排序,归并排序,选择... -
C:排序【1】---选择排序
2019-03-12 23:26:47时间按复杂度为O(n^2),空间复杂度为O(1),是一种不稳定的排序方法。 选择排序的规则(来自百度):每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,然后,再从剩余未排序元素...
-
百瓦级全光纤线偏振激光振荡器
-
数据库设计StepbyStep
-
一个简单的PHP在线书签系统
-
axios学习优化及使用
-
scrapy_pipelines.py
-
linux中安装nacos,seata并集成到nacos中
-
自动化测试Python3+Selenium3+Unittest
-
那些技术文档
-
CSRFTester:一款CSRF漏洞的安全测试工具
-
【Python-随到随学】FLask第二周
-
可用性测试方法:卡片分类法
-
Web前端开发笔记(1)
-
nlp3
-
MaxScale 实现 MySQL 读写分离与负载均衡
-
两个栈实现队列
-
50个优秀的名片设计作品欣赏
-
前端开发中常用图片格式
-
产品团队管理经验一枚
-
程序员必修基础套餐课
-
PHP深入理解-PHP架构布局