交换排序之快速排序

逃离我推掉我的手 2023-07-18 02:49 24阅读 0赞

## 快速排序的核心思想： ##

1.  每一轮选取一个随机的数字作为参照，一般选取本轮的第一个数字，然后设置两个指针，分别指向序列头部和尾部；
2.  与参照数字作比较，左边遇到大于参照数字指针停止移动，右边遇到小于参照的数字，指针停止移动；
3.  将此时左右两边指针所指的数字交换位置；
4.  如此下去，直到左右指针相遇

这样做保证左边的数字总小于参照数字，右边的数字总大于参照数字，每一轮的比较和移动，**实际就是为了找到本轮参照数字在排序完成后应该所在的位置**。

## 过程演示 ##

这里选取30做为参照数字  
![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTUzOTI5_size_16_color_FFFFFF_t_70][]

1.  左指针指向第一个数54，大于30，停止，右指针移动

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTUzOTI5_size_16_color_FFFFFF_t_70 1][]  
2. 59大于30，继续向左移动

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTUzOTI5_size_16_color_FFFFFF_t_70 2][]

1.  6小于30，停止，将左右指针所指元素互换  
    ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTUzOTI5_size_16_color_FFFFFF_t_70 3][]
2.  互换后，左指针继续向右移动  
    ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTUzOTI5_size_16_color_FFFFFF_t_70 4][]
3.  67大于30，左2指针停止，右指针移动  
    ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTUzOTI5_size_16_color_FFFFFF_t_70 5][]
4.  64大于30，继续左移

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTUzOTI5_size_16_color_FFFFFF_t_70 6][]  
7. 67大于30，右指针向左移动

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTUzOTI5_size_16_color_FFFFFF_t_70 7][]  
8. 6小于30 指针停止，下面条件判断发现左右指针早已相遇，跳出循环

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTUzOTI5_size_16_color_FFFFFF_t_70 8][]  
9. 最后将参照数字与跳出循环后右指针所指位置的数字互换，至此，30就找到了排序后它应该所在的位置。

这样不断递归后，所有的数字都找到了它排序后应该在的位置上面，于是排序就完成了。

## 完整代码 ##

c语言

#include<stdio.h>
    
    
    int partition(int A[],int low ,int high){ //获取枢轴下标函数，并调整使得枢轴左边的元素小于枢轴，右边大于枢轴
    	int povit=A[low];
    	while(low<high){ 
    		while(low<high&&povit<=A[high])high--;
    			A[low]=A[high];
    		while(low<high&&povit>=A[low])low++;
    			A[high]=A[low];
    	}
    	A[low]=povit;
    	return low;
    }
    
    void quickSort(int *A,int low,int high){ //递归排序
    	if(low<high){ 
    		int pivotpos=partition(A,low,high);
    		quickSort(A,low,pivotpos-1);//对序列前半部分排序
    		quickSort(A,pivotpos+1,high);//对序列后半部分排序
    	}
    	
    }
    
    
    
    int main(){ 
    	int A[11]={ 0,5,3,6,8,1,9,2,6,7,-2};
    	int i=0;
    	
    	quickSort(A,0,10);
    	
    	for(;i<11;i++){ 
    		printf("%d ",A[i]);
    	}
    	return 0;
    }

结果如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTUzOTI5_size_16_color_FFFFFF_t_70 9]

## 时间复杂度与空间复杂度 ##

快速排序最差的情况下时间复杂度为：O( n^2 )，退化为冒泡排序  
**不适用于本来有序的情况**

平均时间复杂度  
快速排序的最优和平均时间复杂度是：O(nlog2n)

最优的情况下空间复杂度为：O(log2n) ；每一次都平分数组的情况  
最差的情况下空间复杂度为：O( n ) ；退化为冒泡排序的情况  
**是不稳定的算法**

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTUzOTI5_size_16_color_FFFFFF_t_70]: /images/20230528/0790d33521b046289f6d607d8950e4ce.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTUzOTI5_size_16_color_FFFFFF_t_70 1]: /images/20230528/756d1e971f204ca1bc10a0f2ea8bf53c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTUzOTI5_size_16_color_FFFFFF_t_70 2]: /images/20230528/6e3e2b3676e6400e86068228f7088aad.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTUzOTI5_size_16_color_FFFFFF_t_70 3]: /images/20230528/12398d6b8c9a4a3fa2def85b56f432be.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTUzOTI5_size_16_color_FFFFFF_t_70 4]: /images/20230528/5948e6ed062e430c92f1bd790c1a6132.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTUzOTI5_size_16_color_FFFFFF_t_70 5]: /images/20230528/db3923c9aa354c929cb73dd1641aee46.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTUzOTI5_size_16_color_FFFFFF_t_70 6]: /images/20230528/304c74e2e8e04649ad6959d802b92995.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTUzOTI5_size_16_color_FFFFFF_t_70 7]: /images/20230528/c95a850caf1b4f2db68df5191dbf46cd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTUzOTI5_size_16_color_FFFFFF_t_70 8]: /images/20230528/c19ef60b70b64725ba62b7159468f09f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTUzOTI5_size_16_color_FFFFFF_t_70 9]: /images/20230528/092861f2dbaf48d2b58861bc2b9c8907.png