精华内容
下载资源
问答
  • 排序算法分析

    2016-09-24 16:22:17
    排序算法分析 很久以来,自己由于习惯于依赖各种现成的库,对于各种排序算法生疏久已,甚至对于选择、冒泡、插入等排序的区别都有些模糊不清了。我们庆幸于生在这个年代,安心享受着前辈大师们的智慧结晶,可以说是...

    据说在计算机发明后的很长一段时间内,30%以上的算力都是用来做排序这一件事情。

    很久以来,自己由于习惯于依赖各种现成的库,对于各种排序算法生疏久已,甚至对于选择、冒泡、插入等排序的区别都有些模糊不清了。我们庆幸于生在这个年代,安心享受着前辈大师们的智慧结晶,可以说是站在巨人的肩膀上眺望远方了。此篇博客用来总结各种排序算法,强化对算法重要性的认识,并且向各位对排序算法做出改进的大师们致敬了。


    一、选择排序

    ·算法描述

    首先,找到数组中最小的那个元素,使它和数组中的第一个元素交换位置;再次,在剩下的元素中继续找最小的那个,使他和数组中的第二个元素交换位置。如此往复,直到整个数组排序。

    ·算法特点

    1、运行时间和输入无关

    一个有序的数组和一个元素随机排列的数组,排序的时间复杂度竟然一样。

    2、数据移动是最少的

    数据交换只在最内层循环之外的地方发生。交换的次数和数组的大小是成线性关系的,我们研究的其他算法都不具备这个特征

    ·时间复杂度分析

    对于长度为N的数组,选择排序需要N2/2次比较和N次交换。总的来说时间复杂度为平方级别O(N2)

    ·空间复杂度分析

    基本不占用多余的内存空间,复杂度为O(1)。

    ·适用情景

    任何刚学编程的菜鸟的第一思路基本就是这个了:)

    ·示例代码

        //选择排序
    void selectSort(int *a,int size)
    {
        for(int i = 0; i < size; ++i)
        {
            //最小值索引
            int minIndex = i;
            for(int j = i+1; j < size; ++j)
            {
                //查找最小值的索引
                if(*(a+j) < *(a+minIndex))
                {
                    minIndex = j;
                }
            }
            //交换数组中两个位置的值
            if(minIndex != i)
            {
                int tmp = *(a+i);
                *(a+i) = *(a+minIndex);
                *(a+minIndex) = tmp;
            }
        }
    }

    二、冒泡排序

    三、插入排序

    ·算法描述

    我们平时打扑克摸牌时,每摸到一张牌,就要插入到手中已排好序的所有牌中,插入排序的算法跟这个很相似。数组左侧都是已拍好序的元素,读取右侧的每一个元素,都要插入到左侧的有序元素中去,左侧的有序元素,会根据新插入元素的位置,做部分整体的向右移位,当所有元素都已插入完毕时,排序结束。

    ·算法特点

    ·时间复杂度

    ·空间复杂度

    ·适用情景

    ·示例代码

    //插入排序
    void insertsort(int *a,int size)
    {
        for(int i = 1; i < size; ++i)
        {
            for(int j = i; j > 0; j--)
            {
                if(*(a+j) < *(a+j-1))
                {
                    int tmp = *(a+j);
                    *(a+j) = *(a+j-1);
                    *(a+j-1) = tmp;
                }
                else
                {
                    break;
                }
    
            }
        }
    }
    

    四、归并排序

    五、快速排序

    六、希尔排序

    展开全文
  • 排序算法分析比较.pdf

    2020-08-13 10:57:14
    排序算法分析比较 王晓宇 北京邮电大学信息与通信工程学院北京(100876) 摘 要所谓排序就是使一串记录按照其中的某个或某些关键字的大小递增或递减的 排列起来的操作排序是程序设计中非常重要的内容其算法种类繁多...
  • 排序算法分析1--冒泡排序、插入排序、选择排序0.综述1.冒泡排序(Bubble sort)算法分析1.1冒泡排序算法原理1.2冒泡排序代码实现1.3冒泡排序算法分析2.插入排序(Insertion sort)算法分析2.1插入排序算法原理2.2插入...

    0.综述

    所谓排序,就是将原本无序的序列重新排列成有序序列的过程。排序算法对任何一个程序员来说都是一项基本功,在实际的项目中我们也经常需要使用排序。排序算法的选择和使用不仅要针对实际数据的特点,有时候排序的稳定性也必须考虑。这样可以提高程序的运行效率,让开发工作事半功倍。

    学习排序算法不能仅仅停留在了解算法原理和使用代码实现这两步,我们应该在此基础上学会去分析和评价一个算法。我们可以从以下几各方面去衡量一个排序算法:

    • 对于排序算法执行效率的分析,包括最好、最坏、平均情况下的时间复杂度,算法运行过程中数据比较和交换的次数等。
    • 对于排序算法的内存消耗分析。算法的内存消耗通过空间复杂度来衡量。
    • 排序算法的稳定性。所谓稳定性,就是待排序的序列中的值相同的元素经过排序算法处理后是否保持原先的位置关系,若保持,则称这个排序算法为稳定的排序算法,反之则称为不稳定的排序算法。

    1.冒泡排序(Bubble sort)

    1.1冒泡排序算法原理

    冒泡排序算法只操作相邻的两个元素,每次冒泡操作都会比较相邻的两个元素,看着两个元素的大小是否满足要求,要是不满足就交换它们的位置。每进行一次冒泡就会至少会有一个元素被放到正确的位置上,这样重复n次就可以完成n个元素的排序工作。

    例如对于这样一组数据:4,5,6,3,2,1,需要进行从小到大的排序。
    进行第一次冒泡操作的时候

    • 首先比较4和5,满足条件 此时元素序列为 4,5,6,3,2,1;
    • 然后比较5和6,满足条件 此时元素序列为 4,5,6,3,2,1;
    • 比较6和3,6比3大,所以交换6和3 此时元素序列为 4,5,3,6,2,1;
    • 比较6和2,6比2大,所以交换6和2 此时元素序列为 4,5,3,2,6,1;
    • 比较6和1,6比1大,所以交换6和1 此时元素序列为 4,5,3,2,1,6;

    这样经过一次冒泡后元素6就被移动到了正确的位置。由于冒泡过程中元素的移动就像气泡网上冒一样,这也是冒泡算法名称的由来。可以看得出,要想对着6个数据进行正确的排序,需要进行6次冒泡操作。

    下面是针对上面的数据每一次冒泡后得到的序列状态:

    • 初始状态:4,5,6,3,2,1
    • 第一次冒泡后:4,5,3,2,1,6
    • 第二次冒泡后:4,3,2,1,5,6
    • 第三次冒泡后:3,2,1,4,5,6
    • 第四次冒泡后:2,1,3,4,5,6
    • 第五次冒泡后:1,2,3,4,5,6
    • 第六次冒泡后:1,2,3,4,5,6

    其中加粗的是每一次冒泡操作往上冒,也就是到达正确位置的元素。

    1.2冒泡排序算法优化与代码实现

    针对上面一节的内容,我们理解了冒泡排序的基本原理与操作步骤。上述的算法是可以优化的,例如针对这样的一组数据:3,4,5,1,2,6。这样的六个数是不是也需要进行六次冒泡操作呢?我们来走一遍冒泡操作看看。

    • 初始状态:3,4,5,1,2,6
    • 第一次冒泡:3,4,1,2,5,6
    • 第二次冒泡:3,1,2,4,5,6
    • 第三次冒泡:1,2,3,4,5,6
    • 第四次冒泡:1,2,3,4,5,6
    • 第五次冒泡:1,2,3,4,5,6

    可以看得出来进行到第三次冒泡操作的时候整个序列就已经是有序的了,所以第四次和四五次都没有进行数据交换。有上述分析可知,此处的六个数据只需进行四次冒泡操作就可以了。

    实际上当没有数据交换的时候,序列就是完全有序的了,此时我们也可以认为排序已经完成,不用在继续执行后面的冒泡操作了。

    最终冒泡排序C语言代码如下:

    //a是数组,n是数组中元素的个数
    void bubble_sort(int a[],int n)
    {
    	if(n<=1)
    		return;
    	for(int i=0;i<n;++i)
    	{
    		int flag = 0;//设定是否提前退出冒泡排序操作的flag
    		for(int j=0;j<n-1;++j)
    		{
    			if(a[j]>a[j+1])
    			{
    				int temp = a[j];
    				a[j] = a[j+1];
    				a[j+1] = temp;
    				flag = 1; //flag = 1表示有数据交换
    			}					
    		}
    		if(!flag)
    			break;
    	}
    }
    

    1.3冒泡排序算法分析

    • 由上述分析可以看出,冒泡排序只涉及相邻两个元素的交换操作,它所使用的临时空间是常量级的,所以冒泡排序算法的空间复杂度为O(1),因此它也是一个原地算法(所谓原地算法,就特指空间复杂度为O(1)的算法)。
    • 从时间复杂度上看,冒泡排序最好情况是原序列已经有序,这样只需要进行一次冒泡操作即可判断出不需要继续冒泡了,所以最好的情况下时间复杂度为O(n)。而最坏的情况下需要进行n次冒泡操作,每次冒泡又要进行n次比较操作,所以最坏情况复杂度为O(n²)。于是总的时间复杂度为O(n²)。
    • 由于可以在程序中设定当两个值相等时不交换两个元素的位置,所以冒泡排序是稳定的排序算法。

    2.插入排序(Insertion sort)

    2.1插入排序算法原理

    首先思考这样一个问题,如何在一个有序序列中插入一个新元素?假设有需要在这样一个有序序列中插入6:1,7,8,15。很容易想到只需要遍历当前这个有序序列,然后找到应该插入新元素的合适位置插入该元素即可。这是一个动态的插入过程,需要搬移插入位置之后的元素,插入过程如下图:
    在这里插入图片描述

    由上面的思想就可以引出这部分的主题:插入排序算法。插入排序的算法思想就是:将数组中的数据分为已排序区间和未排序区间两个区间。一开始的时候已排序区间只有一个元素,一般就是数组中的第一个元素。则剩下的数组中的其他元素所组成区间就是未排序区间。插入算法每次选取一个未排序区间内的元素按照上面插入6的方法插入到前面的已排序区间中。一直重复插入操作至未排序区间中的元素个数为0算法结束。

    2.2直接插入排序代码实现

    与上面的分析不难写出插入排序代码:

    void inseration_sort(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;
    	}
    }
    

    2.3直接插入排序算法分析

    • 由上述分析可知,插入排序空间复杂度为O(1),即插入排序算法是一个原地排序算法。
    • 在插入排序中我们可以设定对于值相同的两个元素,将后出现的元素插入到前面出现元素的后面,这样就可以保证排序后两个元素的位置关系不变,所以插入排序是一个稳定的排序算法。
    • 在最好的情况下,也就是数组已经有序的时候,比较次数为n-1,所以时间复杂度为O(n)。在最坏情况下,数组刚好严格逆序的时候,比较次数和移动次数都是n(n-1)/2,时间复杂度为O(n2)O(n^2)所以最终得出,插入排序算法的时间复杂度为O(n²)O(n²)

    2.4折半插入排序算法

    折半插入排序算法的是对直接插入排序算法的优化,它们的区别是查找插入位置的方法不同,折半插入采用折半查找法来查找插入位置。我们知道,对于折半查找法来说,它的一个基本要求是待查找的序列已经有序,而先前直接插入法中的有序区间内的元素显然符合这样的条件,因此针对于直接插入法中的遍历查找待插入位置的方法,我们可以用折半法来进行优化,折半查找法可以在这个有序序列中查找插入位置。

    折半插入代码实现:

    void binary_inseration_sort(int a[], int n)
    {
    	for (int i = 1; i<n; ++i)
    	{
    		int tmp = a[i];
    		//查找区间 0~i-1
    		int low = 0, high = i - 1;
    		int mid;
    		while (low <= high)
    		{
    			mid = (low + high) / 2;
    			if (a[mid]>tmp)
    			{
    				high = mid-1;
    			}
    			else 
    			{
    				low = mid+1;
    			}
    		}
    
    		int j;
    		for (j = i - 1; j >= low; --j)
    		{
    			a[j + 1] = a[j];
    		}
    		a[j + 1] = tmp;
    	}
    }
    

    3.选择排序(Slection sort)

    3.1选择排序算法原理

    选择排序的算法思路有点类似插入排序,它也是分为了已排序区间和未排序区间,并且每次从未排序区间的选取一个元素插入到已排序区间。不同于插入排序的是,选择排序算法每次从未排序区间中找到最小的元素,将其插入到已排序区间的末尾。

    3.2选择排序代码实现

    void slection_sort(int a[],int n)
    {
    	int temp = 0;
    	for(int i=0;i<n-1;++i)
    		for(int j=i+1;j<n;++j)
    		{
    			if(a[i]>a[j])
    			{
    				temp = a[i];
    				a[i]=a[j];
    				a[j]=temp;
    			}
    		}
    }
    

    选择排序算法实现较为简单,但是要注意区别,很多人不仔细看会误认为跟冒泡算法实现代码一样。冒泡排序算法是挨个比较两个相邻元素,而选择插入排序是每次将未排序区间内的最小值提取出来插入到已排序区间的末尾。具体的过程就是挨个比较未排序区间内的元素和已排序区间的末元素,若已排序区间末元素大则替换掉,否则继续比较未排序区间内的下一个元素,直到都比较完。

    例如对于下面的序列,第一次选择的时候挨个比较a[0]与后面的元素,10比6大,所以交换它们,序列就成了6,10,7,8,15。注意接下来比较的不是10和7,而是6和7,6和8,6和15!这是和冒泡排序的不同的地方。
    在这里插入图片描述

    3.3选择排序算法分析

    • 选择排序的空间复杂度为O(1),所以它是一个原地排序算法。
    • 选择排序不是一个稳定算法,因为选择排序每次从未排序区间中找到一个最小值,并且和前面的元素交换位置,这样就破坏了稳定性。
    • 选择排序的时间复杂度为O(n²)。

    4.总结

    上面的三种算法都是O(n²)的,但是相对而言,插入排序又比冒泡排序优秀一些,因为插入排序过程中每次只需要赋值一次,而冒泡排序因为要交换两个数,因此要经过三次赋值,在数据规模比较大的时候就会有明显的性能差异。

    在实际工作中O(n²)的排序算法并不常用,但是插入排序还是挺有用的,因为它在某些情况下的性能还是比较好的。

    展开全文
  • 基于OpenMP排序算法分析与程序设计.ppt
  • 排序算法分析及源代码
  • 排序算法分析2--归并排序和快速排序0.综述1.归并排序原理分析2.归并排序代码实现 0.综述 在前面一节中,我们分析了三种时间复杂度为O(n²)的排序算法–冒泡排序、插入排序、选择排序,由于这三种算法的时间复杂度较...

    0.综述

    在前面一节中,我们分析了三种时间复杂度为O(n²)的排序算法–冒泡排序、插入排序、选择排序,由于这三种算法的时间复杂度较高,因而适用于小规模数据的排序。而今天分析的两种排序算法适用于大规模数据的排序,因为它们的时间复杂度都是O(nlogn),它们分别是归并排序和快速排序

    1.归并排序(MergeSort)原理

    归并排序利用了分而治之的思想,对于一个未排序的数组,归并排序将它从数组中间分为前后两个部分,然后分别对这两个部分进行排序,再将这两个有序的序列合并起来,最终使整个数组是有序的。

    例如对于包含4,3,2,1,8,76,5这8个元素的序列,我们可以先将其分成4,3,2,1和8,76,5这两组序列,再将它们分为4,3/2,1/8,7/6,5这四组,然后在组内分别排序,得到3,4/1,2/7,8/5,6,然后将它们两两合并,得到1,2,3,4/5,6,7,8,在将这两个合并,最终就得到有序数组:1,2,3,4,5,6,7,8。

    整个示意图如下:
    在这里插入图片描述
    分治算法一般用递归来解决,归并排序也是如此。对于递归程序,首先应该弄清楚它的递归边界,也就是终止条件,然后就是它的递归方程。由上面对归并排序的原理分析不难得出,归并排序的递归公式就是:

    q = (p+r)/2
    merge_sort(p,r)=(merge_sort(p,q),merge_sort(q+1,r)
    

    归并排序的递归边界应该就是:

    p>=r //p>=r时不再继续分解
    

    其中merge_sort(p,r)表示给下标p到下标r直接的元素排序。这样就可以转换成分别给p->q和q+1->r两个区间内的元素进行排序的子问题,其中q是p和r之间中间的元素下标,也就是q=(p+r)/2。

    2.归并排序代码实现

    void merge(int*a,p,q,r)
    {
    	int *tmp = (int*)malloc((r - p + 1) * sizeof(int));
    	if(!tmp)
    		perror("malloc failed.")	
    	int i, j, k;
    	for (i = p, j = q + 1, k = 0; i <= q && j <= r;) 
    	{
    		if (a[i] <= a[j])
    			tmp[k++] = a[i++];
    		else
    			tmp[k++] = a[j++];
    	}
    	if (i == q + 1) 
    	{
    		for (; j <= r;)
    			tmp[k++] = a[j++];
    	} 
    	else {
    		for (; i <= q;)
    			tmp[k++] = a[i++];
    	}
    	memcpy(a + p, tmp, (r - p + 1) * sizeof(int));
    	free(tmp);	
    }
    
    void merge_sort(int *a, int p, int r)
    {
    	int q;
    
    	if (p >= r)
    		return;
    
    	q = (p + r) / 2;
    	merge_sort(a, p, q);
    	merge_sort(a, q + 1, r);
    	merge(a, p, q, r);
    }
    
    

    其中merge函数完成的功能是将已经有序的两个序列,也就p->q以及q->r两个序列之间的元素合并到一个序列中。

    3.归并排序算法分析

    • 在归并排序算法中,我们可以设定merge函数中对于值相同的两个元素位置不改变,所以归并排序算法是一个稳定的排序算法。
    • 归并排序算法的时间复杂度为O(nlogn)。
    • 由于归并排序算法的执行过程中,在合并有序数组的时候需要申请额外的内存空间,所以它不是原地排序算法并且它的空间复杂度为O(n)。

    4.快速排序(QuickSort)算法原理

    快速排序一般被简称为快排,它也用了分治的思想。快排的核心思想是若要对乱序数组中的下标p到r之间的元素排序,我们可以选择p到r之间任意的一个元素作为pivot分区点,将p->r这个序列分为两个部分,我们遍历p->r之间的元素,然后将小于pivot的放在pivot左边,将大于pivot的放在pivot右边,将pivot放在中间。

    快排的递推公式如下:

    quick_sort(p,r) = quick_sort(p,q-1)+quick_sort(q+1,r)
    

    递推终止条件就是:

    p>=r
    

    5.快排代码

    void swap(int *a, int *b)
    {
    	int tmp = *a;
    	*a = *b;
    	*b = tmp;
    }
    
    int get_q(int *a, int p, int r)
    {
    	int i, j;
    	i = j = p;
    
    	for (; j < r; ++j)
    	{
    		if (a[j] < a[r]) 
    		{
    			if(i != j)
    			{
    				swap(a + i, a + j);
    			}
    			++i;
    		}
    	}
    	swap(a + i, a + r);
    	return i;
    }
    
    void quick_sort(int *a, int p, int r)
    {
    	int q;
    	if (p >= r)
    		return;
    	q = get_q(a, p, r);
    	quick_sort(a, p, q-1);
    	quick_sort(a, q+1, r);
    }
    

    6.快排分析

    • 快排是一个不稳定的排序算法,但是它是原地的排序算法。
    • 快排的时间复杂度为O(nlogn)。
    展开全文
  • 排序算法分析比较,王晓宇,,所谓排序,就是使一串记录,按照其中的某个或某些关键字的大小,递增或递减的排列起来的操作。排序是程序设计中非常重要的内容,
  • 快速排序算法分析

    2017-04-07 22:56:21
    算法分析: 快速排序的最直接竞争者是堆排序(Heapsort)。堆排序通常比快速排序稍微慢,但是最坏情况的运行时间总是O(n log n)。快速排序是经常比较快,除了introsort变化版本外,仍然有最坏情况性能的机会。如果...

    快速排序
    算法分析:
    快速排序的最直接竞争者是堆排序(Heapsort)。堆排序通常比快速排序稍微慢,但是最坏情况的运行时间总是O(n log n)。快速排序是经常比较快,除了introsort变化版本外,仍然有最坏情况性能的机会。如果事先知道堆排序将会是需要使用的,那么直接地使用堆排序比等待introsort再切换到它还要快。堆排序也拥有重要的特点,仅使用固定额外的空间(堆排序是原地排序),而即使是最佳的快速排序变化版本也需要Θ(log n)的空间。然而,堆排序需要有效率的随机存取才能变成可行。
    快速排序也与归并排序(Mergesort)竞争,这是另外一种递归排序算法,但有坏情况O(n log n)运行时间的优势。不像快速排序或堆排序,归并排序是一个稳定排序,且可以轻易地被采用在链表(linked list)和存储在慢速访问媒体上像是磁盘存储或网络连接存储的非常巨大数列。尽管快速排序可以被重新改写使用在炼串列上,但是它通常会因为无法随机存取而导致差的基准选择。归并排序的主要缺点,是在最佳情况下需要Ω(n)额外的空间。

    时间复杂度:
    从一开始快速排序平均需要花费O(n log n)时间的描述并不明显。但是不难观察到的是分区运算,数组的元素都会在每次循环中走访过一次,使用O(n)的时间。在使用结合(concatenation)的版本中,这项运算也是O(n)。
    在最好的情况,每次我们运行一次分区,我们会把一个数列分为两个几近相等的片段。这个意思就是每次递归调用处理一半大小的数列。因此,在到达大小为一的数列前,我们只要作log n次嵌套的调用。这个意思就是调用树的深度是O(log n)。但是在同一层次结构的两个程序调用中,不会处理到原来数列的相同部分;因此,程序调用的每一层次结构总共全部仅需要O(n)的时间(每个调用有某些共同的额外耗费,但是因为在每一层次结构仅仅只有O(n)个调用,这些被归纳在O(n)系数中)。结果是这个算法仅需使用O(n log n)时间。
    另外一个方法是为T(n)设立一个递归关系式,也就是需要排序大小为n的数列所需要的时间。在最好的情况下,因为一个单独的快速排序调用牵涉了O(n)的工作,加上对n/2大小之数列的两个递归调用,这个关系式可以是:
    T(n) = O(n) + 2T(n/2)
    解决这种关系式型态的标准数学归纳法技巧告诉我们T(n) = O(n log n)。
    事实上,并不需要把数列如此精确地分区;即使如果每个基准值将元素分开为99%在一边和1%在另一边,调用的深度仍然限制在100log n,所以全部运行时间依然是O(nlog n)。
    然而,在最坏的情况是,两子数列拥有大各为1和n-1,且调用树(call tree)变成为一个n个嵌套(nested)调用的线性连串(chain)。第i次调用作了O(n-i)的工作量,且 递归关系式为:
    T(n) = O(n) + T(1) + T(n - 1) = O(n) + T(n - 1)
    这与插入排序和选择排序有相同的关系式,以及它被解为T(n) = O(n2)。
    空间复杂度:
    被快速排序所使用的空间,依照使用的版本而定。使用原地(in-place)分区的快速排序版本,在任何递归调用前,仅会使用固定的額外空間。然而,如果需要产生O(logn)嵌套递归调用,它需要在他们每一个存储一个固定数量的信息。因为最好的情况最多需要O(log n)次的嵌套递归调用,所以它需要O(log n)的空间。最坏情况下需要O(n)次嵌套递归调用,因此需要O(n)的空间。
    然而我们在这里省略一些小的细节。如果我们考虑排序任意很长的数列,我们必须要记住我们的变量像是left和right,不再被认为是占据固定的空间;也需要O(log n)对原来一个n项的数列作索引。因为我们在每一个堆栈框架中都有像这些的变量,实际上快速排序在最好跟平均的情况下,需要O(log2 n)空间的比特数,以及最坏情况下O(nlog n)的空间。然而,这并不会太可怕,因为如果一个数列大部分都是不同的元素,那么数列本身也会占据O(n log n)的空间字节。
    非原地版本的快速排序,在它的任何递归调用前需要使用O(n)空间。在最好的情况下,它的空间仍然限制在O(n),因为递归的每一阶中,使用与上一次所使用最多空间的一半,且它的最坏情况是很恐怖的,需要空间,远比数列本身还多。如果这些数列元素本身自己不是固定的大小,这个问题会变得更大;举例来说,如果数列元素的大部分都是不同的,每一个将会需要大约O(logn)为原来存储,导致最好情况是O(n log n)和最坏情况是O(n2 log n)的空间需求。
    最坏时间复杂度: O(n²)
    最优时间复杂度: O(nlogn)
    平均时间复杂度: O(nlogn)
    空间复杂度: 根据实现的方式不同而不同

    展开全文
  • 常用排序算法分析

    2014-08-25 00:09:08
    常用排序算法分析 常用排序算法有冒泡排序,选择排序,插入排序,堆排,希尔排序和快排;本文尽可能详尽地分析每一种排序算法的定义,实现代码,算法时间复杂度和稳定性。 1.冒泡排序...
  • 排序类别,基本思想,排序算法,复杂度分析,稳定性,排序特点分析
  • 常见的排序算法分析(一) 说来惭愧,自2015~16年在大学校园里做了些小项目后,边从来没关注过排序算法。恰逢17年中兴成研所招收实习生,一把进入之后也再没想过关注这些排序算法。恰巧上周有校招新人面试,听闻...
  • 题目一: 内排序算法比较 1) 对以下6种常用的内部排序算法进行比较:起泡排序,直接插入排序,简单选择排序,快速排序,希尔排序,堆排序。 2) 待排序记录的文件个数不小于1000( 其数据用伪随机数产生),至少用5组...
  • 各种排序算法分析

    2013-09-05 11:51:02
    各种排序算法分析 2.1冒泡排序是稳定的,算法时间复杂度是O(n ^2)。 2.2 选择排序(Selection Sort) 选择排序的基本思想是对待排序的记录序列进行n-1遍的处理,第i遍处理是将L[i..n]中最小者与L...
  • Arrays.sort()排序算法分析 Arrays.sort()根据入参类型选择以下排序算法 基本类型数组使用快速排序 对象数组使用归并排序 原因 使用不同类型的排序算法主要是由于快速排序是不稳定的,而合并排序是稳定的。这里...
  • 插入排序算法分析

    2013-06-07 13:29:24
    插入排序算法分析  插入排序算法的原理类似扑克牌,最开始手中没有牌,所有的牌都反向铺在桌面上,玩家第一次起牌后,将此牌放于右手,可看成一个只有一个元素的排好序的数组,每当玩家起到其它牌的时候,就将此牌...
  • 一、如何分析一个排序算法 1.1 排序算法的执行效率 对于排序算法执行效率的分析,我们一般会从这几个方面来衡量: - 最好、最坏、平均情况时间复杂度 - 时间复杂度的系数、常数 、低阶 - 比较、交换或移动的次数 ...
  • JAVA中排序算法分析

    2012-11-25 10:45:48
    排序算法,JAVA中的快速排序,交换排序,冒泡排序,选择排序等算法的分析
  • 简单排序算法分析

    2018-04-14 17:26:24
    本文描述的算法虽然比较简单,执行速度...实际上插入排序也常作为快速排序算法实现的一部分一、冒泡排序冒泡算法运行起来非常慢,但是规则简单,因此冒泡排序算法在刚开始研究排序技术时是一个非常好的算法规则:1....
  • VC++ 经典的7种排序算法分析

    千次阅读 2016-11-18 10:36:04
    C++中经典的排序算法分析和应用。
  • 几种排序算法分析及python实现
  • 归并排序算法分析及优化 归并算法采用了分治法的思想:将原问题分解为几个规模较小但类似于原问题的字问题,递归地求解这些字问题,然后再合并这些字问题的解来建立原问题的解。 归并排序算法完全采用分治模式,操作...
  • 八大排序算法分析

    千次阅读 2020-06-11 12:58:20
    简要解释每一种排序算法思想,对每种排序的代码进行解读 对比复杂度,稳定性,并列表。 典型题目分析 时间复杂度下界 逆序对:i<j,如果A[i]>A[j],(i,j)即为逆序对,而交换两个相邻元素正好是消去一个逆序...
  • 经典排序算法分析

    2015-11-12 22:19:11
    文章对经典排序算法进行了分析、实现及比较。
  • 排序算法分析 - java版本

    千次阅读 2021-02-21 22:13:52
    它是直接插入排序算法的一种威力加强版。 主要是为了解决插入排序中,在集合前面有序元素过多时导致的重复无用循环的问题。 由于属于插入排序的变种,故基本原理也是插入排序的原理,将整个集合分为有序以及无无序...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 18,262
精华内容 7,304
关键字:

排序算法分析