首页 > 代码库 > 让算法会说话之快速排序

让算法会说话之快速排序

        转载请注明出处:http://blog.csdn.net/ruoyunliufeng/article/details/30729523


       快速排序是由东尼.霍尔所发展的一种排序算法。在平均状况下,排序n 个项目要O(n log n)次比较。在最坏状况下则需要Ο(n2)次比较,但这种状况并不常见。事实上,快速排序通常明显比其他Ο(n log n) 算法更快,因为它的内部循环(inner loop)可以在大部分的架构上很有效率地被实现出来。


一.排序步骤总结:

快速排序使用分治法(Divide and conquer)策略来把一个串行(list)分为两个子串行(sub-lists)。

1.用三数中值分割法找出枢纽元(基准)。

2.重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作。

3.递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。


二.快速排序算法

/***************************************************************
*版权所有 (C)2014,公司名称。
*
*文件名称:快速排序法
*内容摘要:无
*其它说明:无
*当前版本:V1.0
*作   者:若云流风
*完成日期:2014.6.14
***************************************************************/
#include <stdio.h>

#define N       (14)
#define cutoff  (3)    //截止范围小于等于3

void disp(void);

int a[N]={8,14,3,12,10,7,5,1,9,4,11,13,2,6};

/*交换函数*/
void Swap(int *a, int *b)
{
        int t;
        t = *a;
        *a = *b;
        *b = t;
}  

/*三种值分割*/
int Median3(int a[], int left, int right)
{
    //取数据的头、尾和中间三个数,并对他们进行排序
    //排序结果直接保存在数组中
    int centre = (left + right)/2;
    if(a[left] > a[centre])
        Swap(&a[left], &a[centre]);
    if(a[left] > a[right])
        Swap(&a[left], &a[right]);
    if(a[centre] > a[right])
        Swap(&a[centre], &a[right]);
    //把中值,即枢纽与数组倒数第二个元素交换
    Swap(&a[centre], &a[right - 1]);
    return a[right - 1];//返回枢纽
}

/*快速排序程序*/
void QSort(int a[], int left, int right)
{
    //如果需要排序的数据大于3个则使用快速排序
    if(right - left >= cutoff)
    {
        //取得枢纽的值
        int centre = Median3(a, left, right);
        int i = left;
        int j = right - 1;
        while(1)
        {
            /*向后扫描数组,找出大于枢纽元素的元素
            * 由于在选择枢纽时,已经把比枢纽值大的数据放在right位置
            * 所以不会越界
			*/
            while(a[++i] < centre);                               //当i大于等于中枢元素时候跳出循环

            /*向前扫描数组,找出小于枢纽元素的元素
            * 由于在选择枢纽时,已经把比枢纽值小的数据放在left位置
            * 所以不会越界
			*/
            while(a[--j] > centre);
            //把比枢纽小的数据放在前部,大的放到后部
            if(i < j)
			{
                Swap(&a[i], &a[j]);
                printf("\n快速排序结果: ");
			    disp();             //打印
			}
            else
			{
				//disp();
                break;
				
			}
            
        }

        Swap(&a[i], &a[right - 1]); //还原枢纽元素
		printf("\n 还原枢纽元素后结果: ");
        disp();

        QSort(a, left, i - 1);
        QSort(a, i + 1, right);
    }
    else                   //如果要排序的数据很少,少于等于3个,则直接使用冒泡排序
    {
        InsertionSort(a+left, right - left + 1);
    }
}

/*插入排序*/
int InsertionSort(int a[],int M)  
{
	int j,p,temp;

	for(p=1;p<M;p++)
	{
		temp=a[p]; //a[p]和左面的有序数列去比较

/*j>0保证不溢出,因为当j=0时啊a[j-1]非法,用a[p]分别与左面的值相比较
**如果a[p]小的话则互换位置,
*/

		for(j=p; j>0 && a[j-1]>temp;j--)     
		{
			a[j]=a[j-1];
        } 
		a[j]=temp;
	}
	printf("\n插入排序结果: ");
    disp();

} 

/*输出函数*/
void disp(void)
{
     int i;

     printf("\n排序结果: \n");
	 for(i=0;i<N;i++)
	 {
		printf("%d", a[i]);
		printf("  ");
	 }
	
}

int main(void)
{
	QSort(a , 0, N-1);
   // disp();
	return 0;

}



三.算法会说话

1.输出结果


2.总体过程分析

      a.三数中值分割法

                                                       8,14,3,12,10,7,5,1,9,4,11,13,2,         

        红色的三个数字按照大小顺序排好,中间的那个元素叫做中枢元,将中枢元和倒数第二个元素互换位置后返回。

                                                       5,14,3,12,10,7,2,1,9,4,11,13,6,8

    b.快速排序

                                                       5,14,3,12,10,7,2,1,9,4,11,13,6,8

                    (找出比中枢元大的)     i  -->                                  <--j(找出比中枢元小的)

                                                       5,14,3,12,10,7,2,1,9,4,11,13,6,8

                                                             i    <--交换-->        j

                                                     

                                                                i   <--交换-->  j         

                                               

                                                                      i <--> j 

                                                

                                                                      j    i                                                                      i>j退出

                         还原枢纽元素 

                   注意此时产生的结果就是以枢纽元素为分界线,左面的全部小于枢纽元素,右面的全部大于枢纽元素

                先对6前面的排序:

                                                             5,   4,   3,   1,   2         

                                                            2,   4,   1,    3,    5

                                                                   i      j


                                                                       

                                                           

                                                          2,1(插入排序)        3             4  ,5(插入排序)                                                      

                                                        

               6后面的排序和前面类似,故不再具体分析。


参考:1.维基百科

           2.数据结构与算法分析---C语言描述     Mark Allen Weiss 著