快速排序时间复杂度和不稳定性

客官°小女子只卖身不卖艺 2022-02-24 10:14 236阅读 0赞

**这里提供讲得超级清楚明白的视频！！！力荐[排序视频][Link 1]（这个都还看不懂就别学了）**

提供源代码，然后这里只讨论快速排序**不稳定性**和**时间复杂度**的问题。

**源代码：**

#include <stdio.h>
    
    //划分
    int Partition(int a[],int Left,int Right){
    	int L=Left;
    	int H=Right;
    	int temp=a[L]; //临时变量存放首元素 
    	while(L<H){
    		while(L<H&&a[H]>=temp){
    			H--;
    		}
    		a[L]=a[H];     //这里不要写为a[L++]=a[H] 
    		while(L<H&&a[L]<temp){
    			L++;
    		}
    		a[H]=a[L];
    	} 
    	a[L]=temp;
    	return L;
    }
    
    void Qsort(int a[],int L,int R){
    	if(L<R){
    		int p=Partition(a,L,R);
    		Qsort(a,L,p-1);
    		Qsort(a,p+1,R);
    	}
    }
    int main(){
    	int a[]={49,38,65,97,76,13,27,49};
    	Qsort(a,0,7);
    	for(int i=0;i<8;i++){
    		printf("%d  ",a[i]);
    	}
    }

**（一）不稳定问题:**  
不稳定指：经过排序后相同元素的值发生了变化（对调），相反稳定就是不会发生变化。  
举例：5 8 2 2' (4个元素，2'在2的右边)  
\-->经过快排过后变成了 2' 2 5 8（2'在2的左边了）

**（二）时间复杂度问题：**  
在序列元素接近有序时，会达到最后坏复杂度O（n^2）；比如：1 2 3 4 5 6 7 8  
因此：快速排序算法当序列元素的排列比较随机时效率最高，期望达到O（nlogn）；

[Link 1]: https://www.bilibili.com/video/av41132733/?p=7

发表评论取消回复

表情：

评论列表（有 0 条评论，236人围观）

还没有评论，来说两句吧...

相关阅读

相关排序算法分类排序算法时间复杂度、空间复杂度、稳定性

排序算法比较表格 ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4u

你的名字/ 2024年02月19日 20:34/ 0 赞/ 83 阅读

相关排序算法的时间复杂度,空间复杂度,稳定性总结

排序算法的时间复杂度,空间复杂度,稳定性总结 ![在这里插入图片描述][format_png_pic_center] [format_png_pic_center]:

╰+哭是因爲堅強的太久メ/ 2022年12月04日 08:49/ 0 赞/ 375 阅读

相关快速排序的时间复杂度和空间复杂度

我们来分析一下快速排序法的性能。 > 快速排序的时间性能取决于快速排序递归的深度，可以用递归树来描述递归算法的执行情况。 > 如图9‐9‐7所示，它是\{50,10,9

蔚落/ 2022年10月29日 03:14/ 0 赞/ 184 阅读

相关归并排序算法、时间复杂度和稳定性

归并排序算法原理归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型

客官°小女子只卖身不卖艺/ 2022年05月17日 06:17/ 0 赞/ 230 阅读

相关快速排序算法、时间复杂度和稳定性

快速排序算法原理通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，

深碍√TFBOYSˉ_/ 2022年05月17日 06:16/ 0 赞/ 194 阅读

相关插入排序算法、时间复杂度和稳定性

插入排序算法原理将数据分为有序部分和无序部分。在无序部分选择一个元素，按照顺序插入到有序部分，使之有序。直到无序部分都插入到有序部分结束。

绝地灬酷狼/ 2022年05月17日 06:15/ 0 赞/ 197 阅读

相关冒泡排序算法、时间复杂度和稳定性

冒泡排序冒泡排序一般是我们学习排序算法时第一个接触的算法，下面来介绍一下冒泡排序。算法原理比较相邻的元素。如果第一个比第二个大，就交换他们两个。

柔情只为你懂/ 2022年05月17日 06:15/ 0 赞/ 225 阅读

相关排序算法时间复杂度、空间复杂度、稳定性比较

排序算法分类 ![这里写图片描述][SouthEast] 排序算法比较表格填空 <table> <thead> <tr> <th style="

喜欢ヅ旅行/ 2022年05月15日 00:13/ 0 赞/ 310 阅读

相关排序算法时间复杂度、空间复杂度、稳定性比较

转自：[https://blog.csdn.net/yushiyi6453/article/details/76407640][https_blog.csdn.net_yush

曾经终败给现在/ 2022年04月01日 14:59/ 0 赞/ 345 阅读

相关快速排序时间复杂度和不稳定性

这里提供讲得超级清楚明白的视频！！！力荐[排序视频][Link 1]（这个都还看不懂就别学了）提供源代码，然后这里只讨论快速排序不稳定性和时间复杂度的问题。源代码：

客官°小女子只卖身不卖艺/ 2022年02月24日 10:14/ 0 赞/ 237 阅读