又见 “快速排序”

古城微笑少年丶 2022-03-20 01:37 248阅读 0赞

同上文一样：[http://blog.csdn.net/shanshanpt/article/details/8680498][http_blog.csdn.net_shanshanpt_article_details_8680498]

快速排序在一般的排序中被认为是平均效率最好的，主要适用于比较乱序的情况，对于基本有序的来说，效率不好~

快排的思想很简单，看下图：

原序列：4 3 5 2 1

一般以第一个数位基准点，但是很多其他的方法也行，例如随机一个数( 保证是数组内部的 )    ( "\_" 代表空的坑 )

变成：4        \_ 3 5 2 1  ->   1 3 5 2 \_   ->  1 3 \_2  5 -> 1 3 24 5 从此处分治：左边 1 3 2；右边 5 重复上面过程！

思想简单，写上CODE :

#include <stdio.h>
    #include <stdlib.h>
    
    void quick(int data[], int low, int high)
    {
    	int i = low, j = high, tmp = data[low];
    
        if (low < high)
        {
            while (i < j)
            {
                while(i < j && data[j] >= tmp)	// 从右向左找第一个小于tmp的数，等于tmp跳过
    	   {
    		j--;  
    	   }
                if(i < j)				// 这个判断是需要的~ 
    	   {
    		data[i++] = data[j];
    	   }
    			
                while(i < j && data[i] < tmp)	// 从左向右找第一个大于等于tmp的数
    	   {
    		i++;  
    	   }
                if(i < j) 
    	   {
    		data[j--] = data[i];
    	   }
            }
    
            data[i] = tmp;				// 原数据归位到中间
    
            quick(data, low, i - 1);		// 递归调用 
            quick(data, i + 1, high);
    
        }
    }
    
    int main()
    {
    	int * data, i, n;
    
    	while( scanf("%d", &n) != EOF )
    	{
    		data = ( int* )malloc( sizeof( int ) * n );
    		for( i = 0; i < n; i++ )
    		{
    			scanf("%d", &data[i]);
    		}
    
    		quick( data, 0, n - 1 );
    
    		for( i = 0; i < n; i++ )
    		{
    			printf("%d ", data[i]);
    		}
    
    		printf("\n");
    
    		free( data );
    	}
    
    	return 0;
    }

用快速排序解决前K个小的数的代码：具体看代码中的注释！

#include <stdio.h>
    #include <stdlib.h>
    
    void quick(int data[], int low, int high ,int k)
    {
    	int i = low, j = high, tmp = data[low];
    
        if (low < high)
        {
            while (i < j)
            {
                while(i < j && data[j] >= tmp)	// 从右向左找第一个小于tmp的数，等于tmp跳过
    	    {
    		j--;  
    	    }
                if(i < j)				// 这个判断是需要的~ 
    	    {
    		data[i++] = data[j];
    	    }
    			
                while(i < j && data[i] < tmp)	// 从左向右找第一个大于等于tmp的数
    	   {
    		i++;  
    	   }
                if(i < j) 
    	   {
    		data[j--] = data[i];
    	   }
            }
    
            data[i] = tmp;				// 原数据归位到中间
    
    	if( i == k )				// 已经出处理了K个，那么后面的排序就没有意义了
    	{
    		return;
    	}
    
            quick(data, low, i - 1, k);		// 递归调用
    
    	if( i > k )				// if左边的个数已经足够，那么右边的处理就可以省略了，因为左边已经包含K个数
    	{
    		return ;
    	}
    
            quick(data, i + 1, high, k);
    
        }
    }
    
    int main()
    {
    	int * data, i, n, k;
    
    	while( scanf("%d%d", &n, &k) != EOF )
    	{
    		data = ( int* )malloc( sizeof( int ) * n );
    		for( i = 0; i < n; i++ )
    		{
    			scanf("%d", &data[i]);
    		}
    
    		quick( data, 0, n - 1, k );
    
    		for( i = 0; i < k; i++ )
    		{
    			printf("%d ", data[i]);
    		}
    
    		printf("\n");
    
    		free( data );
    	}
    
    	return 0;
    }

[http_blog.csdn.net_shanshanpt_article_details_8680498]: http://blog.csdn.net/shanshanpt/article/details/8680498