快速排序----(排序算法四)

约定不等于承诺〃 2022-09-17 13:22 123阅读 0赞

# 1.算法原理 #

快速排序算法是对冒泡法([http://blog.csdn.net/whzhaochao/article/details/12971057][http_blog.csdn.net_whzhaochao_article_details_12971057])的改进，其思想是，先初始化一个数据，然后交换，将小于它的数据放它左边，大于等于它的数据放右边。

例如对：49 38 65 97 76 13 27 49

第一次：初始化一个数据通常取第一个为49，那么一趟排序后为 27 38 13 \[49\] 76 97 65 49

可见\[49\]左边全部小于49，49右边不小于49

第二次：对\[49\]左边27 38 13 和\[49\]右边76 97 65 49 分别再用一次排序得到

13 \[27\] 38和 49 65 \[76\] 97

第三次 对\[76\]左边49 65进行一次排序得 \[49\] 65

排序结束，结果为 13 27 38 49 49 65 76 97

# 2.一次快速排序实现 #

对 a\[9\]=\{0 49 38 65 97 76 13 27 49\}进行一次快速排序

首先初始化监视哨a\[0\]为49，定义一个low=1指向a\[1\]，定义一个high=8，指向a\[8\]

a\[8\]=49，所以high--=7；

a\[7\]<49，所以将27移至a\[low\]即a\[9\]=\{0 27 38 65 97 76 13 27 49\}

然后从a\[low\]开始比较

a\[1\]<49，所以low++=2；

a\[2\]<49，所以low++=3；

a\[3\]>49，所以将65，移至a\[high\]处即a\[9\]=\{0 27 38 65 97 76 13 65 49\}

然后再从a\[high\]开始比较

a\[7\]>49，所以high--=6；

a\[6\]<49，所以将13移到a\[low\]处即a\[9\]=\{0 27 38 13 97 76 13 65 49\}

然后再从a\[low\]开始比较

a\[3\]<49，所以low++=4;

a\[4\]>49，所以将97移到a\[high\]处即a\[9\]=\{0 27 38 13 97 76 97 65 49\}

然后再从，a\[high\]开始比较

a\[6\]>49，所以high--=5；

a\[5\]>49，所以high--=4；

因为low=high=4所以结束

a\[low\]=a\[0\]即a\[9\]=\{0 27 38 13 49 76 97 65 49\}

通过上面我们将49左边存放的全部小于49，49右边全部不小于49，完成一次快速排序

代码如下：

#include <stdio.h>
    
    void printArray(int a[],int size){  
        printf("数组为：[%d] ",a[0]);  
        for (int i=1;i<size;i++)  
        {  
            printf(" %d ",a[i]);  
        }  
        printf("\n");  
    }
    
    //一次划分
    int Partition(int a[],int low,int high){	
    	a[0]=a[low];
    	int prvotkey=a[low];
    	while(low<high){
    		while(low<high &&a[high]>=prvotkey) --high;
    			a[low]=a[high];
    		printf(" a[%d]=a[%d] ",low,high);
    		printArray(a,9);
    		while(low<high && a[low]<=prvotkey) ++low;
    			a[high]=a[low];
    		printf(" a[%d]=a[%d] ",high,low);
    		printArray(a,9);
    	}
    	printf(" a[%d]=a[%d] ",low,0);
    	a[low]=a[0];
    	return low;
    }
    
    
    
    void main()
    {
    	//a[0]为监视哨
    	int a[9]={0,49,38,65,97,76,13,27,49}; 
    	Partition(a,1,8);
    	printArray(a,9);
    	
    }

结果

a[1]=a[7] 数组为：[49]  27  38  65  97  76  13  27  49
     a[7]=a[3] 数组为：[49]  27  38  65  97  76  13  65  49
     a[3]=a[6] 数组为：[49]  27  38  13  97  76  13  65  49
     a[6]=a[4] 数组为：[49]  27  38  13  97  76  97  65  49
     a[4]=a[4] 数组为：[49]  27  38  13  97  76  97  65  49
     a[4]=a[4] 数组为：[49]  27  38  13  97  76  97  65  49
     a[4]=a[0] 数组为：[49]  27  38  13  49  76  97  65  49

# 3.快速排序代码实现 #

#include <stdio.h>
    
    void printArray(int a[],int size){  
        printf("数组为：[%d] ",a[0]);  
        for (int i=1;i<size;i++)  
        {  
            printf(" %d ",a[i]);  
        }  
        printf("\n");  
    }
    
    //一次划分
    int Partition(int a[],int low,int high){	
    	a[0]=a[low];
    	int prvotkey=a[low];
    	while(low<high){
    		while(low<high &&a[high]>=prvotkey) --high;
    			a[low]=a[high];
    		while(low<high && a[low]<=prvotkey) ++low;
    			a[high]=a[low];
    	}
    	a[low]=a[0];
    	return low;
    }
    
    //递归法快速排序
    void QSrot(int a[],int low,int high){
    	if (low<high)
    	{	
    		int m=Partition(a,low,high);
    		printf(" low=%d high=%d m=%d ",a[low],a[high],a[m]);
    		printArray(a,9);
    		QSrot(a,low,m-1);
    		QSrot(a,m+1,high);
    	}
    }
    
    void main()
    {
    	//a[0]为监视哨
    	int a[9]={0,49,38,65,97,76,13,27,49}; 
    	QSrot(a,1,8);
    	printArray(a,9);
    	
    }

# 4.结果 #

low=27 high=49 m=49 数组为：[49]  27  38  13  49  76  97  65  49
     low=13 high=38 m=27 数组为：[27]  13  27  38  49  76  97  65  49
     low=49 high=97 m=76 数组为：[76]  13  27  38  49  49  65  76  97
     low=49 high=65 m=49 数组为：[49]  13  27  38  49  49  65  76  97
    数组为：[49]  13  27  38  49  49  65  76  97

[http_blog.csdn.net_whzhaochao_article_details_12971057]: http://blog.csdn.net/whzhaochao/article/details/12971057