精华内容
下载资源
问答
  • 在这篇文档中将介绍几种...不稳定:如果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 中数组排序的常见方法的一个总结 : 前置知识 : 排序分类可以分为两种:内排序和外排序。在排序过程中,全部记录存放在内存,则称为内排序,如果排序过程中需要使用外... 不稳定:选择排...

    这篇文章是对于 JS 中 数组排序 的常见方法的一个总结 :


    前置知识 :

    排序大的分类可以分为两种:内排序 和  外排序。在排序过程中,全部记录存放在内存,则称为内排序,如果排序过程中需要使用外存,则称为外排序。下面讲的排序都是属于内排序。

    内排序有可以分为以下几类:

    1. 插入排序:直接插入排序、二分法插入排序、希尔排序。
    2. 选择排序:直接选择排序、堆排序。
    3. 交换排序:冒泡排序快速排序
    4. 归并排序
    5. 基数排序

    稳定性

    1. 稳定:归并排序、冒泡排序、插入排序,基数排序。
    2. 不稳定:选择排序、快速排序、希尔排序、堆排序。

    时间复杂度

    最基础的四个算法:冒泡、选择、插入、快排 中,快排的 时间复杂度 最小 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

     

    展开全文
  • 排序是利用堆这种数据结构而设计一种排序算法,堆排序是一种选择排序,它最坏,最好,平均时间复杂度均为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;
    		}
    	}
    }
    
    
    展开全文
  • 这是一种不稳定的排序方法。比冒泡排序快。 二 冒泡排序: 冒泡排序重复访问要排序的元素,依次比较两个相邻的元素。如果前一个元素大于后一个,或者小于,就把它们交换过来。重复的进行直到没有相邻元素需要交换...

    一 选择排序:

      选择排序的工作原理是从 待排序的元素中选出最小或者最大的一个元素,存放在序列的起始位置,直到全部待排序的元素排完。这是一种不稳定的排序方法。比冒泡排序快。

    二 冒泡排序:

      冒泡排序重复访问要排序的元素,依次比较两个相邻的元素。如果前一个元素大于后一个,或者小于,就把它们交换过来。重复的进行直到没有相邻元素需要交换,说明冒泡排序已经完成。时间复杂度为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) 快速排序 堆排序 归并排序 基数排序题目在乎空间只要速度,没记错应该是基数排序最快且稳定。 如果结合实际(顾及空间...
  • 希尔排序是不稳定的排序算法。  希尔排序是基于插入排序的以下两点性质而提出改进方法的: 插入排序在对几乎已经排好序的数据操作时,效率高,即可以达到线性排序的效率但插入排序一般来说是低效的,因为插入...
  • 排序算法总结

    2018-05-17 08:32:09
    以下几个方面来比较...不稳定排序方法: 选择排序、谢尔排序、快速排序、堆积排序是不稳定排序算法。算法复杂度比较:各种内排序算法时间、空间复杂度排序方法平均时间最坏情况辅助空间插入排序O(n*n)O(n*n)O(...
  • 排序算法之选择排序

    2015-01-16 19:20:59
    不稳定的排序方法。 算法: 排序算法即解决以下问题的算法: 输入:n个数的序列。 输出:原序列的一个重排;,使得a1* 排序算法有很多,包括插入排序,冒泡排序,堆排序,归并排序,选择排序,计数...
  • 希尔排序是不稳定的排序算法。  希尔排序是基于插入排序的以下两点性质而提出改进方法的: · 插入排序在对几乎已经排好序的数据操作时,效率高,即可以达到线性排序的效率 · 但插入排序一般来说是低效的,因为...
  • 同时也是分治法的典型应用,先把问题细分,再整合,听说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. 排序稳定性 ...不稳定排序方法: 选择排序、谢尔排序、快速排序、堆积排序是不稳定排序算法。 算法复杂度比较:  
  • 希尔排序(递减增量排序)希尔排序是基于插入排序的以下两点性质而提出改进方法的:原理算法描述伪代码代码Donald Shell增量其他增量希尔排序是不稳定的排序算法。复杂度 希尔排序是基于插入排序的以下两点性质而...
  • 基数排序

    2016-09-17 19:18:36
    基数排序是一种与之前几种排序不同的排序方法,之前的排序是基于关键字排序算法。基数排序属于分配式排序,而且基数排序是稳定排序。以下是基数排序的步骤:假设在一个数组为例,数据中的数据项均小于1000(位数最多...
  • 希尔排序

    千次阅读 2017-09-14 11:23:58
    希尔排序是基于插入排序的以下两点性质而提出改进方法的: 1)插入排序在对几乎已经排好序数据操作时,效率高,即可以达到线性排序的效率; 2)插入排序是低效, 因为插入排序每次只能将数据移动一位。(2)...
  • 代码~原理伪代码代码稳定性复杂度算法描述:二分查找:代码希尔排序是基于插入排序的以下两点性质而提出改进方法的:原理算法描述伪代码代码Donald Shell增量其他增量希尔排序是不稳定的排序算法。复杂度堆的概念...
  • 排序算法小结

    2014-08-31 16:06:05
    以下几个方面来比较排序算法: 1. 算法时间和空间复杂度 2. 排序稳定性 ...不稳定排序方法: 选择排序、谢尔排序、快速排序、堆积排序是不稳定排序算法。 算法复杂度比较:
  • 软考系列——排序算法盘点

    千次阅读 热门讨论 2015-10-09 18:58:33
    所谓排序,就是按照关键字递增或递减次序排列起来。本文将会从四个方面来分析各个排序方法:逻辑、时间复杂度、稳定性...不稳定的:若具有相同关键字的记录之间的相对次序发生变化,则称其为不稳定的。 下面是一张
  • 希尔排序是不稳定的排序算法。 希尔排序是基于插入排序的以下两点性质而提出改进方法的: 插入排序在对几乎已经排好序的数据操作时,效率高,即可以达到线性排序的效率 但插入排序一般来说是低效的,因为插入...
  • 不稳定的排序方法。 算法: 排序算法即解决以下问题的算法: 输入:n个数的序列。 输出:原序列的一个重排;,使得a1* 排序算法有很多,包括插入排序,冒泡排序,堆排序,归并排序,选择排序,计数...
  • (以下为百度)选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理是:第一次从待排序的数据元素中选出最小(或最大)的一个...选择排序是不稳定的排序方法。博客地址:http://www.coderframe.com/Info/in...
  •  选择排序是不稳定的排序方法。 排序简介 排序算法即解决以下问题的算法: 输入:n个数的序列。 输出:原序列的一个重排;,使得a1* 排序算法有很多,包括插入排序,冒泡排序,堆排序,归并排序,选择...
  • 时间按复杂度为O(n^2),空间复杂度为O(1),是一种不稳定的排序方法。 选择排序的规则(来自百度):每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,然后,再从剩余未排序元素...

空空如也

空空如也

1 2 3 4 5 6
收藏数 120
精华内容 48
关键字:

以下不稳定的排序方法是