分治算法——快速排序 原理与C++代码实现(简短)

分治算法——快速排序 原理与C++代码实现(简短)

分治算法——快速排序 原理与C++代码实现(简短) 

分治算法——快速排序 原理与C++代码实现(简短) 

 

如何分解是一个难题,因为如果基准元素选取不当,有可能分解
成规模为0和n−1的两个子序列。
例如,序列(30, 24, 5, 58, 18, 36, 12, 42, 39),第一次选取5作为
基准元素,第二次选取12作为基准元素……
基准元素选取有以下几种方法:
取第一个元素。
取最后一个元素。
取中间位置元素。
取第一个、最后一个、中间位置元素三者之中位数。
取第一个和最后一个之间位置的随机数k(low≤k≤high)

算法步骤:
1)取第一个元素作为基准元素pivot=R[low],i=low,j=high
2)从右向左扫描,找小于等于pivot的数,则R[i]和R[j]交换,i++
3)从左向右扫描,找大于pivot的数,则R[i]和R[j]交换,j− −
4)重复2)和3),直到i和j重合,返回该位置mid=i,该位置的数
正好是pivot元素
5)至此完成一趟排序。此时以mid为界,将原数据分为两个子序
列,左侧子序列元素都比pivot小,右侧子序列元素都比pivot大,
再分别对这两个子序列进行快速排序

#include<iostream>
using namespace std;
int partition(int r[], int low, int high)//划分函数
{
    int i = low, j = high, pivot = r[low];
    while (i < j)
    {
        while (i < j && r[j] > pivot) //向左移动 ,停
            j--;
        if (i < j)
            swap(r[i++], r[j]);
        while (i < j && r[i] <= pivot) //向右移动,停
            i++;
        if (i < j)
            swap(r[i], r[j--]);
    }
    return i;//返回最终划分完成后基准所在元素的位置
}
void QuickSort(int R[], int low, int high)
{
    int mid;
    if (low < high)
    {
        mid = partition(R, low, high);
        QuickSort(R, low, mid - 1);
        QuickSort(R, mid + 1, high);
    }
}
void main()
{
    int i, N;
    int *a;
    cout << "请输入要排序数据的个数:";
    cin >> N;
    a = new int[N];
    cout << "请输入要排序数据:";
    for (i = 0; i < N; i++)
        cin >> a[i];
    cout << endl;
    QuickSort(a, 0, N - 1);
    cout << "排序后序列为:" << endl;
    for (i = 0; i < N; i++)
    {
        if (i != 0)
            cout << " ";
        cout << a[i];
    }
    cout << endl;
}

 时间复杂度分析:
1)分解:划分函数Partition需要扫描每个元素,每次扫描的元素
个数不超过n,因此时间复杂度为O(n)。
2)治理:最好情况下,每次划分将问题分解为两个n/2的子问题,
递归求解两个子问题,所需时间为2T(n/2) 。最坏情况下,每次划
分将问题分解为1和n-1的子问题,所需时间为T(n-1) 。
3)合并:原地排序,合并操作不需要时间。

最好(平均)情况:
时间复杂度:O(nlogn)
空间复杂度:O(logn)

最坏情况:
时间复杂度:O(n2)
空间复杂度:O(n)

上一篇:序列重排-求相邻差和最大(京东笔试题)


下一篇:算法设计与分析----分治法