精华内容
下载资源
问答
  • 快速排序比较次数公式
    万次阅读 多人点赞
    2019-07-23 17:48:40

    个问题其实也没有多么复杂,但是网上这部分内容不多,故总结一下最优与最差比较次数。

    n个元素线性表快速排序,最好情况下比较次数是多少?

    参照严书的方法,以第一位作为标杆。

    ①考虑第一趟排序,无论怎样也要有n-1次比较次数;

    ②如果此时能把数据分成两部分,前一部分与后一部分元素个数相近,那样就是最优的。

    例如,4 1 2 3 5 6 7,经过一趟排序,变成 1 2 3 4 5 6 7 。也就是说,以4为标杆,一趟后分成了两部分,这两部分个数相同或相差 1,那么快排会很优。

    于是,可以想到,最优时,n个数,第一趟分成前⌊(n-1)/2⌋,后⌈(n-1)/2⌉两组,每组也是按照最优的分,设最优是an,于是有:

    an = a⌊(n-1/2)⌋+a⌈(n-1/2)⌉ + n - 1

    比如,n=7时,最优情况就是 a7=a3+a3+6 ,a3=a1+a1+2 ,而显然a1=0。

    于是a3=2,a7=10。

    举 例 4 1 3 2 6 5 7 。第一次4为标杆,一趟后为 2 1 34 6 5 7

    第二趟两边分别以2,6为标杆,这样最好,因为是均分了。

    问题,n=8时,最好排序次数?

    a8=7+a4+a3,a3算的2,a4=3+a1+a2,显然a2=1,于是a4=4,故a8=13

    因此,n=8时,最好情况下比较次数是13。

    举例,4 1 3 2 6 5 7 8 可以数一下

    对于别的情况,参照这个思路即可轻松求比较次数以及举例。

    n个元素线性表快速排序,最坏情况下比较次数是多少?

    这个就容易多了,因为顺序或者逆序时最坏的。
    
    故比较次数,1+2+3……+ n-1 = n(n-1)/2
    

    作者:XueWang1
    来源:CSDN
    原文:https://blog.csdn.net/XueWang1/article/details/78118758

    更多相关内容
  • 快速排序算法的三种方式及其优化java实现1、快速排序算法的简绍2、快速排序的基本思想3、快速排序左右指针法图解4、快速排序左右指针法核心代码5...算法的时间复杂度11、快速排序的稳定性11、快速排序与其他排序的比较...

    1、快速排序算法的简绍

    快速排序算法(QuickSort)又称为划分交换排序,快速排序是对冒泡排序的一种改进方法,在冒泡排序中,记录关键字的比较和交换是在相邻记录之间进行的,记录每次交换只能上移或下移一个相邻位置,因而总的比较和移动次数较多;在快速排序中,记录关键字的比较和交换是从两端向中间进行的,关键字较大的记录一次就能交换到后面的单元,关键字较小的记录一次就能交换到前面的单元(升序),记录每次移动的距离较远,因而总的比较和移动次数较少,速度很快,所以被称为快速排序。

    2、快速排序的基本思想

    首先当前无序区data[low…high]中任取一个记录作为排序比较的基准(不妨设为x,其位置为i),用次基准将当前无序区划分为两个较小的无序区:data[low…i-1]和data[i+1…high],并使左边的无序区中所有的记录的关键字均小于等于基准的关键字,右边的无序区中所有的记录的关键字均大于等于基准的关键字,即data[low…i-1]中的关键字<=x.key<=data[i+1…high]中的关键字,这个过程称为一趟快速排序(或一次划分)。当data[low…i-1]和data[i+1…high]均非空时,分别对它们进行上诉划分过程,直到所有无序区中的记录均已排序好为止。

    3、快速排序左右指针法图解

    1、选取一个关键字(key)作为枢轴,一般取整组记录的第一个数/最后一个,这里采用选取序列最后一个数为枢轴。 设置两个变量left = 0;right = N - 1。
    2、 从left一直向后走,直到找到一个大于key的值,right从后至前,直至找到一个小于key的值,然后交换这两个数。
    3、重复第三步,一直往后找,直到left和right相遇,这时将key放置left的位置即可。
    在这里插入图片描述

    4、快速排序左右指针法核心代码

    
    public class Quick_Sort4 {
    	public static void quickSort(int[] arrays, int low, int hi) {
    
    		if (low < hi) {
    
    			// 求每次分治的分割线
    			int divideIndex = getDivideIndex(arrays, low, hi);
    			// 再递归分别对分割的俩个子数组进行递归排序
    			quickSort(arrays, low, divideIndex - 1);
    			quickSort(arrays, divideIndex + 1, hi);
    
    		}
    
    	}
    
    	public static int getDivideIndex(int[] arrays, int low, int hi) {
    		// 设定arrays[low]为基准值,从右到左移动hi,找到大于第一个大于基准值的数字。
    		// 从左向右移动low指针,找到第一个小于基准值的数,交换low和high位置上的值
    		// 直到low=high的时候,将基准值填入arrays[low]
    		int baseValue = arrays[low];
    		int oldLow = low;
    		while (low < hi) {
    			while (low < hi && arrays[hi] >= baseValue) {
    
    				hi--;
    			}
    
    			while (low < hi && arrays[low] <= baseValue) {
    				low++;
    			}
    			if (low < hi) {
    				swap(arrays, low, hi);
    			}
    		}
    
    		if (low == hi) {
    			arrays[oldLow] = arrays[low];
    			arrays[low] = baseValue;
    
    		}
    		return low;
    	}
    
    	public static void swap(int[] arrays, int low, int high) {
    
    		int temp = 0;
    		temp = arrays[low];
    		arrays[low] = arrays[high];
    		arrays[high] = temp;
    
    	}
    
    	public static void main(String[] args) {
    		// 显示排序前的序列
    
    		int[] arrays = { 36, 25, 48, 12, 65, 25, 43, 58, 76, 32 };
    		System.out.println("快速排序之左右指针排序前:");
    		for (int data : arrays) {
    			System.out.print(data + " ");
    		}
    		System.out.println();
    		getDivideIndex(arrays, 0, arrays.length - 1);
    		System.out.println("第一趟排序结果:");
    		for (int data : arrays) {
    			System.out.print(data + " ");
    		}
    		System.out.println();
    		quickSort(arrays, 0, arrays.length - 1);
    		System.out.println("快速排序之左右指针排序后:");
    		for (int data : arrays) {
    			System.out.print(data + " ");
    		}
    	}
    
    }
    

    运行结果:
    在这里插入图片描述

    5、快速排序挖坑法图解

    1、选取一个关键字(key)作为枢轴,一般取整组记录的第一个数/最后一个,这里采用选取序 列最后一个数为枢轴,也是初始的坑位。
    2、设置两个变量left = 0;right = N - 1;
    3、从left一直向后走,直到找到一个大于key的值,然后将该数放入坑中,坑位变成了array[left]。
    4、right一直向前走,直到找到一个小于key的值,然后将该数放入坑中,坑位变成了array[right]。
    5、重复3和4的步骤,直到left和right相遇,然后将key放入最后一个坑位。
    6、当left >= right时,将key放入最后一个坑,就完成了一次排序。
    注意:left走的时候right是不动的,反之亦然。因为left先走,所有最后一个坑肯定在array[right]。
    在这里插入图片描述

    6、快速排序挖坑法核心代码

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    运行结果:
    在这里插入图片描述
    在这里插入图片描述

    7、快速排序前后指针法图解

    定义变量cur指向序列的开头,定义变量pre指向cur的前一个位置。
    当array[cur] < key时,cur和pre同时往后走,如果array[cur]>key,cur往后走,pre留在大于key的数值前一个位置。
    当array[cur]再次 < key时,交换array[cur]和array[pre]。
    通俗一点就是,在没找到大于key值前,pre永远紧跟cur,遇到大的两者之间机会拉开差距,中间差的肯定是连续的大于key的值,当再次遇到小于key的值时,交换两个下标对应的值就好了。
    在这里插入图片描述

    8、快速排序前后指针法核心代码

    
    public class Quick_Sort3 {
    	public static void main(String[] args) {
    
    		int[] arrays = { 36, 25, 48, 12, 65, 25, 43, 58, 76, 32 };
    		System.out.println("快速排序之左右指针排序前:");
    		for (int data : arrays) {
    			System.out.print(data + " ");
    		}
    		System.out.println();
    		partion(arrays, 0, arrays.length - 1);
    		System.out.println("第一趟排序结果:");
    		for (int data : arrays) {
    			System.out.print(data + " ");
    		}
    		System.out.println();
    		quickSort(arrays, 0, arrays.length - 1);
    		System.out.println("快速排序之左右指针排序后:");
    		for (int data : arrays) {
    			System.out.print(data + " ");
    		}
    
    	}
    
    	static int partion(int arr[], int left, int right) {
    		int pCur = left;
    		int prev = pCur - 1;
    		int key = arr[right];
    		while (pCur <= right) {
    			if (arr[pCur] <= key && (++prev) != pCur)
    				swap(arr, prev, pCur);
    			pCur++;
    		}
    		return prev;
    	}
    
    	static void quickSort(int arr[], int left, int right) {
    		if (left < right) {
    			int mid = partion(arr, left, right);
    			quickSort(arr, left, mid - 1);
    			quickSort(arr, mid + 1, right);
    		}
    
    	}
    
    	public static void swap(int[] arrays, int low, int high) {
    
    		int temp = 0;
    		temp = arrays[low];
    		arrays[low] = arrays[high];
    		arrays[high] = temp;
    
    	}
    }
    
    

    运行结果:
    在这里插入图片描述

    9、快速排序基准点优化及其核心代码

    对于基准点的优化一般有三种:固定切分,随机切分和三数取中法。固定切分的效率并不是太好,随机切分是常用的一种切分,效率比较高,最坏情况下时间复杂度有可能为O(N^2)。对于三数取中选择基准点是最理想的一种。
    下面给出三个数取中间数的算法实现:

    
    public class Quick_Sort {
    	public static void quickSort(int[] a, int low, int high) {
    		if (low >= high) {
    			return;
    		}
    		// 进行第一轮排序获取分割点
    		int index = partSort(a, low, high);
    		// 排序前半部分
    		quickSort(a, low, index - 1);
    		// 排序后半部分
    		quickSort(a, index + 1, high);
    	}
    
    	public static int partSort(int[] a, int low, int high) {
    		// 调用三数取中
    		int mid = Quick_Sort.getMid(a, low, high);
    		swap(mid, a[high]);
    		int key = a[high];
    		while (low < high) {
    			// 从前半部分向后扫描
    			while (low < high && a[low] <= key) {
    				++low;
    			}
    			a[high] = a[low];
    			// 从后半部分向前扫描
    			while (low < high && a[high] >= key) {
    				--high;
    			}
    			a[low] = a[high];
    		}
    		// 最后把基准点存入
    		a[high] = key;
    		return low;
    	}
    
    	public static int getMid(int[] a, int low, int high) {
    		int mid = low + (high - low) / 2;
    		// 下面两步保证了a[high]是最大的
    		if (a[mid] > a[high]) {
    			swap(a[mid], a[high]);
    		}
    		if (a[low] > a[high]) {
    			swap(a[low], a[high]);
    		}
    		// 将a[low]和a[mid]比较,让较小的在啊[low]的位置
    		if (a[mid] > a[low]) {
    			swap(a[mid], a[low]);
    		}
    		int key = a[low];
    		return key;
    	}
    
    	public static void swap(int a, int b) {
    		int temp = a;
    		a = b;
    		b = temp;
    	}
    
    	public static void main(String[] args) {
    		// 显示排序前的序列
    		int[] array = { 36, 25, 48, 12, 65, 25, 43, 58, 76, 32 };
    		System.out.print("排序前:");
    		for (int data : array) {
    			System.out.print(data + " ");
    		}
    		System.out.println();
    		// 显示排序后的序列
    		Quick_Sort.quickSort(array, 0, 9);
    		System.out.print("排序后:");
    		for (int data : array) {
    			System.out.print(data + " ");
    		}
    	}
    }
    
    

    运行结果:
    在这里插入图片描述

    10、快速排序算法的时间复杂度

    10.1最优情况下
    快速排序最优的情况就是每一次取到的元素都刚好平分整个数组;
    此时的时间复杂度公式则为:T[n] = 2T[n/2] + f(n);T[n/2]为平分后的子数组的时间复杂度,f[n] 为平分这个数组时所花的时间;
    下面来推算下,在最优的情况下快速排序时间复杂度的计算(用迭代法):
    T[n] = 2T[n/2] + n ----------------第一次递归
    令:n = n/2 = 2 { 2 T[n/4] + (n/2) } + n ----------------第二次递归
    = 2^2 T[ n/ (2^2) ] + 2n
    令:n = n/(2^2) = 2^2 { 2 T[n/ (2^3) ] + n/(2^2)} + 2n ----------------第三次递归
    = 2^3 T[ n/ (2^3) ] + 3n

    令:n = n/( 2^(m-1) ) = 2^m T[1] + mn ----------------第m次递归(m次后结束)
    当最后平分的不能再平分时,也就是说把公式一直往下跌倒,到最后得到T[1]时,说明这个公式已经迭代完了(T[1]是常量了)。
    得到:T[n/ (2^m) ] = T[1] ===>> n = 2^m ====>> m = logn;
    T[n] = 2^m T[1] + mn ;其中m = logn;
    T[n] = 2^(logn) T[1] + nlogn = n T[1] + nlogn = n + nlogn ;其中n为元素个数
    又因为当n >= 2时:nlogn >= n (也就是logn > 1),所以取后面的 nlogn;
    综上所述:快速排序最优的情况下时间复杂度为:O( nlogn )
    10.2最差情况下
    最差的情况就是每一次取到的元素就是数组中最小/最大的,这种情况其实就是冒泡排序了(每一次都排好一个元素的顺序)
    这种情况时间复杂度就好计算了,就是冒泡排序的时间复杂度:T[n] = n * (n-1) = n^2 + n;
    综上所述:快速排序最差的情况下时间复杂度为:O( n^2 )
    10.3平均时间复杂度
    快速排序的平均时间复杂度是:O(nlogn)

    11、快速排序的稳定性

    因为在快速排序的时候,即使待排序元素可基数相等也需要移动待排序元素的位置使得有序,所以快速排序是不稳定的

    11、快速排序与其他排序的比较

    在这里插入图片描述

    展开全文
  • 内部排序算法比较

    2015-06-14 19:26:54
    1)比较范围:直接插入排序、冒泡法排序、简单选择排序、快速排序1(自己实现)、快速排序2(调用STL)、归并排序。 2)比较指标:a)关键字操作次数比较次数和移动次数之和),b)排序时间。每个指标采用多次重复...
  • 请问各位大佬,快速排序比较次数(最优),有计算公式吗</p>
  • 归并排序与快速排序背后的秘密

    千次阅读 2021-11-03 22:30:23
    到处说归并排序采用了分而治之的方法,所以效率比冒泡排序高: 将一个大问题分解成一些小问题,分而治之,各个击破… 但这些诠释基本都缺少了最关键的点,即效率必须随规模非...只要记住,基于比较排序效率随着规

    排序问题一直都是各类考试和面试的热门问题,在读了《算法之美》第三章后,就发觉其实它在各个场合都很热门。其实我们一直在不断地排序,无论我们做什么。

    说回具体的考试面试中的排序,很多人都能用各种语言写出各种排序算法,但很少有人会去思考这些算法步骤背后的秘密,那么本文来抛块砖,说说归并排序和快速排序。

    到处都讲归并排序采用分治方法,所以效率比冒泡排序高:

    将一个大问题分解成一些小问题,分而治之,各个击破…

    但这些诠释都缺了关键点,即 效率必须随规模非线性增加的场景,分治才有意义,如果是线性系统,比如计数,分时调度,分治反而增加额外开销。

    只要记住,基于比较的排序效率随着规模下凸增加,就足以理解分治方法了。这很容易理解,每次比较涉及两个数而不是一个,这意味着比较的次数比参与比较的数字规模更大。

    把规模缩小一倍,排序效率便不止提升一倍,这是分治策略的基础。排序两个子数组(相当于降维)然后再合并的效率一定比直接排序一个大数组效率高,在此基础之上再看归并排序的时间复杂度。

    设待排序数组大小为 n n n,使用冒泡排序算法,需要比较的次数为:

    T ( n ) = ( n − 1 ) + ( n − 2 ) + . . . + 1 = n ( n − 1 ) 2 T(n)=(n-1)+(n-2)+...+1=\dfrac{n(n-1)}{2} T(n)=(n1)+(n2)+...+1=2n(n1)

    按照时间复杂度的定义忽略小阶项, T ( n ) T(n) T(n)可以等价为 n 2 n^2 n2

    现在将数组均拆成两半,每一半分别冒泡排序,然后合并两个有序子数组,设 T i T_i Ti为将数组均拆成 i i i个子数组时的排序时间复杂度度量,则:

    T 2 ( n ) = 2 ( n 2 ) 2 + n T_2(n)=2(\dfrac{n}{2})^2+n T2(n)=2(2n)2+n

    具体采用什么算法排序子数组无所谓,只是为了演示经过 log ⁡ n \log n logn次均拆之后,子数组将仅剩下一个元素,整个归并排序只需要 log ⁡ n \log n logn层的子数组合并即可,而每层若干合并的总比较次数为 n n n

    继续均拆,随着子数组变小,排序涉及的比较次数指数递减。

    将大小为 i i i的子数组逐级合并为大小为 2 i 2i 2i的子数组,每次合并操作涉及的操作次数固定为 n n n,对于不同的 i i i,总比较次数分别为:

    T 4 ( n ) = 4 ( n 4 ) 2 + 2 n T_4(n)=4(\dfrac{n}{4})^2+2n T4(n)=4(4n)2+2n

    T 8 ( n ) = 8 ( n 8 ) 2 + 3 n T_8(n)=8(\dfrac{n}{8})^2+3n T8(n)=8(8n)2+3n

    可以期望,子数组大小肯定会递减到1,合并两个大小为1的子数组仅需一次比较,此时:

    T n ( n ) = n ( n n ) 2 + n log ⁡ 2 n = n log ⁡ 2 n + n T_n(n)=n(\dfrac{n}{n})^2+n\log_2n=n\log_2n+n Tn(n)=n(nn)2+nlog2n=nlog2n+n

    这就是归并排序的时间复杂度 O ( n log ⁡ 2 n ) O(n\log_2n) O(nlog2n)。从这个过程发现无论最好,最坏,平均,归并排序的时间复杂度不变。

    这是一个非常清晰的过程,但并没有回答一个核心问题,与 O ( n 2 ) O(n^2) O(n2)的冒泡排序相比,归并排序到底省掉了哪些比较,从而让时间复杂度减少到 O ( log ⁡ n ) O(\log n) O(logn)

    看一下合并两个已排序数组的过程,请看下图:

    在这里插入图片描述
    两个有序子数组中两组数字,其中一个的头和另一个的尾,在一次合并中不会同时参与比较,减少的比较操作正是来源于此,经过不断分治,归并排序实际上就是一个递归合并的过程。

    若仅仅考虑时间复杂度,归并排序可以证明是最高效的排序算法。 O ( n log ⁡ n ) O(n\log n) O(nlogn)是比较排序算法绕不过的极限,而这很容易证明。

    n n n个数字有 n ! n! n!种序列,升序(或者降序)是其中一种。 n n n个数字中两数经过一次比较可确定两数的相对位置,那么就剩下 n ! 2 \dfrac{n!}{2} 2n!种序列,在 n ! 2 \dfrac{n!}{2} 2n!种序列中,再比较一次,就会剩下 n ! 4 \dfrac{n!}{4} 4n!种序列,以此类推,现在问,至少比较多少次能只剩下1种序列,设比较 x x x次可达,那么:

    2 x ≥ n ! 2^x\geq n! 2xn!

    两边取对数,解 x x x,即:

    x ≥ log ⁡ 2 n ! x\geq\log_2n! xlog2n!

    不等号右边用斯特林公式近似,得到比较排序的时间复杂度极限 O ( n log ⁡ n ) O(n \log n) O(nlogn),而归并排序就是比较排序的一种,它的最差情况都能达到 O ( n log ⁡ n ) O(n\log n) O(nlogn),这无疑是最棒的算法。

    遗憾的是,它的空间复杂度为 O ( n ) O(n) O(n),在实际实现中,随着 n n n的增加,排序操作需要大量的内存,这非常不利于cache亲和,而快速排序的原地排序优化可以避免空间问题,这就是快速排序胜出的原因。

    那么快速排序为什么可以胜任?它的时间复杂度表现如何呢?

    很著名的一篇文章:
    数学之美番外篇:快排为什么那样快
    我觉得小题大做了,没那么复杂,快速排序核心就是随机,如果每次都能抓到剩余子数组的中位数,每次都是均拆,考虑到每拆到一层 i i i,该层比较总和为 n − 1 − i n-1-i n1i,总的操作次数是可以算出来的:

    T = ∑ i = 0 log ⁡ n ( n − 1 − i ) T=\sum\limits_{i=0}^{\log n}(n-1-i) T=i=0logn(n1i)

    在最好的情况下,快速排序和归并排序时间复杂度均一致,均为 O ( n log ⁡ n ) O(n\log n) O(nlogn)

    但每次都抓住中位数几乎不可能, n n n个数选一个,概率均为 1 n \dfrac{1}{n} n1,所有子数组均能选中中位数概率可想而知。

    无论是否抓到了中位数,快速排序每一步总是可以将子数组分成两个部分,相比 O ( n 2 ) O(n^2) O(n2)的冒泡排序,快速排序减少比较次数从而降低时间复杂度的秘密在于,在某层被拆开的两部分之间,直到排序结束,均不会发生任何比较。

    既然最好情况几乎不可达,最差时间复杂度又是不可接受的 O ( n 2 ) O(n^2) O(n2),问题是,平均情况下,距离最好情况,差多少呢?如果平均情况接近最好情况,也不错。

    快速排序的平均情况显然也是 O ( n log ⁡ n ) O(n\log n) O(nlogn),若非如此,也就没有本文,问题是不光要把它推导出来,还要能直观地描绘出来。

    平均情况体现在所有排序可能性最接近所有可能性平均数的地方,下图展示了最坏情况到最好情况的单调过渡:
    在这里插入图片描述
    退化成链表的二叉树高度为 h = n h=n h=n,它逐渐变矮,直到满二叉树最矮 h = log ⁡ n h=\log n h=logn,这个过程中, h h h越小,可以构造的二叉树越多,可能性分布越密集。而每一棵二叉树都表示一种可能的快速排序,所有可能的平均数位置必然接近密度最大处,显然 h a v g h_{avg} havg会很小:
    在这里插入图片描述
    有了直观的感受,推导出来的平均时间复杂度就容易理解了。来自wiki,设 T ( n ) T(n) T(n)为排序 n n n个数所需的操作:

    T ( n ) = 1 n ∑ i = 0 n − 1 ( T ( i ) + T ( n − i − 1 ) ) + ( n − 1 ) = 1.39 n log ⁡ n T(n)=\dfrac{1}{n}\sum\limits_{i=0}^{n-1}(T(i)+T(n-i-1))+(n-1)=1.39n\log n T(n)=n1i=0n1(T(i)+T(ni1))+(n1)=1.39nlogn

    其中 ( n − 1 ) (n-1) (n1)为每一次排列子数组固定的比较操作。这就定量化了上图中平均值的位置,偏离最好情况39%处,非常近。

    这就是快速排序为什么在统计意义上很快的原因。这是随机的胜利,虽然达到最好情况概率非常低,但统计意义上绝大多数情况离最好情况都不太远,这是随机的魅力!

    相比之下,归并排序显得有些呆板。

    随机似乎与理性相反,但在某些问题上,它却比最好的确定性算法更优秀。

    浙江温州皮鞋湿,下雨进水不会胖。

    展开全文
  • 排序算法——稳定性、比较次数、交换次数

    万次阅读 多人点赞 2017-10-29 22:16:06
    在学习排序算法时,出于效率考虑,经常容易看到算法的稳定性、比较次数及交换次数研究。特别是考试或者公司笔试题,经常出现这样的题目。由于排序算法有很多种,平时提出大家才能说出个大概,但真要考查这些细节,...

     本文转自:无名大盗——http://blog.csdn.net/dreamer2020/article/details/8740244

    在学习排序算法时,出于效率考虑,经常容易看到算法的稳定性、比较次数及交换次数研究。特别是考试或者公司笔试题,经常出现这样的题目。由于排序算法有很多种,平时提出大家才能说出个大概,但真要考查这些细节,估计很多人都说不准确。博主下决心写此文章,彻底探查清楚这些问题,与大家共享之。

            首先说明稳定性是指相同元素在排序后相对位置保持不变。个人感觉稳定性的含义在于更广泛情形下,排序元素通常具有多个键值,即可以按照多个标准来排序。稳定性则保证了按照一个键排序的结果可以为第二个键所用。举个例子,对于学生的课程成绩,通常会和学号、姓名列在一起,先按照学生学号排序,然后再根据成绩从高到低,这样,相同分数的学生则是按照学号排名。

            其次是关于比较次数和交换次数,通常用于算法效率分析。基于比较的排序算法其性能最好是nlog(n)。因而,不同的优化都是向这个边界靠近。且不同的算法也有不同的应用场景,不完全是看复杂度。

            下面逐个分析常见排序算法。

    一、冒泡排序

            冒泡排序的原理是将相邻元素比较,小的往左移动,大的往右,整个过程就像是水中气泡上浮。在相邻两个元素的比较中,如果相等,则没有必要交换。这一点,保证了冒泡排序的稳定性。无论相等的元素之前处于什么位置,在冒泡的效果下, 最终会相邻,只要相等元素不交换,就不会改变相对位置。所以冒泡排序是稳定的。

            对于n个元素,相邻元素均要比较,共有(n-1)次。经过一回合冒泡过程后,最大元素沉淀到最右位置。第二回合, 只剩下(n-1)个元素,只需要比较(n-2)次。依次类推,其他比较次数为(n-3),......,2,1. 所以总共比较次数为n(n-1)/2,而且是固定为这个数目.

           至于交换次数,这个取决于初始序列的逆序数。对于数组A[1,...,n],如果对于i<j有A[i]>A[j],则称(A[i],A[j])是一个逆序对,序列中逆序对的个数称为逆序数。

            冒泡排序每次交换,只改变了相邻两元素的位置,不影响和其他元素之间的逆序关系,因而,逆序数只减1。所以,冒泡排序交换次数等于初始序列的逆序数。

    二、选择排序

            选择排序的原理是每回合找出最小元素,然后交换到前面位置。

            选择排序是不稳定的排序算法,不稳定主要产生于交换。交换过程可能改变相同元素的相对位置,举个例子,序列(5,8,5,1),最小数是1,第一次交换,得到(1,8,5,5),元素5相对位置已经发生变化。

            下面是比较次数。对于n个元素的序列,找出最小元素需要比较(n-1)次。第一回合后,序列只剩下(n-1)个元素,下一次找最小元素还需要(n-2)次比较。最后直到2个元素需要比较1次。所以最后比较次数总共为(n-1)+(n-2)+...+1=n(n-1)/2,且固定不变。

            每一回合最多交换一次,有(n-1)回合,所以最多交换次数为(n-1)。

    三、插入排序

            插入排序基本原理是假定前面i个元素已经排好,接下来将第(i+1)个元素插入到前面的序列中,保证有序。循环插入所有元素,即完成排序。

            插入第(i+1)元素如果是从后往前扫描,寻找比其小的元素,这叫作直接插入排序。如果是使用二分查找判断新元素位置,则叫作二分插入排序。两种插入排序都是稳定的。对于直接插入排序,新来元素位置是通过从后往前比较(寻找比其小或相等元素,假设是a[j])来确定的,将新元素放在a[j]后即可,相等可以保证稳定性。对于二分插入排序,可以通过修改二分查找来保证稳定性,如下代码所示,但x[mid] == temp时,low指针右移,该操作可以保证相等元素不会被放到前面。

    [cpp]  view plain  copy
    1. while (low <= high)     
    2.    {     
    3.     mid = (low + high) / 2;     
    4.     if (x[mid] <= temp)     
    5.     {     
    6.      low = mid + 1;     
    7.     }     
    8.     else    
    9.     {     
    10.      high = mid - 1;     
    11.     }   

           直接插入排序每回合的比较次数和元素移动次数等于其原始位置和插入位置之间的偏移。最好情况下(有序),需要比较(n-1)次,移动0次;最差情况下,需要比较1+2+...+(n-1)=n(n-1)/2次,移动n(n-1)/2次。在程序实现上,通常会用一个临时变量(如temp)保存待插入元素,最后又将temp移动到相应位置上,因而在很多教材上第回合插入会多2次移动操作,本文在此指出这一点。从上面的分析可以发现,直接插入排序对于基本有序的初始序列,有较好效果,无论是比较次数还是移动次数,都很少。

           二分插入排序仅仅是加快了查找这一过程,即减少了元素比较次数,对于m个有序的序列,二分查找最坏情况下比较次数为1+log(m)。因而,在插入排序中,元素比较次数为(n-1)+log(1*2*...*(n-1)),在初始序列杂乱无章的情形下,其平均查找性能较好。

    四、归并排序

           归并的基本思想是合并多路有序数组,通常我们考虑两路归并算法。

           归并排序是稳定的,这是因为,在进行多路归并时,如果各个序列当前元素均相等,可以令排在前面的子序列的元素先处理,不会打乱相等元素的顺序。

           考虑元素比较次数,两个长度分别为m和n的有序数组,每次比较处理一个元素,因而合并的最多比较次数为(m+n-1),最少比较次数为min(m,n)。对于两路归并,序列都是两两合并的。不妨假设元素个数为n=2^h,

           第一次归并:合并两个长度为1的数组,总共有n/2个合并,比较次数为n/2。

           第二次归并:合并两个长度为2的数组,最少比较次数是2,最多是3,总共有n/4次,比较次数是(2~3)n/4。

           第三次归并:合并两个长度为4的数组,最少比较次数是4,最多是7,总共有n/8次合并,比较次数是(4-7)n/8。

           第k次归并:合并两个长度为2^(k-1)的数组,最少比较次数是2^(k-1),最多是2^k-1,总共合并n/(2^k)次,比较次数是[2^(k-1)~(2^k-1)](n/2^k)=n/2~n(1-1/2^k)。

           按照这样的思路,可以估算比较次数下界为n/2*h=nlog2(n)/2。上界为n[h-(1/2+1/4+1/8+...+1/2^h)]=n[h-(1-1/2^h)]=nlog2(n)-n+1。

           综上所述,归并排序比较次数为nlog2(n)/2~nlog2(n)-n+1。

           归并排序引入了一个与初始序列长度相同的数组来存储合并后的结果,因而不涉及交换。

    五、快速排序

            快速排序的基本思想是分治。

            快排是不稳定的,关键在于划分过程。现有的几种划分过程,基本都是分两个指针从左右同时扫描,然后交换元素,交换过程很容易打乱元素位置。

            元素比较次数,也就是其复杂性分析。理想情况下,快速排序每次划分都将原始序列划分为两个等长的子序列。所以其比较次数为T(n)=2T(n/2)+n,所以其平均期望时间为nlog(n)。但在最坏情况下,即序列有序情形下,每次划分只能分出一个元素,因而总共需要(n-1)次划分,总的比较次数为(n-1)+(n-2)+...+1=n(n-1)/2,即退化为O(n^2).

            元素交换次数取决于序列,不知道怎么给出准确分析,只好略过。

    六、堆排序

           堆排序的基本思想是对序列建立最小堆,然后依次取堆顶元素、删除和调整堆。

           堆排序是不稳定的,堆的删除操作直接将最后一个元素提到堆顶,然后再调整,该操作容易改变相同元素的顺序。

           比较主要发生在堆调整过程中,堆排序可以分解为两个过程,一是建堆,二是移除元素。建堆过程中,自底而上,每个元素和其孩子结点比较,找最大元素,并调整。如果元素是从大到小排列的,即已经成堆的情形下,对于完全树,其比较次数为(n-1)。在不满足堆的前提下,还会发生递归调用,比较次数更多。调整过程中,把最后一个元素提到堆顶后,需要重新调整堆,此时还是需要比较和调整。因而,初始有序的序列,其比较次数不会有太大变化(此处有疑问,无法论证清楚)。所以,堆排序的比较次数较稳定的靠近nlog(n)。

           堆调整过程中会发生交换,交换次数跟数据位置相关,目前没有见到有分析清楚这个的。

    七、其他排序算法

           除上述外,还有许多其他排序算法,如希尔排序、基数排序、桶排序等。

           希尔排序将序列划分成多个子序列,先对子序列分别排序,然后减少子序列个数,重复该过程。在开始时,数据规模较小,到最后,数据多数有序,采用直接插入排序,整体来说,取得比较好的效果。

           基数排序根据多个键值对序列进行分配,属于分配类算法。

    最后,本文分析可以总结如下:



    稳定性比较次数交换次数空间复杂性适用场景
    冒泡排序稳定n(n-1)/2逆序数O(1)
    选择排序不稳定n(n-1)/20~(n-1)O(1)
    插入排序稳定最好为(n-1),最差为n(n-1)/2最好为0,最差为n(n-1)/2O(1)初始序列大量有序
    归并排序稳定nlog2(n)/2~nlog2(n)-n+1
    O(n)大量数据排序,外排序
    快速排序不稳定nlog(n),最差为n(n-1)/2无法分析log(n)
    堆排序 不稳定 nlog(n),和初始顺序关系不大 无法分析 O(1)
    展开全文
  • 各种排序算法的比较次数

    万次阅读 多人点赞 2015-08-08 21:16:27
    借助比较的排序每次比较贡献O(1)的复杂度 插入排序  最少n-1 最多n(n-1)/2 ...快速排序  int partition(int *arr , int low , int high)  {   int pivo = arr[low];   
  • 尽管这两种排序算法的时间复杂度都是 O(nlogn),甚至堆排序比快速排序的时间复杂度还要稳定,但是,在实际的软件开发中,快速排序的性能要比堆排序好,这是为什么呢? 现在,你可能还无法回答,甚至对问题本身还...
  • 冒泡排序和快排的交换次数

    千次阅读 2017-12-21 17:39:59
    数据结构实验之排序二:交换...冒泡排序和快速排序都是基于"交换"进行的排序方法,你的任务是对题目给定的N个(长整型范围内的)整数从小到大排序,输出用冒泡和快排对这N个数排序分别需要进行的数据交换次数。 Inpu
  • 堆和堆排序:为什么说堆排序没有快速排序

    千次阅读 多人点赞 2019-01-22 10:23:50
    ------ 本文是学习算法的笔记,《数据结构与算法之美》,极客时间的课程 ------ 我们今天讲另外一种特殊的树,“堆(Heap)”。...尽管这两种排序算法的时间复杂度都是O(nlogn),甚至堆排序比快速排序的时间...
  • 第二大节点,以此类推,直到叶子节点被删除。这里我也画了一个分解图。不过这种方法有点问题,就是最后堆化出来的堆并不满足完全二叉树的特性。public class
  • 排序是算法中最基础的问题之一,经典的排序算法是前人不断总结得到的,基于比较的方法是比较直观的方式,主要存在插入法排序、堆排序、增量排序、归并排序、快速排序,每一种排序算法都有自己的优缺点,比如插入法...
  • 排序——快速排序(Quick sort)

    万次阅读 多人点赞 2020-02-09 20:12:34
    概况 快速排序(Quick sort)是对冒泡排序的一种改进。快速排序由C. A. R.... 算法思路 ...通过一趟排序将要排序的数据分割成独立的两部分,其中一...快速排序算法通过多次比较和交换来实现排序,其排序流程如下: ......
  • 冒泡排序到快速排序做的那些优化

    千次阅读 2017-10-28 07:39:51
    彻底弄明白常用的排序算法的基本思想,算法的时间和空间复杂度,以及如何选择这些排序算法,确定要解决的问题的最佳排序算法,我们先总结下冒泡排序和其改进后的快速排序这两个算法,后面再继续总结插入排序、希尔...
  • 快速排序练习题

    千次阅读 2020-09-09 20:11:13
    //其中从1到i是小于x的元素,i+1到r是大于x的元素 一、快速排序的描述 1、说明Partion在数组A=,19,9,5,12,8,7,4,21,2,6,11>上操作的过程。 解:其始,p = 1,r = 12,x = 11,i = 0(此时有0个小于11的...
  • 各种排序最好最坏的比较次数

    万次阅读 多人点赞 2014-12-07 11:12:38
    都不知道怎么回答,各种排序说的也太多了,这里讲几种简单的吧,希望对你有帮助! 比如n个顺序存储元素进行排序,a[0]做...1 直接插入排序比较次数 最少n-1次;最多(n-1)(n+2)/2 移动次数 最少0; 最多(n-1)(n+4)/2
  • 用分治可以实现另一种排序方法,快速排序。把n个元素分为三段,left, middle, right,其中middle段仅有一个元素,left段中的元素都不大于中间段的元素,right段的元素都不小于middle段的元素。middle的元素称为支点。...
  • 快速排序 1.挖坑法 2.左右指针法 3.前后指针法 四.归并排序 (一).归并排序 1.思路: 2.代码: 3.对文件中的数据排序: 五.非递归的归并排序与快排 六.计数排序 (一).计数排序 1.思路: 2.代码: 3....
  • 几种排序的总结(包括含有重复数字的快速排序

    千次阅读 多人点赞 2020-07-05 21:25:46
    它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换...
  • 排序算法之 冒泡排序和快速排序

    千次阅读 2018-09-11 10:27:10
    冒泡排序是一种简单的排序方法,它的基本思想是:通过相邻两个元素之间的比较和交换,使较大的元素逐渐从前面移向后面(升序),就像水底下的气泡一样逐渐向上冒泡,所以被称为“冒泡”排序。冒泡排序的最坏时间...
  • 快速排序在C++的泛型排序中,拷贝对象需要很大的开销,而比较对象常常是相对省时的(编译器的自动优化)。在这种情况下,如果我们能够使用更少的数据移动,那么有理由让一个算法多使用一些比较。而快速排序...
  • 逆序数——冒泡排序的交换次数

    千次阅读 2020-03-24 12:35:33
    给定一个1~n的排列a,..,an-,求对这个数列进行冒泡排序所需要的交换次数(冒泡排序是每次找到满足a>a+t的i,并交换a;和a++t,直到这样的i不存在为止的算法)。 限制条件 ●1≤n≤100000 输入 n=4,a={3,1,4,2} ...
  • 有助于目录的生成如何改变文本的样式插入链接与图片如何插入一段漂亮的代码片生成一个适合你的列表创建一个表格设定内容居中、居左、居右...列表如何创建一个注脚注释也是必不可少的KaTeX数学公式新的甘特图功能...
  • 在Excel中快速查看所有工作表公式 在Excel中设置行间距 怎样同时改变多行行高 快速换行 让文本换行 在Excel中行列快速转换 将原有列中的内容倒置过来 快速回到A1单元格 复制粘贴中回车键的妙用 一次选中批注单元格 ...
  • 快速排序练习题(Java)

    千次阅读 2019-07-24 15:56:46
    快速排序 1、算法实现 快速排序的核心方法:partition,它首先随机选择一个数,然后以这个数为轴,小于它的放在它前面,大于它的放在后面,然后放回这个轴数的排序位置。有很多种实现方法,选择我比较熟悉的一种: ...
  • 快速排序的时间复杂度与空间复杂度

    万次阅读 多人点赞 2019-10-13 11:59:56
    我们来分析一下快速排序法的性能。 快速排序的时间性能取决于快速排序递归的深度, 可以用递归树来描述递归算法的执行情况。 如图9‐9‐7所示,它是{50,10,90,30, 70,40,80,60,20}在快速排序过程中的递归过程。...
  • 最坏情况比较次数

    千次阅读 2019-07-26 18:01:00
    在顺序表中: 顺序查找法:最坏情况下...快速排序: 最坏情况下比较n(n-1)/2次 冒泡排序: 最坏情况下比较n(n-1)/2次 堆排序: 最坏情况下比较nlog2n 转载于:https://www.cnblogs.com/-slz-2/p/11252018.html...
  • 《内部排序算法比较

    千次阅读 多人点赞 2018-12-13 19:24:18
    (1) 对6种常用内部排序算法进行比较:冒泡排序、直接插入排序、简单选择排序、快速排序、希尔排序、堆排序 (2) 待排序的表长不小于100,其中数据要用伪随机数产生,至少用5组不同的输入数据做比较 ...
  • C 排序 数据结构 链表 堆排序 希尔排序 快速排序 递归排序。详细解释了每个排序方法原理,并带有程序代码。是学习C语言的绝好资料
  • ——“随机化快速排序可以满足一个人一辈子的人品需求。” 快速排序是一种很高效且有多种优化方法的排序算法,具体的介绍和实现在我的专栏01.其实我之前只知道快速排序的平均时间复杂度为O(n×log(n)),却...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 23,685
精华内容 9,474
关键字:

快速排序比较次数公式

友情链接: Instance-Aware-Hashing.rar