排序算法——快速排序

一、快速排序算法的思想

  

    快速排序是基于分而治之的思想处理的。

    1、分解

    array[f...l]被划分为两个子数组array[f...q-1]和array[q...r]，使得array[f...q-1]<=array[q]       <=array[q...r]。

    2、解决

    通过递归调用快速排序，对两个子数组进行排序。

    3、合并

二、快速排序算法的描述

       

QuickSort（int array[],int first,int last）
{
    if(first<last)
    {
       k=partition(array,first,last);
       QuickSort(array,first,k-1);
       QuickSort(array,k+1,last);
    }
}

   数组的划分：快速排序的关键是partition的过程，即对数组的重新排序：

   

partition(int array[],int first,int last)
{
     key <- array[last];
     i <- first-1;
     for j <- first to last-1
     {
           if(array[j]<=key)
           {
                i++;
                swap(&array[i],&array[j]);
           }
     }
     swap(&array[i+1],&array[last]);
     return i+1;
}

   举个例子，如下为第一趟排序：

   第一趟(4步)：

   a：3   8   7   1   2   5   6   4   //以最后一个元素，array[last]为key

   b：3   1   7   8   2   5   6   4

   c：3   1   2   8   7   5   6   4

   d：3   1   2   4   7   5   6   8    //最后，swap(&array[i+1],&data[last])

三、C代码实现

   

#include "stdio.h"
/*
* 函数：swap(int *a,int *b)
* 功能：进行两个数的交换
*/
void swap(int *a,int *b)
{
    int temp;
    temp=*a;
    *a=*b;
    *b=temp;
}
/*
* 函数：partition(int array[],int ,int)
* 功能：分而治之，即对数组data进行重新排序
* 返回值：基准位置
*/
int partition(int array[],int first,int last)
{
    int key=array[last];//以最后一个元素为key
    int i=first-1;
    int j;
    for(j=first;j<last;j++)
    {
        if(array[j]<=key)
        {
            i++;
            swap(&array[i],&array[j]);
        }
    }
    swap(&array[i+1],&array[j]);//不能改为swap(&array[i+1],&key)
    return i+1;
}
/*
* 函数：QuickSort(int array[],int f,int h)
* 功能：进行快速排序—递归算法
*/
void QuickSort(int array[], int f, int h)
{
    if (f<h)
    {
        int k = partition(array, f, h);
        QuickSort(array, f, k-1);
        QuickSort(array, k+1, h);
    }
}

int main(int argc,char *argv[])
{
    int array[]={3,8,7,1,2,5,6,4};
    QuickSort(array,0,7);
    for(int i=0;i<8;i++)
    {
        printf("%d ",array[i]);
    }
    printf("\n");
    return 0;
}

四、快速排序算法的时间复杂度

    

   快速排序每次将待排序数组分为两个部分，在理想状况下，每一次都将待排序数组划分成等长两个部 分，则需要logn次划分。

   而在最坏情况下，即数组已经有序或大致有序的情况下，每次划分只能减少一个元素，快速排序将不幸退化为冒泡排序，所以快速排序时间复杂度下界为O(nlogn)，最坏情况为O(n^2)。在实际应用中，快速排序的平均时间复杂度为O(nlogn)。