-
常用排序算法时间复杂度、空间复杂度、稳定性比较
2019-09-17 11:34:25最近在准备秋招的期间遇到了很多排序算法时间复杂度、空间复杂度、稳定性相关的题目,那就做个大致的总结吧。 排序算法 时间复杂度(平均) 时间复杂度(最坏) 时间复杂度(最好) 空间复杂度 稳定...最近在准备秋招的期间遇到了很多排序算法时间复杂度、空间复杂度、稳定性相关的题目,那就做个大致的总结吧。
排序算法 时间复杂度(平均) 时间复杂度(最坏) 时间复杂度(最好) 空间复杂度 稳定性 直接插入排序 O(n²) O(n²) O(n) O(1) 稳定 希尔排序 O(nlog2n) O(n²) O(n) O(1) 不稳定 直接选择排序 O(n²) O(n²) O(n²) O(1) 不稳定 堆排序 O(nlog2n) O(nlog2n) O(nlog2n) O(1) 不稳定 冒泡排序 O(n²) O(n²) O(n) O(1) 稳定 快速排序 O(nlog2n) O(n²) O(nlog2n) O(nlog2n) 不稳定 归并排序 O(nlog2n) O(nlog2n) O(nlog2n) O(n) 稳定 -
算法(一)——时间复杂度及常用排序算法时间复杂度
2019-07-13 20:19:14算法效率度量 1.时间复杂度O(n) 原则: 常数1代替所有加法中的常数 只保留最高阶数项(且不要前面的系数) ...时间复杂度 ...时间复杂度:算法性能指标(本质常数时间操作的个数);...常用排序算法及...文章目录
算法效率度量
1.时间复杂度O(n)
原则:- 常数1代替所有加法中的常数
- 只保留最高阶数项(且不要前面的系数)
- O(1)<O(log n)<O(n)<O(n logn)<O(n^2)
2.空间复杂度
常用空间换时间时间复杂度
时间复杂度:算法性能指标(本质常数时间操作的个数);先看指标再看系数;先看高阶项再看低阶项
常数时间操作:例如位操作、算术运算等。master公式
其中a表示子过程发生次数,b表示子过程样本量,
复杂度为
复杂度为
复杂度为常用排序算法及其时间复杂度
冒泡排序(bubblesort):
选择排序:
插入排序:
时间复杂度与数据状况有关,最好最差。但算法性能一律按最差考虑,即插入排序时间复杂度为
归并排序:
分治思想
总结
常用排序算法 时间复杂度 空间复杂度 稳定性 平均情况 最好情况 最坏情况 辅助存储 交换排序 冒泡排序 O(n*n) O(n) O(n*n) O(1) 稳定 快速排序 O(n*logn) O(n*logn) O(n*n) O(n*logn) 不稳定 插入排序 直接插入 O(n*n) O(n) O(n*n) O(1) 稳定 shell排序 O(n*n) O(n) O(n*n) O(1) 不稳定 选择排序 直接选择 O(n*n) O(n*n) O(n*n) O(1) 不稳定 堆排序 O(n*logn) O(n*logn) O(n*logn) O(1) 不稳定 归并排序 O(n*logn) O(n*logn) O(n*logn) O(n) 稳定 -
常用排序算法时间复杂度和空间复杂度
2017-12-27 14:50:57摘自维基百科: ...计算的时间复杂度(最差、平均、和最好性能),依据列表(list)的大小(n)。一般而言,好的性能是O(n log n),摘自维基百科: http://zh.wikipedia.org/wiki/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95#.E7.A8.B3.E5.AE.9A.E6.80.A7
在计算机科学所使用的排序算法通常被分类为:
- 计算的时间复杂度(最差、平均、和最好性能),依据列表(list)的大小(n)。一般而言,好的性能是O(n log n),且坏的性能是O(n2)。对于一个排序理想的性能是O(n)。仅使用一个抽象关键比较运算的排序算法总平均上总是至少需要O(n logn)。
- 存储器使用量(以及其他电脑资源的使用)
- 稳定性:稳定排序算法会让原本有相等键值的纪录维持相对次序。也就是如果一个排序算法是稳定的,当有两个相等键值的纪录R和S,且在原本的列表中R出现在S之前,在排序过的列表中R也将会是在S之前。
- 依据排序的方法:插入、交换、选择、合并等等。
稳定性
当相等的元素是无法分辨的,比如像是整数,稳定性并不是一个问题。然而,假设以下的数对将要以他们的第一个数字来排序。
(4, 1) (3, 1) (3, 7)(5, 6)
在这个状况下,有可能产生两种不同的结果,一个是让相等键值的纪录维持相对的次序,而另外一个则没有:
(3, 1) (3, 7) (4, 1) (5, 6) (維持次序) (3, 7) (3, 1) (4, 1) (5, 6) (次序被改變)
不稳定排序算法可能会在相等的键值中改变纪录的相对次序,但是稳定排序算法从来不会如此。不稳定排序算法可以被特别地实现为稳定。作这件事情的一个方式是人工扩充键值的比较,如此在其他方面相同键值的两个对象间之比较,(比如上面的比较中加入第二个标准:第二个键值的大小)就会被决定使用在原先数据次序中的条目,当作一个同分决赛。然而,要记住这种次序通常牵涉到额外的空间负担。
排序算法列表
在这个表格中,n是要被排序的纪录数量以及k是不同键值的数量。
稳定的排序
- 冒泡排序(bubble sort)— O(n2)
- 鸡尾酒排序(cocktail sort)—O(n2)
- 插入排序(insertion sort)—O(n2)
- 桶排序(bucket sort)—O(n);需要O(k)额外空间
- 计数排序(counting sort)—O(n+k);需要O(n+k)额外空间
- 归并排序(merge sort)—O(n log n);需要O(n)额外空间
- 原地归并排序— O(n2)
- 二叉排序树排序(binary tree sort)— O(n log n)期望时间; O(n2)最坏时间;需要O(n)额外空间
- 鸽巢排序(pigeonhole sort)—O(n+k);需要O(k)额外空间
- 基数排序(radix sort)—O(n·k);需要O(n)额外空间
- 侏儒排序(gnome sort)— O(n2)
- 图书馆排序(library sort)— 时间复杂度通常是O(n log n),需要(1+ε)n额外空间
不稳定的排序
- 选择排序(selection sort)—O(n2)
- 希尔排序(shell sort)—O(n log2 n)如果使用最佳的现在版本
- Clover排序算法(Clover sort)—O(n)期望时间,O(n^2/2)最坏情况
- 梳排序— O(n log n)
- 堆排序(heap sort)—O(n log n)
- 平滑排序(smooth sort)— O(n log n)
- 快速排序(quick sort)—O(n log n)期望时间, O(n2)最坏情况;对于大的、乱数列表一般相信是最快的已知排序
- 内省排序(introsort)—O(n log n)
- 耐心排序(patience sort)—O(n log n + k)最坏情况时间,需要额外的O(n + k)空间,也需要找到最长的递增子序列(longest increasing subsequence)
不实用的排序
- Bogo排序— O(n × n!),最坏的情况下期望时间为无穷。
- Stupid排序—O(n3);递归版本需要O(n2)额外存储器
- 珠排序(bead sort)— O(n) or O(√n),但需要特别的硬件
- 煎饼排序—O(n),但需要特别的硬件
- 臭皮匠排序(stooge sort)算法简单,但需要约n^2.7的时间
平均时间复杂度
平均时间复杂度由高到低为:
说明:虽然完全逆序的情况下,快速排序会降到选择排序的速度,不过从概率角度来说(参考信息学理论,和概率学),不对算法做编程上优化时,快速排序的平均速度比堆排序要快一些。
名称 数据对象 稳定性 时间复杂度 空间复杂度 描述 平均 最坏 冒泡排序 数组 (无序区,有序区)。从无序区通过交换找出最大元素放到有序区前端。 选择排序 数组 (有序区,无序区)。在无序区里找一个最小的元素跟在有序区的后面。对数组:比较得多,换得少。 链表 插入排序 数组、链表 (有序区,无序区)。把无序区的第一个元素插入到有序区的合适的位置。对数组:比较得少,换得多。 堆排序 数组 (最大堆,有序区)。从堆顶把根卸出来放在有序区之前,再恢复堆。 归并排序 数组 ,如果不是从下到上
把数据分为两段,从两段中逐个选最小的元素移入新数据段的末尾。可从上到下或从下到上进行。 链表 快速排序 数组 (小数,枢纽元,大数)。 希尔排序 数组 每一轮按照事先决定的间隔进行插入排序,间隔会依次缩小,最后一次一定要是1。 计数排序 数组、链表 统计小于等于该元素值的元素的个数i,于是该元素就放在目标数组的索引i位(i≥0)。 桶排序 数组、链表 将值为i的元素放入i号桶,最后依次把桶里的元素倒出来。 基数排序 数组、链表 一种多关键字的排序算法,可用桶排序实现。 -
- 均按从小到大排列
- k代表数值中的"数位"个数
- n代表数据规模
- m代表数据的最大值减最小值
-
常用排序算法时间复杂度和空间复杂度简析
2014-06-24 21:08:08前段时间将排序算法从新整理了一下,并对工作原理,时间复杂度,空间复杂度进行了一些简单分析。内容主要包括快速排序,堆排序,归并排序等三种常用排序算法。1. preface
/****
* This article will try to explain something about:
* --Bubble sort.
* --Quick sort.
* --Merge sort.
* --Heap sort.
* To read this, some prerequisites is necessary:
* --a survive skill in C programming language.
* --a basic skill in CPP.
* --basic knowledge about Time complexity and Space complexity.
* --a generous mind for my fault because this article is free.
*
* Actually, their basic operating principle are easy to understand, but , unfortunately, the precise explication is big problem, at least for me. Here is the contents.
* --Analysis about Bubble sort.
* --Analysis about Quick sort.
* --Analysis about Merge sort.
* --Analysis about Heap sort.
* their source code can be find in fellowing articles. As we all know, for a programmer, the source code is also a good choice.
*/2. Bubble sort
/****
* Bubble Sort
* This is a really simple algorithm. I learn it when I began to learn C. It just compare two value successively and swap them. The core source code is as fellowing:
*/2.1 core code
bool BubbleSort::sort(void) { int i,j; for( i=0; i<=n; i++) for( j=0; j< n -i; j++) { if( this->array[ j]>this->array[ j+1]) { this->swap( j, j + 1); //swap two values } } }
2.2 Time complexity and Space complexity
/**
* For sort algorithm, it's basic operation is swap two values.So we can compute it's sentence frequency f(n):
* f(n) = n*n = n^2
* (at worst situation)
* and it's time complexity is :
* T(n) = O( f(n)) = O(n^2)
*
*
* obviously, It's space complexity is :
* S(n) = O( g(n)) = O( C) = O(1)
* because it use only constant space whatever n change.
*//*
* The totally example source code is here:
*
* (It maybe some fault, I will glad to your advices)
*/3. Quick sort
/****
* Quick Sort
* This is a famous algorithm. It was developed in 1960 , but never outdated even for now. I was face a problem about sort a million of numbers. Need to say that is a* nightmare if use bubble sort. Then I learn Quick Sort, it provide a exciting performance. I will explain this below. The principle of quicksort is "divided and process".
* In detail,
* --step1: Pick an element from the array as pivot.
* --step2: Part all elements into two areas: left area and right area.put element that's value less than pivot's value into left area,and put other elements into right area.
* --step3: Recursively do the step above to those sub-array.
*
*
*. First at all, examine it's core source code:
*/3.1 Core Code
static void quick_sort( int array[], INDEX left, INDEX right) { if( right-left>=2) {//core code int p; p = pivot( array, left, right); //step1 + step2 quick_sort( array, left, p-1); //step3 quick_sort( array, p+1, right); } else if( right -left ==1) {//auxiliary if( array[left] > array[right]) { swap( array + left, array + right); } } } static int pivot( int array[], INDEX left, INDEX right) { //get povit, one of methods INDEX mInd = (left + right)/2; //divide array into two parts int i = 0; int LLen = 0, RLen = 0; for( i=left; i<=right; i++ ) { if( i==mInd) continue; if( array[i]< array[mInd] ) { Arr_back[left + LLen] = array[i]; LLen++; } else { Arr_back[right - RLen] = array[i]; RLen++; } } Arr_back[left + LLen] = array[mInd]; memcpy( array+left, Arr_back + left, (right-left + 1)*sizeof(int)); //use a auxiliary space return left + LLen; }
3.2 Time complexity
/**
* For quicksort, the basic operation is similar to swap above. So we could compute a valid sentence frequency. If there are n elements, in average situation the depth of* recurrence is log2(n).Just as below:
*
* step1: [1.........................................................n] // n
* step2: [1......................m1] [m1.......................n] // n/2 + n/2
* step3: [1.....m2] [m2.....m1] [m1....m3] [m3......n] // n/4 + n/4 + n/4 + n/4
* .......
* stepX: [1,2][3,4]................................................
*
* and funny is that: for step N, if we want to part those arrays into sub-array, we need the number of basic operation is :
* N*(n/N)
* that's means:
* f(n) = n*log2(n)
* and
* T(n) = O( f(n)) = O( n*log2(n) )
*
*/3.3 Space complexity
/**
* At least two points are deserve to consider.
* Point.1 : Normally, we need more auxiliary space when n increase.
* Point.2 : the recursion of function may be need more space.
*
* In my situation, the auxiliary space of Point.1 is n. For Point.2, Assume that the cost is A for ecah function call, the totally number of call is
* 2^0 + 2^1 + 2^2 + .....2^log2(n)
*
* then, the cost of point.2 is
*
* A*[1 + 2^1 + 2^2 + ....2^log2(n) ]
* =A*[1 + 2^1 + 2^2 + ....+ n]
* =A*[2*n-1] < A*2*n
*
* combine two parts:
* S(n) = O( B*n) = O(n)
*/
/*
* References
* wikipedia-Quicksort <http://en.wikipedia.org/wiki/Quicksort>
*/4. Merge sort
/****
* Merge Sort
* The common view is that: compare with famous Quicksort and Heapsort, it is slightly worse in sort a array. but it provide a excellent performance in sort a link list,* which is difficult to Quicksort and Heapsort. on the other side, Mergesort is a stable sort, unlike standard in-place quicksort and heapsort. It's core principle is "divide
* and conquer".
*
* conceptually, Mergesort work as fellow:
* step1: divide the array into n sublists.That means every sublist is only contain of 1 element.
* step2: repeatedly merge all sublists to create new sorted sublist untill there is only 1 sublist remaining.
*
* just like this:
* step1: [0] [1] [2] [3] [4] [5] [6] [7]
* step2: [0...1] [2...3] [4...5] [6...7]
* step3: [0............3] [4..............7]
* step4: [0..................................7]
*
* If you need more information, there will be a good place.
* http://en.wikipedia.org/wiki/Merge_sort
*
* then , examine the core source code:
*/4.1 core code
bool MergeSort::sort(void) { ...... int width = 1; while( width < (this->right - this->left + 1) ) { this->subsort( width); //sort sublists width *= 2; } ..... } bool MergeSort::subsort( int width) { ..... INDEX cur = this->left; while( cur + width <= this->right) { //sort two sublists into a new sorted list. this->sort2Arr( cur, width, cur + width, MIN( width, this->right-cur-width+1)); cur += 2*width; } memcpy( this->array, this->array_back, (this->right - this->left + 1)*sizeof(int)); ..... }
4.2 Time complexity
/**
* Time complexity
*
* Now, let me see a interesting thing before check it's Time frequency. Image this, there are two arrays ,both of them are progressive increase. they are contain of n and* m elements respectively.
*
* [1.............n] [1..........m]
*
* How many times is necessary to merge them into a new sorted array?
*
* -- at least: MIN( n,m);
* at most: m+n;
*
* For example:
* [ 1, 2, 3] [4,5,6,7]
* and
* [1,2,3,7] [4,5,6]
*
*
* Based on the conclusions above, we could know that : at worst situation, if we want to sort n elements by the way of Mergesort, the times of compare operation is n.
*
* So, Time frequency is n*log2(n)
* and
* T(n) = O( f(n)) = O( n*log2(n) )
*
*/4.3 Space complexity
/**
* Space complexity
* In my example, a additional array was used to auxiliary operation.
* obviously, the space complexity is :
* S(n) = O(n);
*
* but that is at worst situation. It could be optimized.
*
*/5. Heap sort
/****
* Heap Sort
* This is another famous sort algorithm. Need to say: it's very cool. Although sometimes it is slower in practice on most machine than well-implemented quicksort, it's*have the advantage of a more favorable worst-case O( n*log(n)) runtime. unfortunately, it is not a stable sort.
*//*
* Before explain heapsort, some questions are necessary to know:
* 1). How can we store a binary tree into a array ?
*
* --if we number all nodes of a tree , based on 1, you will find a rule. To a node n, it must have the fellowing relationship:
* parent : floor(n/2)
* left chil : 2*n
* right chil : 2*n + 1
*
* This feature gives us a chance to save a tree into a array.
*
* 2). What is max heapify ?
* --For a binary tree, if all of parent nodes greater than or equal to those corresponding child nodes, the root node must be the largest node in this tree. In other words,
* we can get the largest one between some nodes by arrange those number into a max binary tree. By the way, if binary tree can do that, then heap can, too.
*/
/*
* The Heapsort algorithm can be divided into two parts.
* step 1: build a max binary tree.
*
* step 2: remove the largest node( the root of the tree) ,and then update the tree repeatedly untill all of nodes has been get out.
*
*/5.1 core code
bool HeapSort::sort(void) { /* * As we all know, some of nodes haven't child node. * For skip those nodes, we need to find the last parent node. * * but How can we do that? * * --the answer is the last child node. */ INDEX nInd = 0; nInd = this->fun.GetParentInd( this->right ); /* * Adjust nodes from bottom to top.Function MaxHeapify() * will arrange a node and its's sublayer nodes to * a max binary tree. */ while( nInd>=0) { // @(this->right) is the number of nodes. this->MaxHeapify( nInd, this->right); nInd--; } /* * moving the largest one between all of nodes into a array, * and tidy the remaining. Repeat this process untill * we get all of nodes. */ nInd = this->right; while( nInd>0 ) { this->Swap( 0, nInd); nInd --; this->MaxHeapify( 0, nInd); } return true; } bool HeapSort::MaxHeapify( INDEX nInd, INDEX right) { INDEX max = this->GetBigNodeInd( nInd, right); while( max!=nInd) { this->Swap( max, nInd); nInd = max; max = this->GetBigNodeInd( nInd, right); } return true; }
/*
* About @MaxHeapify(), there are many problems need to solve. This article is worth to reading:
* http://shmilyaw-hotmail-com.iteye.com/blog/1775868
*
*/5.2 Time complexity
/**
* sorry, I have no idea.
*/5.3 Space complexity
/**
* space complexity
*
* It is simple to compute the space complexity.
* S(n) = O(1);
* because it use a constant space.
*//*
* The totally example source code is here:
*
* (It maybe some fault, I will glad to your advices)
*/
/**
* References:
*
* heap sort分析和总结 <http://shmilyaw-hotmail-com.iteye.com/blog/1775868>
* heapsort <http://en.wikipedia.org/wiki/Heapsort>
*
*/ -
笔试时常用排序算法时间复杂度和空间复杂度
2017-05-13 21:10:13摘自维基百科: ...在计算机科学所使用的排序算法通常被分类为:计算的时间复杂度(最差、平均、和最好性能),依据列表(list)的大小(n)。一般而言,好的性能是O(n log n),且坏的性能是O(n2)。 -
常用排序算法时间复杂度及相关性能
2019-09-03 16:58:37 -
常用排序算法时间复杂度、空间复杂度和稳定性比较
2019-10-06 16:45:28 -
各种常用排序算法时间复杂度
2013-04-10 11:06:36 -
数据结构和算法分析之排序篇--归并排序(Merge Sort)和常用排序算法时间复杂度比较(附赠记忆方法)
2018-09-08 22:06:38归并排序的基本思想 归并排序法是将两个或以上的有序表合并成一个新的有序表,即把待排序序列分成若干个子序列,每个子序列是有序的。然后再把有序子序列合并为整体有序序列。注意:一定要是有序序列! 归并排序... -
js排序的时间复杂度_各种排序算法时间复杂度
2020-12-23 17:16:12各种排序算法比较各种常用排序算法类别排序方法时间复杂度空间复杂度稳定性复杂性特点最好平均最坏辅助存储简单插入排序直接插入O(N)O(N2)O(N2)O(1)稳定简单希尔排序O(N)O(N1.3)O(N2)O(1)不稳定复杂选择排序直接选择... -
各种排序算法时间复杂度
2019-10-07 23:09:57各种排序算法时间复杂度 各种排序算法比较 各种常用排序算法 类别 排序方法 时间复杂度 空间复杂度 稳定性 复杂性 特点 最好 ... -
Unity3d常用的排序算法时间复杂度与空间复杂度
2016-07-24 13:29:00常用的排序算法的时间复杂度与空间复杂度 快排时间复杂度与空间复杂度 1、时间复杂度 (1)时间频度 一个算法执行所耗费的时间,从理论上是不能算出来的,必须上机运行测试才能知道。但我们不可能也没有必要对... -
各种排序算法时间复杂度和空间复杂度表
2017-09-05 10:23:00常用排序算法的时间复杂度和空间复杂度表格,自己整理了一下,如下: -
java排序算法复杂度_076-排序算法时间复杂度比较
2021-03-01 08:07:282.网上数据结构和算法的课程不少,但存在两个问题:1)授课方式... 本课程针对上述问题,有针对性的进行了升级3)授课方式采用图解+算法游戏的方式,让课程生动有趣好理解4)系统多面的讲解了数据结构和算法, 除常用数... -
常用排序算法的时间复杂度以及空间复杂度
2017-04-14 18:20:53下面是常用排序算法的时间复杂度,空间复杂度分享 -
常用排序算法的时间复杂度和空间复杂度
2020-11-25 20:41:49常用的排序算法的时间复杂度和空间复杂度 排序法 最差时间分析 平均时间复杂度 稳定度 空间复杂度 冒泡排序 O(n2) O(n2) 稳定 O(1) 快速排序 O(n2) O(nlog2n) 不稳定 O(log2n)~O(n) 选择排序 O(n2)