快速排序

　　快速排序是面试中经常问到的排序算法

　　基本思想：通过一趟排序将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，

　　则可分别对这两部分记录继续进行排序，以达到整个序列有序的目的

　　代码如下：

　　1.swap 交换函数

void swap(int& a,int& b)

{

    int temp = a;

    a = b;

    b = temp;

}

　 2.Partition函数—快速排序中最关键的函数

int Partition(int* list,int low,int high)

{

    int pivot = list[low];

    while(low<high)

    {

        while(low<high&&list[high]>=pivot)

            high--;

        swap(list[low],list[high]);

        while(low<high&&list[low]<=pivot)

            low++;

        swap(list[low],list[high]);

    }

    return low;

}

　3.QSort函数—快速排序算法实现—递归

void QSort(int* list,int low ,int high)

{

    int pivotKey;

    if(low<high)

    {

        pivotKey = Partition(list,low,high);

        QSort(list,low,pivotKey-1);

        QSort(list,pivotKey+1,high);

    }

}

　　改进算法：
　　1.优化选取枢轴

　　　　Partition函数中选取pivotKey是一个关键，如果pivotKey选取的不是中间数，效率会受到不同程度的影响

　　　　比如数组{9,1,5,8,3,7,6,2},pivotKey = 9,partition结果是最后一位，只是实现了9和2的互换

　　　　改进办法：

　　　　　　1.取随机数

　　　　　　2.三数取中:取三个关键字先进行排序，将中间数作为枢轴，一般是取左端、右端、中间三个数

　　　　　　在Partition基础之上，添加、修改成如下代码：

　　 int pivotKey;

    int m = low+(high-low)/2;

    if(list[low]>list[high])

        swap(list[low],list[high]);

    if(list[m]>list[high])

        swap(list[m],list[high]);

    if(list[m]<list[low])

        swap(list[m],list[low]);
　　 pivotKey = list[m];

　　　　　　当然也可以九数取中　　

　　2.优化不必要的交换

int Partition2(int* list,int low,int high)

{

    int pivotKey;

    //可以加上三数取中

    pivotKey = list[low];

    int temp  = pivotKey;

    while(low<high)

    {

        while(low<high&&list[high]>=pivotKey)

            high--;

        list[low] = list[high];

        while(low<high&&list[low]<=pivotKey)

            low++;

        list[high] = list[low]

    }

    list[low] = temp;

    return low;

}

　　3.优化小数组时的排序方案

　　　　如果数组是小数组，应该采用插入排序，如果数组较长，应该采用快速排序　

void QSort1(int* list,int low,int high)

{

    int pivot;

    if((high-low)>MAX_LENGTH)

    {

        pivot = Partition(list,low,high);

        QSort1(list,low,pivot-1);

        QSort1(list,pivot+1,high);

    }else{

        InsertSort(list);

    }

}

　　4.优化递归操作

void QSort2(int *list,int low,int high)

{

    int pivot;

    if((high-low)>MAX_LENGTH)

    {

        while(low<high)

        {

            pivot = Partition(list,low,high);

            QSort2(list,low,pivot-1);

            low = pivot+1;

        }

    }else

    {

        InsertSort(list);

    }

}

巴特西

快速排序（C++）

快速排序

最新文章

热门文章