精华内容
下载资源
问答
  • 数据结构排序算法大总结(C语言),总结整理直接插入排序、折半插入排序、希尔排序、冒泡排序、快速排序,简单选择排序、堆排序、归并排序、基数排序九大排序算法以及外排序的算法思想,结合图片演示原理,含源码。

    最近复习数据结构,看完排序,就想着赶紧总结一下,供自己整理学习,也供大家一起学习进步。

        目    录

    一、概述

    二、内排序

    1.插入排序

    1)直接插入排序

             2)折半插入排序(先折半查找再移动插入)

             3)希尔排序(缩小增量排序)

    2.交换排序

    1)冒泡排序

    2)快速排序

    3.选择排序

    1)简单选择排序

    2)堆排序

    4.归并排序

    5.基数排序(桶排序)

    1)LSD

    2)MSD

    三、内部排序总结

    四、外部排序

    1.置换选择排序

    2.最佳归并树

    3.败者树

     


    一、概述

    1. 排序分为内排序和外排序。衡量算法的三个主要标准,空间复杂度、时间复杂度、稳定性(稳定性指关键字相同的元素,在排序后前后相对顺序不变,本身不含褒贬)。
    2. 内排序又分为插入排序、交换排序、选择排序、归并排序、基数排序(根据算法实现的思想不同)。
    3. 外排序主要采用归并排序,为提高外部排序的效率有三种相关的优化算法。

    二、内排序

    1.插入排序

    插入排序包含:直接插入排序、折半插入排序、希尔排序

    1)直接插入排序

    算法思想:将数据集合看作是两个部分,前部分是有序集合,后半部分是待排序集合,每次从待排序的集合中取第一个元素,将其插入到有序集合应该放入的位置。在插入时候涉及到向后移位的操作,因为待插入位置之后的元素要向后移动,在直接插入排序中,比较移位同时进行的,待插入元素依次向前比较,若前一个元素大于它,则将前一个元素向后移动,再向前比较下一个元素,如图此时待排序元素为2,2与4比较,2小于4,在4前面,4向后移,2比较3,3向后移,2比较1,2在1后,则插入1之后。

    void InsertSort(int array[],int len){
    	int i,j,key;
    	for(i=1;i<len;i++){
    		if(array[i]<array[i-1]){
    			key=array[i];
    			for(j=i-1;j>=0&&array[j]>key;j--){
    				array[j+1]=array[j];
    			}
    			array[j+1]=key;
    		}
    		
    	}
    }

    空间复杂度:O(1);

    时间复杂度:最好情况,序列已经是升序排列了,需要进行的比较操作需(n-1)次即可。最坏情况,序列是降序排列,那么此时需要进行的比较共有n(n-1)/2次。插入排序的赋值操作是比较操作的次数加上 (n-1)次。平均来说插入排序算法的时间复杂度为O(n^2);

    稳定性:稳定;

    使用范围:适用于顺序存储和链式存储。

    总结:排序效率与初始序列的状态有关,适用于初始基本有序且规模不太大的序列,对于初始状态基本无序的序列,时间消耗较大。

    2)折半插入排序(先折半查找再移动插入)

    算法思想:直接插入排序是边比较边移动(如递增序列,若小于前一个数,前一个数向后移,继续向前比较),而折半插入排序则是将比较移动进行分离。先折半查找元素待插入的位置,再统一移动待插入位置之后的所有元素。因此,折半插入排序主要是减少了元素比较的次数,但移动次数没变。

    void BinaryInsertSort(int array[],int len){
    	int i,j,low,high,mid,key;
    	for(i=1;i<len;i++){
    		if(array[i]<array[i-1]){
    			key=array[i];
    			high=i-1;
    			low=0;
    			while(low<=high){
    				mid=(high+low)/2;
    				if(array[mid]>array[i])
    					high=mid-1;
    				else
    					low=mid+1;
    			}
    			for(j=i;j>low;j--){
    				array[j]=array[j-1];
    			}
    			array[low]=key;
    		}
    	}
    }

    空间复杂度:O(1);

    时间复杂度:比较次数减小,平均为O(nlog2n),移动次数未减少,平均来说,算法的时间复杂度为O(n^2);

    稳定性:稳定;

    使用范围:适用于顺序存储。

    总结:比较次数与待排序列初始状态无关,移动次数与初始序列状态有关,对于顺序存储的数据,使用折半插入可以节省比较的时间,但总的移动次数没有变。

    3)希尔排序(缩小增量排序)

    直接插入排序适用于数据量不大的排序,希尔排序适用于数据量比较大的情况。

    算法思想:将数据分成若干组,假设a[10]内存有10个无序元素,取增量d为10/2=5,则将10个数据分为5组,每组2个元素,将下标为0,5(0+d)定义为1组,1,6(1+d)定义为2组,3,7(3+d)定义为3组,4,8(4+d)定义为4组,5,9(5+d)定义为5组(注意这里是说的下标),然后每组中的元素进行比较,如不符合排序规则就进行插入排序操作。

    假设a[10]={8,5,3,1,2,4,6,9,7,0},递增排序;

    第一轮增量为5,分组如下:

    8,4为一组,4在8前,插入排序,4插入8前,则相当于两数互换,4,8;

    5,6为一组,5在6前,插入排序,位置不变;

    3,9为一组,3在9前,插入排序,位置不变;

    1,7为一组,1在7前,插入排序,位置不变;

    2,0为一组,0在2前,插入排序,0插入2前,相当于两数互换,0,2;

    第二轮,取增量为d=5/2=2(此时5为第一次取的增量),分成2组,每组5个元素,下标0,2(0+d),4(0+2d),6(0+3d),8(0+4d)为第一组,下标1,3(1+d),5(1+2d),7(1+3d),9(1+4d)为第二组,分组情况如图。

    此时执行插入排序,即{4,3,0,6,7}和{5,1,8,9,2}分别执行直接插入排序,直接插入排序过程就不赘述了(依次向前比较),比较结果插入相应位置,结果为{0,3,4,6,7}和{1,2,5,8,9},此时排序情况如图。

    第三轮,取增量为d=2/2=1(2为第二轮所取的增量),分成1组,即全部10个元素执行直接插入排序,此时,因为元素经过上面两轮的排序,已经具有较好的局部有序性,则很快就能得到最终结果,直接插入排序不做赘述。

    void ShellSort(int a[],int len){
    	int i,j,d=len/2,key;
    	while(d>=1){
    		for(i=d;i<len;i++){
    			if(a[i]<a[i-d]){
    				key=a[i];
    				for(j=i-d;j>=0&&a[j]>key;j=j-d)
    					a[j+d]=a[j];
    				a[j+d]=key;
    			}
    		}
    		d=d/2;
    	}
    }

    空间复杂度:O(1);

    时间复杂度:依赖于增量函数,最坏情况下,算法的时间复杂度为O(n^2);

    稳定性:不稳定;

    使用范围:适用于顺序存储。

    总结:中等大小规模表现良好,对规模非常大的数据排序不是很好的选择。但是比O(n^2)复杂度的算法快得多。

    2.交换排序

    交换排序包含:冒泡排序,快速排序

    交换,就是指两个元素互换位置,通过两个元素的比较,将这两个元素通过交换按照正确的顺序排列,不管是冒泡排序还是快速排序,每一趟排序都会将一个元素放置到有序序列的最终位置

    1)冒泡排序

    算法思想:将待排序表中的元素从后往前(或从前往后)两两比较相邻元素的值,若为逆序则交换它们的位置,直到序列比较完,这样最小的元素(假设递增排序)就会被交换到第一个位置,就这称之为一趟冒泡,每一趟冒泡都会将待排序元素中最小的一个放到有序序列的最后。

    void BubbleSort(int a[],int len){
    	int i,j;
    	int flag=1;//初始设置,假设有序
    	for(i=0;i<len;i++){
    		for(j=len-1;j>i;j--)
    			if(a[j-1]>a[j]){
    				swap(a,j,j-1);
    				flag=0;//每趟比较,若发生交换则设为无序。
    		}
    		if(flag)
    			return;
    	}
    }

    空间复杂度:O(1);

    时间复杂度:最好的情况下O(n),最坏情况下O(n^2),平均O(n^2);

    稳定性:稳定;

    使用范围:比较和移动只涉及相邻元素,适用于顺序存储,链式存储。

    总结:每一次排序都会有一个元素放在最终位置,执行效率与初始状态有关。

    2)快速排序

    算法思想:在待排序的元素序列中,选取一个关键字作为key,然后将剩下的元素分为两个子序列,一个子序列是关键字大于key的,另一个子序列是关键字小于key的,这样关键字为key的元素在最终有序序列的位置就确定了。然后采用递归操作,依次递归两个子序列,通常我们将每个序列的第一个元素的关键字作为key,这样对于相对有序的初始序列,快排的效率会大大降低,所以快排一般处理初始序列基本无序的序列,才能发挥最大优势。还可以用以下两种思路提高效率,一是在划分的子序列规模较小时,采用直接插入排序算法处理后续工作,二是,对于key的选取,可以采用不同的key的选取方法,尽量将序列划分两个长度差不多的子序列,避免极端情况。

    举例,a[]={3,5,4,0,2},按从小到大排序,第一次排序过程如下图。

    void QuickSort(int a[],int low,int high){
    	int key=a[low],low_2=low,high_2=high;//保存当前的上下界
    	if(low>high)//递归终止条件
    		return;
    	while(low<high){
    		while(low<high&&a[high]>key)
    			high--;
    		a[low]=a[high];
    		while(low<high&&a[low]<key)
    			low++;
    		a[high]=a[low];
    	}
    	a[low]=key;
    	QuickSort(a,low_2,low-1);
    	QuickSort(a,low+1,high_2);
    }

    空间复杂度:利用了一个工作栈,最好O(log2(n+1)),最坏O(n),平均O(log2n);

    时间复杂度:与划分的两个子序列是否对称有关,假设取第一个元素的关键字为key,当初始状态基本有序时,划分不对称,为最坏情况O(n^2),理想状态下O(nlog2n),平均运行时间与理想状态较接近;

    稳定性:不稳定;

    使用范围:适用于顺序存储。

    总结:每趟排序都会有一个元素放到最终位置,执行效率与划分方法有关,也即与key的取值有关,快排是所有内部排序算法中平均性能最佳的算法,适用于大量数据排序。

    3.选择排序

    选择排序包含:简单选择排序,堆排序

    选择排序,就是每次从待排序序列中找出最小(最大)值插入到有序序列的后面,选择的过程比较简单,也比较容易理解。

    1)简单选择排序

    算法思想:简单选择排序中,要从n个元素中找到一个关键字最小值或最大值则需要比较n-1次,设置一个min用来记录关键字最小的元素位置,初始设为第一个元素的下标,每次取一个元素和min位置的元素比较关键字大小,根据结果更新min,每一趟就会选出一个关键字最小的元素,共需要n-1趟,共需要比较1+2+3+...+(n-1)=n(n-1)/2次。

    void SelectSort(int a[],int len){
    	int i,j,min;
    	for(i=0;i<len;i++){
    		min=i;
    		for(j=i+1;j<len;j++){
    			if(a[j]<a[min])
    				min=j;
    		}
    		if(min!=i)
    			swap(a,min,i);
    	}
    }

    空间复杂度:O(1);

    时间复杂度:始终为O(n^2);

    稳定性:不稳定;

    使用范围:适用于顺序存储,链式存储。

    总结:与序列的初始状态无关,每趟选择可以确定一个元素的最终位置,时间复杂度固定不变。

    2)堆排序

    算法思想:利用树形结构进行选择排序,将a[1...n]视为一棵完全二叉树的顺序存储结构,双亲结点元素的关键字大于孩子结点关键字的称为大根堆,双亲结点元素的关键字小于孩子结点关键字的称为小根堆。初始状态下,需要先建堆,这个过程称之为堆化(heapify),建堆完成后,这棵树的根节点就是最大值(大根堆),直接选择根节点的元素即是待排序列的最大值,进行下次选择时,将根节点与最后一个叶子结点对换位置,然后删除最后一个叶子结点,再次heapify,以此类推。

    heapify:由上可知,堆排序的关键在于heapify,heapify的算法思想是,从第n/2⌋(向下取整)个结点 的位置(这个位置是最后一个非叶子结点)开始,以大根堆为例,判断⌊n/2⌋结点的关键字是否大于两个孩子结点的关键字:

    (1)若小于,则将⌊n/2⌋结点与其关键字较大的孩子结点互换位置,然后向下进行判断,以同样的方法继续判断以互换位置的孩子结点为根节点的子树是否满足大根堆(只有发生互换,即出现不满足大根堆时才继续向下heapify);

    (2)若大于,则向上判断,判断第n/2⌋-1个结点,直至判断调整至根结点,这里为了方便建堆结束。

    例,a[8]={1,2,3,4,5,6,7,8},建大根堆过程如下:

    1>8/2=4,第4个结点为a[4-1]=4,判断该结点是否满足大根堆定义,孩子节点a[7]=8>a[3],不满足大根堆,互换,然后判断a[7]结点,无孩子结点,满足大根堆。

    2>向上判断,4-1=3,第3个结点为a[3-1]=3,孩子结点a[5]=6,a[6]=7都比a[2]要大,不满足大根堆,取最大值互换,a[2]与a[6]互换,判断a[6]结点,无孩子结点,满足大根堆。

    3>向上判断,3-1=2,第2个结点为a[2-1]=2,孩子结点a[3]=8,a[4]=5都比a[1]要大,不满足大根堆,取最大值互换,a[1]与a[3]互换,判断a[3]结点,此时a[3]=2,孩子结点a[7]=4,不满足大根堆,互换,判断a[7]结点,无孩子结点,满足大根堆。

    4>向上判断,2-1=1,第1个结点为a[1-1]=2,孩子结点a[1]=8,a[2]=7都比a[0]要大,不满足大根堆,取最大值互换,a[0]与a[1]互换,判断a[1]结点,此时a[1]=1,孩子结点a[3]=4,a[4]=5,不满足大根堆,取最大值互换,判断a[4]结点,a[4]=1,无孩子结点,满足大根堆建堆完成。

    //堆化
    //heapify想要输出序列为递增,构造大根堆
    void Heapify(int tree[],int i,int n){
    	int c1=i*2+1;
    	int c2=i*2+2;
    	int max=i;
    	if(c1<n&&tree[c1]>tree[max]){
    		max=c1;
    	}
    	if(c2<n&&tree[c2]>tree[max]){
    		max=c2;
    	}
    	if(max!=i){
    		swap(tree,i,max);
    		Heapify(tree,max,n);
    	}
    }
    void BuildHeap(int tree[],int len){
    	int i;
    	//建大根堆
    	for(i=len/2;i>=0;i--)
    		Heapify(tree,i,len);
    	//排序
    	for(i=len-1;i>0;i--){
    		swap(tree,0,i);
    		Heapify(tree,0,i);
    	}
    }

    空间复杂度:O(1);

    时间复杂度:建堆时间O(n),n-1次调整,每次调整O(log2n),最坏情况O(nlog2n);

    稳定性:不稳定;

    使用范围:适用于顺序存储。

    总结:每趟排序确定一个元素的最终位置,适用于大量数据排序的情况,即使在最坏的情况下,时间复杂度仍为O(nlog2n)。

    4.归并排序

    算法思想:归并的含义就是将两个或两个以上的有序表组合成一个新的有序表。设待排序序列中含有n个元素,可将其视为n个有序的子序列,每个序列长度为1,在归并算法中,每次取m(m<n)个子序列进行归并,则称为m路归并。第一趟归并时,将n个子序列分成s=⌈n/m⌉ 个组,每个组内有m个子序列,最后一个组可以小于m,每个进行m路归并排序,形成新的s个子序列;然后进行第二趟归并,分成⌈s/m⌉个组,每组进行m路归并,如此重复,直到合并为1个有序序列。

    假设,a[]={8,5,2,3,4,6,7,1,9},由小到大,2路归并排序如下;

    void Merge(int a[],int b[],int low,int mid,int high){
    	int i,j,k=low;
    	for(i=low;i<=high;i++)//复制到b
    		b[i]=a[i];
    	for(i=low,j=mid+1;i<=mid&&j<=high;k++)
    		if(b[i]<=b[j])
    			a[k]=b[i++];
    		else
    			a[k]=b[j++];
    	while(i<=mid)
    		a[k++]=b[i++];
    	while(j<=high)
    		a[k++]=b[j++];
    }
    void MergeSort(int a[],int b[],int low,int high){
    	int mid;
    	if(low<high){
    		mid=(low+high)/2;
    		MergeSort(a,b,low,mid);
    		MergeSort(a,b,mid+1,high);
    		Merge(a,b,low,mid,high);
    	}
    }

    空间复杂度:辅助空间占n个单元,复杂度O(n);

    时间复杂度:每趟归并O(n),共log2n趟,时间复杂度O(nlog2n);

    稳定性:稳定;

    使用范围:适用于顺序存储;

    总结:时间复杂度为O(nlog2n)的稳定的排序算法,但需要消耗额外的空间,空间复杂度为O(n)。

    5.基数排序(桶排序)

    基数排序是一种与上述方法都不同的排序方法,上述方法都是基于对元素关键字的比较而进行排序的,基数排序是适用于多关键字,且关键字有一定范围的情况,通过“分配”与“回收”两种操作,对多个关键字中单关键字逐个进行排序,最后达到整体有序的目的。基数排序又称为桶排序,箱排序,个人觉得叫桶排序更形象。

    基数排序按照但关键字比较顺序的不同,可分成两类:最高位优先(MSD)、最低位优先(LSD),对于整数来讲,MSD和LSD是完全不同的,MSD适用于数据数位较多的情况,LSD适用于数据数位较少的情况;MSD在分配后,不立即回收桶,MSD是一个递归的算法,每次分配后,将元素多于1个的桶再分配,直至全分配为每个桶内元素均不多于1个,再回收桶,LSD则不存在这个问题,每次在分配后立即按序回收。

    算法思想:首先根据最后一个关键字(或者第一个,根据是MSD还是LSD)的范围设置桶的数量,假设范围为r,设置r个桶,然后“分配”:根据序列中每个数据元素最后一个关键字的取值,依次(元素的相对顺序不变)扔进对应的桶里;“回收”,按照关键字的取值顺序将各个桶内的元素首尾相接形成新的序列,这个序列就是按照最后一个关键字排序的序列。然后再根据倒数第二个关键字“分配”和“回收”,直至全部完成。所谓的关键字的范围,对于10进制整数来讲,范围为0-9;

    1)LSD

    举例说明,序列{321,852,753,416,085,009},按照从小到大递增顺序排序。

    分析:最高位为百位,所以有个位、十位、百位三个关键字,十进制数,每个关键字的范围为0-9,则每次分配10个桶,共需分配3次,按照LSD算法,第一次按照个位分配,第二次按照十位分配,第三次按照百位分配。

    2)MSD

    一样的例子,序列{321,852,753,416,085,009},按照从小到大递增顺序排序。

    分析:最高位为百位,所以有个位、十位、百位三个关键字,十进制数,每个关键字的范围为0-9,则每次分配10个桶,共需分配3次,按照MSD算法,第一次按照百位分配,如果有桶内元素多余1个,再按十位分配。

    void RadixSort(int a[],int len){
    	int i,j,max=a[0],r=0,d;
    	//创建10个桶
    	int bucketId,bucketLen;
    	int k,p;
            //使用二维数组作为桶(队列)
    	int **buckets=(int **)malloc(sizeof(int *)*10);
    	for(i=0;i<10;i++){
    		buckets[i]=(int *)malloc(sizeof(int)*(len+1));//多设一个位置,存当前桶内的元素个数
    		buckets[i][0]=0;//设置为空桶
    	}
    	//求最大值
    	for(i=1;i<len;i++)
    		if(max<a[i])
    			max=a[i];
    	//求最大位数
    	while(max!=0){
    		r++;
    		max=max/10;
    	}
    	//扔进桶
    	d=1;
    	for(i=0;i<r;i++){
    		//分配
    		for(j=0;j<len;j++){
    			bucketId=(a[j]/d)%10;
    			bucketLen=buckets[bucketId][0];
    			buckets[bucketId][bucketLen+1]=a[j];
    			buckets[bucketId][0]++;
    		}
    		//回收,回收时候注意要把桶清空。这里我直接把桶内的元素个数设置为0
    		j=0;
    		for(k=0;k<10;k++){
    			bucketLen=buckets[k][0];
    			if(bucketLen>0){
    				for(p=1;p<=bucketLen;p++)
    					a[j++]=buckets[k][p];
    			}
    			buckets[k][0]=0;//!!清空桶!!!!
    		}
    		d=d*10;//每次取得的位数慢慢增高
    	}
    	free(buckets);
    }

    空间复杂度:与关键字的范围有关,若范围为r,需要r个辅助队列,复杂度O(r);

    时间复杂度:与关键字的个数有关,若关键字个数为d(整数就是指位数),每趟分配为O(n),每趟回收为O(r),分配d趟,时间复杂度为O(d(n+r));

    稳定性:稳定;

    使用范围:适用于顺序存储,链式存储;

    总结:执行效率与序列初始状态无关,是基于多关键字的排序,关键字必须具有一定的范围,若范围太大,效率反而会降低,也不适用。

    三、内部排序总结

         算法名称 空间复杂度 时间复杂度 稳定性
    直接插入排序 O(1) O(n^2) 稳定
    折半插入排序 O(1) O(n^2) 稳定
    希尔排序 O(1) <O(n^2)(基于增量函数,最坏n^2) 不稳定
    冒泡排序 O(1) O(n^2) 稳定
    快速排序 O(log2n)(利用工作栈) O(nlog2n) 不稳定
    简单选择排序 O(1) O(n^2)(固定不变) 不稳定(低级排序中,唯一不稳定)
    堆排序 O(1) O(nlog2n) 不稳定
    归并排序 O(n)(合并操作创建辅助数组) O(nlog2n) 稳定(高级排序中,唯一稳定)
    基数排序 O(r)(关键字范围,桶的数量) O(d(n+r))(d躺分配,r个桶) 稳定

    1)高级排序中(O(nlog2n)),就平均性能而言,快速排序性能最佳,时间最省,但快速排序在最坏情况下不如堆排序和归并排序,而堆排序和归并排序,堆排序空间消耗更少,在n较大时,归并更快,但消耗辅助空间更多。

    2)简单排序中(O(n^2)),冒泡排序和直接插入排序在最好的情况下可以达到O(n),其中直接插入排序最为简单,当基本有序或者n较小时,使用直接插入排序最佳;当n较小时,如果元素本身信息量较大时,为减少元素移动消耗的时间,选择简单选择排序较好。

    四、外部排序

    外部排序,数据结构里只介绍了多路归并排序,然后由此延申,提出了三个提升归并效率的算法。

    因为内存比较小,在处理海量数据时,数据没有办法全部同时装入内存,导致只能利用外部排序归并算法将数据不断在内存和外存间写入写出,以达到排序的目的。在外部排序时,影响排序效率的主要因素是写入写出的时间,也即IO次数越多,耗时越久。

    算法思想:在外部排序时,首先将数据分成一个一个小的数据段,再将数据段装入内存利用内部排序算法进行排序,再写回外存,这个过程结束后,形成一个又一个的有序段,称为归并段。然后就是利用归并排序的思想,需要不断将归并段进行归并排序,如m路归并,每次从m个归并段各取一个元素装入内存比较,每次取出一个最小元素,输出到外存,然后取出元素所在的归并段下一个元素补上,再比较,再输出,以此类推。

    1.置换选择排序

    如果分成的归并段太多,那么需要多次归并,增加了归并趟数,同时增加了写入写出时间的消耗,由此引出了置换选择算法,该算法可以减少归并段的数量,甚至可以使归并段的大小(元素个数)超过内存。

    算法思想:(假设递增)

    1)将待排序序列元素依次放入内存,直至填满内存;

    2)此时选内存中关键字最小的元素输出到外存加入有序序列,并将其关键字记录下来记为max;

    3)从待排序序列中取出下一个元素放入内存,补上空出的位置;再次执行2操作,如果要输出元素的关键字小于max,执行4操作;

    4)将该元素进行标记(此时内存中的最小值),选取内存中未标记过的关键字最小的元素输出到外存加入有序序列,执行3操作,直至内存中所有的元素都已经被标记,此时,已经输出的有序序列作为第一个归并段(长度可能远大于内存大小),将内存中元素的标记全部抹去,按照2-4的顺序,输出下一个归并段。

    举例,8,3,1,9,7,2,6,4,5,按递增排序,内存可容纳3个数,采用置换选择排序生成归并段。

    2.最佳归并树

    利用置换选择排序后,得到的是大小不等的归并段,假设m路归并,每一趟归并,都要让m个归并段参加,那么第一趟就参与归并操作的归并段中的元素,后面每一趟排序都要再次参与归并,这样的话,如果第一次归并时,归并段的元素太多,那么后面每一趟归并所需要的IO次数就会很多,所以最佳归并树,就是利用哈夫曼树的原理,让归并树的带权路径最短,从而减少总的IO次数,提升系统排序效率的方法。

    最佳归并树是一棵只有度为0和度为m的结点的严格m叉树(假设m路归并)。将每一个归并段当作一个叶子结点,每个归并段的长度作为该结点的权值,在构建最佳归并树时,和构建哈夫曼树不同的是,需要先计算一下所给的结点(归并段数量)是否可以正好构成一棵严格的m叉树,如果不能构成的话,需要添加权值为0的结点,使其可以刚好构成一棵严格的m叉树,首先计算u=(n0-1)%(m-1)(n0为叶子结点的数量,也就是归并段的段数),如果u为0,则说明刚好可以构成一棵严格的m叉树,若u不为0,计算m-u-1的值,这个值就是应该添加的0结点的数量。

    举例,8个初始归并段,其长度分别为8,3,9,7,2,6,4,5,采用3路归并排序,构造最佳归并树。

    u=(8-1)%(3-1)=1,表示需要添加3-1-1=1个0结点,构造最佳归并树过程如下。

    3.败者树

    每一趟归并排序,从需要归并的归并段中各取出一个元素,放入内存进行比较,每次取出其中的关键字最小(大)的元素,如果有N个元素,那么需要比较N-1次,当数据量很大时,这是很耗时间的,而败者树是用来在归并排序中减少元素间比较次数的。败者树的思想是,构造一棵完全二叉树,每个叶子结点存放各个参与归并排序需要比较的元素,内部结点用来记忆左右子树的失败者,让胜者往上继续比较(作为败者结点的父节点),一直到根节点,根节点指向最小(大)的元素。

    假设,归并段为(8,5,2),(4,1,6),(3,7),初始装入内存为,8,4,3;

    后面就不细讲了,依次选出最小的元素,只举第一二轮作为例子,在第一轮结束后,第三个归并段内的7补上,此时,8与4不用再重新比较了,只需要不叫4与7的大小,就可以选出最小元素为4,减少了比较的次数。

    因此,n个元素,m路归并,初始归并段数为r,所需的归并趟数s=logm(r),使用败者树,每m个元素挑选1个最小值需要比较⌈log2m⌉ 次(败者树的深度),故每一趟归并(n个元素参加),只需要比较(n-1)⌈log2m⌉ 次(败者树的深度),故总的比较次数为S(n-1)⌈log2m⌉=⌈logm(r)⌉(n-1)⌈log2m⌉=(n-1)⌈log2r⌉,比起不使用败者树的情况,共需要比较⌈logm(r)⌉(n-1)(m-1)次,使用归并树,减少了IO次数,提高了效率。

     

    参考书:《2020年数据结构考研复习指导》王道论坛,《数据结构》严蔚敏。

    (有不妥不对之处,欢迎留言指出,一起进步~有些算法还看不懂我觉得可以去B站搜相关视频看)

    展开全文
  • 数据结构排序算法

    千次阅读 2013-07-15 13:00:09
    冒泡排序: #include void Swap(int *a,int *b) { int tmp = *a; *a = *b; *b = tmp; } void BubbleSort(int arr[],int len) { /*需要n-1趟排序*/ for (int i = 0; i ; ++i) { for (int j = 0; j < len -
    转载请注明出处:http://blog.csdn.net/anzelin_ruc/article/details/9294459
    
    

    冒泡排序:

    重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到不再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端,故名。

    算法步骤:

    1.比较相邻的元素。如果第一个比第二个大,就交换他们两个。
    2.对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。对所有元素在一趟比较之后,最后的元素应该就是最大的数。

    3.针对除最后已排好序的所有的元素重复以上步骤1和2,直到没有任何一对数字需要比较。

    时间复杂度:

    若文件的初始状态是正序的,一趟扫描即可完成排序。所需的关键字比较次数和记录移动次数均达到最小值:C(min) = n-1, M(min) = 0。所以,冒泡排序最好的时间复杂度为:o(n)。

    若初始文件是反序的,需要进行趟排序。每趟排序要进行次关键字的比较(1≤i≤n-1),且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下,比较和移动次数均达到最大值:C(max) = n(n-1)/2 = o(n^2) M(max) =  3n(n-1)/2 = o(n^2)。所以,冒泡排序的最坏时间复杂度:o(n^2)

    综上,因此冒泡排序总的平均时间复杂度为:o(n^2)。

    空间复杂度:

    该算法只有在进行数据交换时最多需要一个临时变量,因此空间复杂度为o(1)。

    算法稳定性:

    冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较,交换也发生在这两个元素之间。所以,如果两个元素相等,则不需要进行交换;如果两个相等的元素没有相邻,那么即使通过前面的两两交换把两个相邻起来,这时候也不会交换,因此相同元素的前后顺序不会发生改变,冒泡排序是一种稳定排序算法。


    #include <stdio.h>
    
    void Swap(int *a,int *b)
    {
    	int tmp = *a;
    	*a = *b;
    	*b = tmp;
    }
    
    void BubbleSort(int arr[],int len)
    {
    	/*需要n-1趟排序*/
    	for (int i = 0; i < len - 1; ++i)
    	{
    		for (int j = 0; j < len -1 - i; ++j)
    		{
    			if (arr[j] > arr[j+1])
    			{
    				swap(&arr[j],&arr[j+1]);
    			}
    		}
    	}
    }
    
    int main(int argc, char const *argv[])
    {
    	int arr[10] = {9,8,7,6,5,4,3,2,1,0};
    	int len = sizeof(arr)/sizeof(int);
    
    	for (int i = 0; i < len; ++i)
    	{
    		printf("%d ",arr[i]);
    	}
    	printf("\n");
    
    	BubbleSort(arr,len);
    
    	for (int i = 0; i < len; ++i)
    	{
    		printf("%d ", arr[i]);
    	}
    	printf("\n");
    	return 0;
    }

    直接插入排序:

    有一个已经有序的数据序列,要求在这个已经排好的数据序列中插入一个数,但要求插入后此数据序列仍然有序。

    算法步骤:

    1.从第一个元素开始,该元素可以认为已经被排序。
    2. 取出下一个元素,在已经排序的元素序列中从后向前扫描。
    3. 如果该元素(已排序)大于新元素,将该元素移到下一位置。
    4. 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置。
    5. 将新元素插入到下一位置中。
    6. 重复步骤2。

    时间复杂度:

    如果目标是把n个元素的序列升序排列,那么采用插入排序存在最好情况和最坏情况。最好情况就是,序列已经是升序排列了,在这种情况下,需要进行的比较操作需(n-1)次即可。最坏情况就是,序列是降序排列,那么此时需要进行的比较共有n(n-1)/2次。插入排序的赋值操作是比较操作的次数加上 (n-1)次。平均来说插入排序算法的时间复杂度为O(n^2)。因而,插入排序不适合对于数据量比较大的排序应用。但是,如果需要排序的数据量很小,例如,量级小于千,那么插入排序还是一个不错的选择。

    空间复杂度:

    直接插入排序只有需要一个临时变量存储将要插入的数据,因此空间复杂度为o(1)。

    算法稳定性:

    直接插入排序是在一个已经有序的小序列的基础上,一次插入一个元素。当然,刚开始这个有序的小序列只有1个元素,就是第一个元素。比较是从有序序列的末尾开始,也就是想要插入的元素和已经有序的最大者开始比起,如果比它大则直接插入在其后面,否则一直往前找直到找到它该插入的位置。如果碰见一个和插入元素相等的,那么插入元素把想插入的元素放在相等元素的后面。所以,相等元素的前后顺序没有改变,从原无序序列出去的顺序就是排好序后的顺序,所以插入排序是稳定的。

    #include <stdio.h>
    
    void InsertSort(int arr[],int n)
    {
    	for (int i = 1; i < n; ++i)
    	{
    		int tmp = arr[i];
    		int j;
    		for (j = i; j > 0 && arr[j-1] > tmp ; --j)
    		{
    			arr[j] = arr[j-1];
    		}
    		arr[j] = tmp;
    	}
    }
    
    int main(int argc, char const *argv[])
    {
    	int arr[10] = {9,8,7,6,5,4,3,2,1,0};
    	int len = sizeof(arr)/sizeof(int);
    	for (int i = 0; i < len; ++i)
    	{
    		printf("%d ", arr[i]);
    	}
    	printf("\n");
    	
    	InsertSort(arr,len);
    	
    	for (int i = 0; i < len; ++i)
    	{
    		printf("%d ", arr[i]);
    	}
    	printf("\n");
    	return 0;
    }

    希尔排序:

    希尔排序(Shell Sort)是插入排序的一种。是针对直接插入排序算法的改进。该方法又称缩小增量排序,因DL.Shell于1959年提出而得名。

    算法步骤:

    先取一个小于n的整数d1作为第一个增量,把文件的全部记录分成d1个组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序;然后,取第二个增量d2<d1重复上述的分组和排序,直至所取的增量dt=1(dt<dt-l<…<d2<d1),即所有记录放在同一组中进行直接插入排序为止。

    时间复杂度:

    希尔排序的时间复杂度与增量序列的选取有关,例如希尔增量时间复杂度为O(n^2),而Hibbard增量的希尔排序的时间复杂度为O(N^(5/4)),但是现今仍然没有人能找出希尔排序的精确下界。

    空间复杂度:

    希尔排序只有需要一个临时变量存储将要插入的数据,因此空间复杂度为o(1)。

    算法稳定性:

    由于进行了多次直接插入排序,我们知道一次插入排序是稳定的,不会改变相同元素的相对顺序,但在不同的插入排序过程中,相同的元素可能在各自的插入排序中移动,最后其稳定性就会被打乱,所以希尔排序是不稳定的。

    #include <stdio.h>
    
    
    void ShellSort1(int arr[],int n)
    {
    	/*步长为gap,每次排序后gap减半,知道gap =1 */
    	for (int gap = n/2; gap > 0; gap /= 2)
    	{
    		/*对各组进行排序*/
    		for (int i = gap; i < n; ++i)
    		{
    			int j;
    			int tmp = arr[i];
    			for (j = i; j >= gap && arr[j - gap] > tmp; j -= gap)
    			{
    				arr[j] = arr[j - gap];
    			}
    			arr[j] = tmp;
    		}
    	}
    
    
    }
    
    
    void ShellSort2(int arr[],int n)
    {
    	/*步长为gap,每次排序后gap减半,知道gap =1 */
    	for (int gap = n/2; gap > 0; gap /= 2)
    	{
    		/*对各组进行排序*/
    		for (int i = gap; i < n; ++i)
    		{
    			int j;
    			int tmp = arr[i];
    			for (j = i; j >= gap && arr[j -gap] > tmp; j -= gap)
    			{
    				arr[j] = arr[j - gap];
    				arr[j -gap] = tmp ;
    			}
    			
    		}
    	}
    
    
    }
    
    
    int main(int argc, char const *argv[])
    {
    	int arr[10] = {9,8,7,6,5,4,3,2,1,0};
    	int len = sizeof(arr)/sizeof(int);
    	for (int i = 0; i < len; ++i)
    	{
    		printf("%d ", arr[i]);
    	}
    	printf("\n");
    
    
    	ShellSort1(arr,len);
    
    
    	for (int i = 0; i < len; ++i)
    	{
    		printf("%d ", arr[i]);
    	}
    	printf("\n");
    
    
    	return 0;
    }


    简单选择排序:

    每一趟从待排序的数据元素中选出最小(或最大)的一个元素,顺序放在已排好序的数列的最后,直到全部待排序的数据元素排完。 

    算法步骤:

    n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果:
    1.初始状态:无序区为R[1..n],有序区为空。
    2.第1趟排序在无序区R[1..n]中选出关键字最小的记录R[k],将它与无序区的第1个记录R[1]交换,使R[1..1]和R[2..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。

    3.第i趟排序开始时,当前有序区和无序区分别为R[1..i-1]和R(i..n)。该趟排序从当前无序区中选出关键字最小的记录 R[k],将它与无序区的第1个记录R交换,使R[1..i]和R分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。
    这样,n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果。


    时间复杂度:

    选择排序的交换操作介于 0 和 (n - 1) 次之间。选择排序的比较操作为 n (n - 1) / 2 次之间。选择排序的赋值操作介于 0 和 3 (n - 1) 次之间。 比较次数O(n^2),比较次数与关键字的初始状态无关,总的比较次数N=(n-1)+(n-2)+...+1=n*(n-1)/2。交换次数O(n),最好情况是,已经有序,交换0次;最坏情况是,逆序,交换n-1次。因此简单选择排序的时间复杂度是O(n^2)。

    空间复杂度:

    这里需要一个额外的空间存储当前临时的最小值,因此空间复杂度为O(1)。

    算法稳定性:

    选择排序是给每个位置选择当前元素最小的,比如给第一个位置选择最小的,在剩余元素里面给第二个元素选择第二小的,依次类推,直到第n-1个元素,第n个元素不用选择了,因为只剩下它一个最大的元素了。那么,在一趟选择,如果当前元素比一个元素小,而该小的元素又出现在一个和当前元素相等的元素后面,那么交换后稳定性就被破坏了。比较拗口,举个例子,序列5 8 5 2 9,我们知道第一遍选择第1个元素5会和2交换,那么原序列中2个5的相对前后顺序就被破坏了,所以选择排序不是一个稳定的排序算法。

    #include <stdio.h>
    
    void swap(int *a,int *b)
    {
    	int tmp = *a;
    	*a = *b;
    	*b = tmp;
    }
    
    void SimpleSelectSort(int arr[],int len)
    {
    	
    	for (int i = 0; i < len; ++i)
    	{
    		int min_index = i;
    		for (int j = i + 1; j < len ; ++j)
    		{
    			if (arr[j] < arr[min_index])
    			{
    				min_index = j;
    			}
    		}
    		if (min_index != i)
    		{
    			swap(&arr[i],&arr[min_index]);
    		}
    	}
    }
    
    
    int main(int argc, char const *argv[])
    {
    	int arr[10] = {9,8,7,6,5,4,3,2,1,0};
    	int len = sizeof(arr)/sizeof(int);
    
    	for (int i = 0; i < len; ++i)
    	{
    		printf("%d ", arr[i]);
    	}
    	printf("\n");
    
    	SimpleSelectSort(arr,len);
    
    	for (int i = 0; i < len; ++i)
    	{
    		printf("%d ", arr[i]);
    	}
    	printf("\n");
    	return 0;
    }

    堆排序:

    堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法,可以利用数组的特点快速定位指定索引的元素

    算法步骤:

    堆排序利用了大根堆(或小根堆)堆顶记录的关键字最大(或最小)这一特征,使得在当前无序区中选取最大(或最小)关键字的记录变得简单。 (1)用大根堆排序的基本思想 :
    ① 先将初始文件R[1..n]建成一个大根堆,此堆为初始的无序区 。
    ② 再将关键字最大的记录R[1](即堆顶)和无序区的最后一个记录R[n]交换,由此得到新的无序区R[1..n-1]和有序区R[n],且满足R[1..n-1].keys≤R[n].key 。
    ③由于交换后新的根R[1]可能违反堆性质,故应将当前无序区R[1..n-1]调整为堆。然后再次将R[1..n-1]中关键字最大的记录R[1]和该区间的最后一个记录R[n-1]交换,由此得到新的无序区R[1..n-2]和有序区R[n-1..n],且仍满足关系R[1..n-2].keys≤R[n-1..n].keys,同样要将R[1..n-2]调整为堆。 …… 直到无序区只有一个元素为止。 
    (2)大根堆排序算法的基本操作:
     ① 初始化操作:将R[1..n]构造为初始堆。
     ② 每一趟排序的基本操作:将当前无序区的堆顶记录R[1]和该区间的最后一个记录交换,然后将新的无序区调整为堆(亦称重建堆)。
     注意:
     ①只需做n-1趟排序,选出较大的n-1个关键字即可以使得文件递增有序。 
    ②用小根堆排序与利用大根堆类似,只不过其排序结果是递减有序的。堆排序和直接选择排序相反:在任何时刻堆排序中无序区总是在有序区之前,且有序区是在原向量的尾部由后往前逐步扩大至整个向量为止

    时间复杂度:

    堆排序的时间,主要由建立初始堆和反复重建堆这两部分的时间开销构成。堆排序的最坏时间复杂度为O(nlogn)。堆序的平均性能较接近于最坏性能。由于建初始堆所需的比较次数较多,所以堆排序不适宜于记录数较少的文件

    空间复杂度:

    和上面算法一样,堆排序是就地排序,辅助空间为O(1)。

    算法稳定性:

    堆排序是不稳定的排序方法。
    #include <stdio.h>
    void swap(int *a,int *b)
    {
    	int tmp = *a;
    	*a = *b;
    	*b = tmp;
    }
    /*堆调整*/
    void HeapAdjust(int *arr,int i,int size){
    	int lchild = 2*i+1;    //节点i的左子节点
    	int rchild = 2*(i+1);  //节点i的右子节点
    	int max = i;           
    	if (i <= size/2)       //只对非叶节点进行调整
    	{
    		if (lchild < size && arr[lchild] > arr[max])
    		{
    			max = lchild;
    		}
    		if (rchild < size && arr[rchild] > arr[max])
    		{
    			max = rchild;
    		}
    
    
    		if (max != i)
    		{
    			swap(&arr[i],&arr[max]);
    			HeapAdjust(arr,max,size);//对调整过的max节点重新进行堆调整
    		}
    	}
    
    
    }
    /*建立无序大顶堆*/
    void BulidHeap(int *arr,int size)
    {
    	for (int i = size/2; i >= 0; --i)
    	{
    		HeapAdjust(arr,i,size);
    	}
    }
    
    
    /*堆排序*/
    void HeapSort(int *arr, int size)
    {
    	BulidHeap(arr,size);
    	for (int i = size - 1; i > 0; --i)
    	{
    		swap(&arr[0], &arr[i]);
    		HeapAdjust(arr,0,i);
    	}
    }
    
    
    int main(int argc, char const *argv[])
    {
    	int size = 10;
    	int arr[10] = {9,8,7,6,5,4,3,2,1,0};
    	for (int i = 0; i < size; ++i)
    	{
    		printf("%d ",arr[i]);
    	}
    	printf("\n");
    	HeapSort(arr, size);
    
    
    	for (int i = 0; i < size; ++i)
    	{
    		printf("%d ",arr[i]);
    	}
    	printf("\n");
    	return 0;
    }
    
    


    归并排序:

    归并(Merge)排法是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个子序列,每个子序列是有序的。然后再把有序子序列合并为整体有序序列的排序算法。归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为2-路归并。

    算法步骤:

    归并操作的工作原理如下:第一步:申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列第二步:设定两个指针,最初位置分别为两个已经排序序列的起始位置第三步:比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置重复步骤3直到某一指针达到序列尾将另一序列剩下的所有元素直接复制到合并序列尾。
    例如:
    如 设有数列{6,202,100,301,38,8,1} 
    初始状态:[6] [202] [100] [301] [38] [8] [1]      比较次数 
    i=1   [6 202 ] [ 100 301] [ 8 38] [ 1 ]3
    i=2[ 6 100 202 301 ] [ 1 8 38 ]
    i=3 [ 1 6 8 38 100 202 301 ]4
     总计: 11次

    时间复杂度:

    将参加排序的初始序列分成长度为1的子序列进行第一趟排序,得到 n / 2 个长度为 2 的各自有序的子序列(若n为奇数,还会存在一个最后元素的子序列),再调用排序函数进行第二趟排序,得到 n / 4 个长度为 4 的各自有序的子序列, 第 i 趟排序就是两两归并长度为 2^(i-1) 的子序列得到 n / (2^i) 长度为 2^i 的子序列,直到最后只剩一个长度为n的子序列。由此看出,一共需要 log2n 趟排序,每一趟排序的时间复杂度是 O(n), 由此可知 该算法的总的时间复杂度是是 O(n log2n)。

    空间复杂度:

    归并排序算法需要和原数据规模一样大的辅助空间 ,因此其空间复杂度是 O(n)。

    算法稳定性:

    归并(Merge)排序法是一个稳定的排序算法。

    #include <stdio.h>
    
    int arr[10] = {9,8,7,6,5,4,3,2,1,0};
    int tmp[10]; 
    
    void Merge(int begin,int middle,int end)
    {
    	int i = begin;
    	int j = middle + 1;
    	int k = begin;
    	
    	while(i <= middle && j <= end)
    	{
    		if (arr[i] <= arr[j] )
    		{
    			tmp[k++] = arr[i++];
    		}
    		else
    		{
    			tmp[k++] = arr[j++];
    		}
    	}
    
    	while(i <= middle)
    	{
    		tmp[k++] = arr[i++];
    	}
    
    	while(j <= end)
    	{
    		tmp[k++] = arr[j++];
    	}
    
    	for (k = begin; k <= end; ++k)
    	{
    		arr[k] = tmp[k];
    	}
    }
    
    void MergeSort(int begin,int end)
    {
    	if (begin < end)
    	{
    		int middle = (begin + end) / 2;
    		MergeSort(begin,middle);
    		MergeSort(middle + 1,end);
    		Merge(begin,middle,end);
    	}
    }
    
    
    int main(int argc, char const *argv[])
    {
    	int len = sizeof(arr)/sizeof(int);
    	for (int i = 0; i < len; ++i)
    	{
    		printf("%d ",arr[i] );
    	}
    	printf("\n");
    	
    	MergeSort(0,len - 1);
    	
    	for (int i = 0; i < len; ++i)
    	{
    		printf("%d ",arr[i] );
    	}
    	printf("\n");
    	return 0;
    }
    


    快速排序:

    快速排序(Quicksort)是对冒泡排序的一种改进。由C. A. R. Hoare在1962年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。

    算法步骤:

    一趟快速排序的算法是:
     1)设置两个变量i、j,排序开始的时候:i=0,j=N-1;
     2)以第一个数组元素作为关键数据,赋值给key,即key=A[0];
     3)从j开始向前搜索,即由后开始向前搜索(j -- ),找到第一个小于key的值A[j],A[i]与A[j]交换; 
    4)从i开始向后搜索,即由前开始向后搜索(i ++ ),找到第一个大于key的A[i],A[i]与A[j]交换; 
    5)重复第3、4、5步,直到 I=J; (3,4步是在程序中没找到时候j=j-1,i=i+1,直至找到为止。找到并交换的时候i, j指针位置不变。另外当i=j这过程一定正好是i+或j-完成的最后令循环结束。
    例如:
    待排序的数组A的值分别是:(初始关键数据:key=49) 注意关键key永远不变,永远是和key进行比较,无论在什么位置,最后的目的就是把key放在中间,小的放前面大的放后面。
    A[0]
    A[1]
    A[2]
    A[3]
    A[4]
    A[5]
    A[6]
    49
    38
    65
    97
    76
    13
    27
    进行第一次交换后:27 38 65 97 76 13 49
    ( 按照算法的第三步从后面开始找,此时:J=6)
    进行第二次交换后:27 38 49 97 76 13 65
    ( 按照算法的第四步从前面开始找>key的值,65>49,两者交换,此时:I=2 )
    进行第三次交换后:27 38 13 97 76 49 65
    ( 按照算法的第五步将又一次执行算法的第三步从后开始找
    进行第四次交换后:27 38 13 49 76 97 65
    ( 按照算法的第四步从前面开始找大于key的值,97>49,两者交换,此时:I=3,J=5 )
    此时再执行第三和四步的时候就发现i=J=4,从而结束一趟快速排序,那么经过一趟快速排序之后的结果是:27 38 13 49 76 97 65,即所有大于key49的数全部在49的后面,所有小于key(49)的数全部在key(49)的前面。

    时间复杂度:

    快速排序每次将待排序数组分为两个部分,在理想状况下,每一次都将待排序数组划分成等长两个部分,则需要logn次划分。而在最坏情况下,即数组已经有序或大致有序的情况下,每次划分只能减少一个元素,快速排序将不幸退化为冒泡排序,所以快速排序时间复杂度下界为O(nlogn),最坏情况为O(n^2)。在实际应用中,快速排序的平均时间复杂度为O(nlogn)

    空间复杂度:

    快速排序需要一个额外的空间存储关键元素(pivot element),因此空间复杂度为O(1)。

    算法稳定性:

    快速排序不稳定,且是在关键元素和某个元素发生交换时导致稳定性被破坏,比如序列5 3 3 4 3 8 9 10 11, 现在中枢元素5和3(第5个元素,下标从1开始计)交换就会破坏元素3的稳定性。

    #include <stdio.h>
    #include <string.h>
    #include <malloc.h>
    
    void swap(int *a,int *b)
    {
    	int tmp;
    	tmp = *a;
    	*a = *b;
    	*b = tmp;
    }
    
    int partition(int *arr,int low,int high)
    {
    	int pivot = arr[low];
    	while(low < high)
    	{
    		while(low < high && arr[high] >= pivot)
    		{
    			high--;
    		}
    		if (low < high)
    		{
    			swap(&arr[low],&arr[high]);
    			low++;
    		}
    		while(low < high && arr[low] <= pivot)
    		{
    			low++;
    		}
    		if(low < high)
    		{
    			swap(&arr[low],&arr[high]);
    			high--;
    		}
    	}
    
    	return low;
    
    }
    void quickSort(int *arr,int low,int high)
    {
    	int pivotpos;
    	if (low < high)
    	{
    		pivotpos = partition(arr,low,high);
    		quickSort(arr,low,pivotpos-1);
    		quickSort(arr,pivotpos+1,high);
    	}
    }
    
    
    int main(int argc, char const *argv[])
    {
    	int n ;
    	printf("please input the length of arr:\n");
    	scanf("%d",&n);
    	//int *arr  = (int*)malloc(n * sizeof(int));
    	int arr[n];
    	printf("please input  %d numbers for each elements\n", n);
    	for(int i = 0; i < n; i++)
    	{
    		scanf("%d",&arr[i]);
    		
    	}
    	quickSort(arr,0,n-1);
    	for (int i = 0; i < n; ++i)
    	{
    		printf("%d ",arr[i]);
    	}
    	printf("\n");
    	return 0;
    }

    以上就是基本的数据结构排序算法,欢迎补充和讨论。
    展开全文
  • 数据结构排序算法学习之插入排序

    万次阅读 2019-09-02 08:46:43
    数据结构排序算法之插入排序<一> 插入排序(Insertion sort) 是一种简单直观且稳定的排序算法。如果有一个已经有序的数据序列,要求在这个已经排好的数据序列中插入一个数,但要求插入后此数据序列仍然有序,...

    数据结构排序算法之插入排序<一>

    插入排序(Insertion sort)

    是一种简单直观且稳定的排序算法。如果有一个已经有序的数据序列,要求在这个已经排好的数据序列中插入一个数,但要求插入后此数据序列仍然有序,这个时候就要用到一种新的排序方法——插入排序法,插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中,从而得到一个新的、个数加一的有序数据,算法适用于少量数据的排序,时间复杂度为O(n^2)。是稳定的排序方法。插入算法把要排序的数组分成两部分:第一部分包含了这个数组的所有元素,但将最后一个元素除外(让数组多一个空间才有插入的位置),而第二部分就只包含这一个元素(即待插入元素)。在第一部分排序完成后,再将这个最后元素插入到已排好序的第一部分中。

    插入排序的基本思想

    每步将一个待排序的记录,按其关键码值的大小插入前面已经排序的文件中适当位置上,直到全部插入完为止。

    分类
    emmmm这里只说三种主要的:

    1. 直接插入排序
    2. 折半插入排序(二分插入排序)
    3. 希尔排序(又称缩小增量排序)

    1.直接插入排序

    把n个待排元素分为有序区和无序区,开始时有序区中只包含1个元素,无序区中则包含n-1个元素,排序过程中每次都从无序区中取出第一个元素,将它插入到有序区中的适当位置,使之成为一个有序的表,重复n-1次可完成排序过程。

    Java实现:

    package priv.qcy.sort.insert;
    
    public class InsertSort {
    
    	public static void insertSort(int[] a, int n) {
    
    		int i, j;
    		for (i = 1; i < n; i++) {
    			int temp = a[i];
    			for (j = i - 1; j >= 0 && a[j] > temp; j--) {
    				a[j + 1] = a[j];
    
    			}
    			a[j + 1] = temp;
    
    		}
    
    	}
    
    	public static void main(String[] args) {
    		int[] a = { 20, 40, 30, 10, 60, 50 };
    		System.out.print("排序前:");
    		for (int i = 0; i < a.length; i++) {
    			System.out.print(a[i] + "  ");
    
    		}
    		System.out.println();
    		insertSort(a, a.length);
    		System.out.print("排序后:");
    		for (int i = 0; i < a.length; i++) {
    			System.out.print(a[i] + "  ");
    
    		}
    
    	}
    
    }
    
    

    直接插入排序时间复杂度
    直接插入排序的时间复杂度是O(N^2)。
    假设被排序的数列中有N个数。遍历一趟的时间复杂度是O(N),而直接插入排序需要遍历N-1次。因此,直接插入排序的时间复杂度是O(N^2)。

    直接插入排序稳定性
    直接插入排序是稳定的算法,它满足稳定算法的定义。
    算法稳定性 – 假设在数列中存在a[i]=a[j],若在排序之前,a[i]在a[j]前面;并且排序之后,a[i]仍然在a[j]前面。则这个排序算法是稳定的!

    特点

    1. 也适用于链式存储结构
    2. 更适用于初始记录基本有序的情况(当N较大且无序时,此算法时间复杂度较高)
    展开全文
  • 数据结构排序算法学习之插入排序3

    万次阅读 2019-09-03 20:28:31
    数据结构排序算法之插入排序<三> 3.希尔排序(递减增量排序) 希尔排序从“减少记录个数”和“序列基本有序”两个方面对直接插入排序算法进行改进,但插入排序一般来说是低效的,因为插入排序每次只能将数据...

    数据结构排序算法之插入排序<三>

    3.希尔排序(递减增量排序)

    希尔排序从“减少记录个数”和“序列基本有序”两个方面对直接插入排序算法进行改进,但插入排序一般来说是低效的,因为插入排序每次只能将数据移动一位。

    基本思想:

    先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序。
    对于n个待排序的数列,取一个小于n的整数gap(gap被称为步长)将待排序元素分成若干个组子序列,所有距离为gap的倍数的记录放在同一个组中;然后,对各组内的元素进行直接插入排序。 这一趟排序完成之后,每一个组的元素都是有序的。然后减小gap的值,并重复执行上述的分组和排序。重复这样的操作,当gap=1时,整个数列就是有序的。

    希尔排序

    Java实现:

    package priv.qcy.sort.insert;
    
    public class ShellSort {
    
    	public static void shellSort(int[] a, int n) {
    		for (int gap = n / 2; gap > 0; gap /= 2) {
    			for (int i = 0; i < gap; i++) {
    				for (int j = i + gap; j < n; j += gap) {
    
    					if (a[j] < a[j - gap]) {
    						int temp = a[j];
    						int k = j - gap;
    						while (k >= 0 && a[k] > temp) {
    
    							a[k + gap] = a[k];
    							k -= gap;
    						}
    						a[k + gap] = temp;
    					}
    
    				}
    			}
    
    		}
    
    	}
    
    	public static void main(String[] args) {
    		int[] a = { 9, 1, 2, 5, 7, 4, 8, 6, 3, 5 };
    		System.out.print("排序前:");
    		for (int i = 0; i < a.length; i++) {
    			System.out.print(a[i] + "  ");
    		}
    		System.out.println();
    		shellSort(a, a.length);
    		System.out.print("排序后:");
    		for (int i = 0; i < a.length; i++) {
    			System.out.print(a[i] + "  ");
    
    		}
    
    	}
    
    }
    
    

    特点:

    • 是插入排序的一种更高效的改进版本,但跳跃导致希尔排序是非稳定排序算法。
    • 只适用于顺序结构
    • 适用于初始记录无序,n较大时的情况

    希尔排序时间复杂度
    希尔排序的时间复杂度与增量(即,步长gap)的选取有关。例如,当增量为1时,希尔排序退化成了直接插入排序,此时的时间复杂度为O(N²),而Hibbard增量的希尔排序的时间复杂度为O(N3/2)。

    展开全文
  • 数据结构排序算法学习之插入排序2

    万次阅读 2019-09-03 19:56:15
    数据结构排序算法之插入排序<二> 2.折半插入排序 基本思想: Java实现: package priv.qcy.sort.insert; public class BinaryInsertSort { public static void binaryInsertSort(int[] a) { int n = a....
  • 数据结构排序算法系列】数据结构八大排序算法

    万次阅读 多人点赞 2016-03-25 22:36:40
    如Windows操作系统的文件管理中会自动对用户创建的文件按照一定的规则排序(这个规则用户可以自定义,默认按照文件名排序)因此熟练掌握各种排序算法是非常重要的,本博客将对数据结构中常见的八大排序算法进行详细...
  • 数据结构排序算法之插入排序<一> 插入排序(Insertion sort) 是一种简单直观且稳定的排序算法。如果有一个已经有序的数据序列,要求在这个已经排好的数据序列中插入一个数,但要求插入后此数据序列仍然有序,...
  • 数据结构排序算法总结

    千次阅读 2019-07-03 20:51:49
    插入排序(Insertion-Sort)的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在实现上,通常采用in-place排序(即...
  • 这篇博客介绍插入排序算法中的三种: 直接插入排序,折半插入排序,希尔排序 一.直接插入排序 1.1 算法思想 直接插入排序是一种最简单的排序算法,其它两种算法都是在直接插入排序算法的基础上的改进。 直接...
  • *改进的冒泡排序算法(有效的降低时间复杂度) *希尔排序(有点模糊)(插入排序的升级版 增加了增量的概念 可以降低时间复杂度) *选择排序 *快速排序 (递归的思想) *堆排序算法(利用二叉树点的储存规则 保证树中...
  • 数据结构排序算法之堆排序

    万次阅读 2016-03-11 16:45:26
    关于堆排序的相关知识非常复杂,不懂得可以参考任意一本数据结构教程,本博客只对堆排序框架及代码进行讲解。 堆排序分三个大的步骤:建初堆,堆调整,堆排序(其中最核心的是堆调整) 1建初堆:从数组中的最后一个非...
  • 冒泡排序(Bubble Sort),是一种计算机科学领域的较简单的排序算法。 它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也...
  • 排序算法之选择排序、插入排序、希尔排序 1.选择排序  选择排序的思想:首先,找到数组中最小的那个元素,其次,将它与数组的第一个元素的位置进行交换,再在剩下的元素中找到最小的元素,与第二个元素的位置进行...
  • 数据结构排序算法—插入排序

    千次阅读 2016-10-11 08:40:56
    插入排序又分为直接插入排序和希尔排序,以下为其两种排序方式的Java实现代码 package com.method; public class InsertMethod { /** * 直接插入排序 * @param arr * @return */ public int[] ...
  • c语言 数据结构 排序算法小结

    千次阅读 2017-12-27 17:49:21
    本题旨在测试各种不同的排序算法在各种数据情况下的表现。各组测试数据特点如下 数据1:只有1个元素; 数据2:11个不相同的整数,测试基本正确性; 数据3:103个随机整数; 数据4:104个随机整数; 数据5:105...
  • 数据结构排序算法综合运用及比较(C语言实现)

    千次阅读 多人点赞 2020-04-29 20:30:09
    排序算法综合及效率比较 实验目的 实验内容 实验要求 实验步骤 概要设计 详细设计 软件测试 设计总结 源程序代码 1.实验目的 (1)熟练掌握几种经典排序的算法(如冒泡排序、选择排序、插入排序、希尔排序、折半...
  • 最近想总结一下学过、用过的排序算法,这篇文章先从整体角度,简单的回顾一下排序算法的分类 排序算法,分为外排序和内排序 外排序:在数据量大的情况下,只能分块排序,但块与块间不能保证有序。外排序用读/写外...
  • public static void main(String[] args) { int a[] = { 2, 8, 7, 1, 3, 5, 6, 4 }; for (int i : a) ... System.out.print("\n排序后 "); for (int i : a) System.out.print(i + " "); }
  •  3、特点:change 如果内层循环完没有 change=true 说明排序完成 以后外层也没必要继续循环了。  */  public static void bubble_sort(int a[] ,int n){  boolean change=true;  for(int i=n-1;i>0&&...
  • 排序算法的归类:总的排序算法分为以下几类:1.插入类排序:如:直接插入排序,折半插入排序,希尔排序2.交换类排序:如:冒泡排序,快速排序,其中冒泡排序应该是计算机专业的学生最为熟悉的一种排序算法了,而快速...
  • 数据结构中,排序算法是一块重头戏,今天主要来总结一下如何用python语言来实现几大主要的排序算法的实现 1.冒泡排序(Bubble Sort) :就像班主任给本班学生排队一样,每次从一列的开头那个同学往下比较,看下前一个...
  • 前言相信学过数据结构的人都知道这个插入排序算法,不多说,今天就总结一下这个算法。注意:测试环境为java8知识点一:插入排序思想 插入排序:将一个记录插入到一个已经排好序的列表中,使得新列表仍然有序。 可能...
  • 折半插入排序是直接插入排序的改进。因为直接插入排序主要分为:查找和插入,折半插入排序就是把直接插入排序的顺序查找改成了折半查找,因此是直接插入排序的改进。 python实现的代码如下: “` 这里写代码片 ...
  • 堆排序也是众多排序算法中比较重要的一种,它属于选择排序的一种。堆可以认为是树的一种,它利用数组的存储方式来存储一个完全二叉树。堆排序就是利用这样的结构进行排序的。以树的结构来说,每一个非终端节点(即...
  • 本文整理了归并排序的大体思路;并用c语言进行了实现;最后将递归过程进行了较为直观的体现
  • 本文较为详细地整理了快速排序的大体思路;并用c语言进行了实现。
  • 数据结构所有排序算法性能分析与比较 通过对数据结构的学习,我发现数据结构中各种排序算法的排序方法,过程,以及时间性能,空间性能都比较容易混淆,现就这些情况做如下总结,希望对大家有所帮助。 起泡排序...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 35,327
精华内容 14,130
关键字:

数据结构排序算法

数据结构 订阅