wizen-coder
10/4/2018 - 10:17 AM

1、未优化的快速排序 快速排序的基本思想是通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。 2、随机后标记元素后的

1、未优化的快速排序 快速排序的基本思想是通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。 2、随机后标记元素后的快速排序 未随机化处理的快速排序最坏情况发生在划分过程产生的两个区域分别包含n-1个元素和1个元素的时候。由于函数Partition的计算时间为O(n),所以如果算法Partition的每一步都出现这种不对称划分，

RandomizedQuickSort.cpp
content_copyfile_download
//2d8-2 随机后标记元素后的快速排序
#include "stdafx.h"
#include <iostream> 
#include <ctime>
using namespace std; 
 
int a[] = {5,7,3,4,8,6,9,1,2};
 
template <class Type>
void Swap(Type &x,Type &y);
 
inline int Random(int x, int y);
 
template <class Type>
int Partition(Type a[],int p,int r);
 
template<class Type>
int RandomizedPartition(Type a[],int p,int r);
 
template <class Type>
void RandomizedQuickSort(Type a[],int p,int r);
 
int main()
{
	for(int i=0; i<9; i++)
	{
		cout<<a[i]<<" ";
	}
	cout<<endl;
	RandomizedQuickSort(a,0,8);
	for(int i=0; i<9; i++)
	{
		cout<<a[i]<<" ";
	}
	cout<<endl;
}
 
template <class Type>
void Swap(Type &x,Type &y)
{
	Type temp = x;
	x = y;
	y = temp;
}
 
inline int Random(int x, int y)
{
     srand((unsigned)time(0));
     int ran_num = rand() % (y - x) + x;
     return ran_num;
}
 
template <class Type>
int Partition(Type a[],int p,int r)
{
	int i = p,j = r + 1;
	Type x = a[p];
 
	while(true)
	{
		while(a[++i]<x && i<r);
		while(a[--j]>x);
		if(i>=j)
		{
			break;
		}
		Swap(a[i],a[j]);
	}
	a[p] = a[j];
	a[j] = x;
	return j;
}
 
template<class Type>
int RandomizedPartition(Type a[],int p,int r)
{
	int i = Random(p,r);
	Swap(a[i],a[p]);
	return Partition(a,p,r);
}
 
template <class Type>
void RandomizedQuickSort(Type a[],int p,int r)
{
	if(p<r)
	{
		int q = RandomizedPartition(a,p,r);
		RandomizedQuickSort(a,p,q-1);
		RandomizedQuickSort(a,q+1,r);
	}
}
QuickSort1.cpp
content_copyfile_download
//2d8-1 未优化的快速排序
#include "stdafx.h"
#include <iostream>
using namespace std;

int a[] = {5,7,3,4,8,6,9,1,2};

template <class Type>
void Swap(Type &x,Type &y);

template <class Type>
int Partition(Type a[],int p,int r);

template <class Type>
void QuickSort(Type a[],int p,int r);

int main()
{
    for(int i=0; i<9; i++)
    {
        cout<<a[i]<<" ";
    }
    cout<<endl;
    QuickSort(a,0,8);
    for(int i=0; i<9; i++)
    {
        cout<<a[i]<<" ";
    }
    cout<<endl;
}

template <class Type>
void Swap(Type &x,Type &y)
{
    Type temp = x;
    x = y;
    y = temp;
}

template <class Type>
int Partition(Type a[],int p,int r)
{
    int i = p,j = r + 1;
    Type x = a[p];

    while(true)
    {
        while(a[++i]<x && i<r);
        while(a[--j]>x);
        if(i>=j)
        {
            break;
        }
        Swap(a[i],a[j]);
    }
    a[p] = a[j];
    a[j] = x;
    return j;
}

template <class Type>
void QuickSort(Type a[],int p,int r)
{
    if(p<r)
    {
        int q = Partition(a,p,r);
        QuickSort(a,p,q-1);
        QuickSort(a,q+1,r);
    }
}