快速排序
概述
快速排序和归并排序一样也是分而治之策略的应用，基本思路是在数组中选取一个主元，以它为标准，遍历数组把小于它的数放在右边，大于它的数放在左边。递归上述过程直至有序。
选主元
选主元与划分子集这两个问题关乎快速排序的效率问题。选主元有很多方式，比如直接那第一个数作主元，那么当数组基本有序时那么时间复杂度就变成了O(n^2)了，而不是O(nlogn)，也可以利用随机函数来选取下标，从而确定主元，但是rand()函数却是O(n^2)的时间复杂度。比较好的做法是选取数组头、中、尾的中位数作主元。算法如下：
int Median3(int* data ,int left , int right)
{
//这里swap函数是利用c++的引用方法
int mid = (left+right)/2;
if(data[left]>data[mid]){
Swap(data[left],data[mid]);
}
if(data[left]>data[right]){
Swap(data[left],data[right]);
}
if(data[mid]>data[right]){
Swap(data[mid],data[right]);
}
//这个时候已经满足
//data[left]<=data[mid]<=data[right]
return data[mid];
}子集划分
主要思想：构造前后两个指针low = 0，high = size-1,分别找到左边第一个大于主元的数，右边第一个小于主元的数，如果low
void QuickSort(int* data ,int left,int right)
{
if(left >= right){
return;
}
int pivot = Median3(data,left,right);
int low,high;
low = left;
high = right;
//将序列中比基准小的移到基准左边，大的移到右边
//以下是子集划分
while(1){
//找到左边第一个大于主元的数
while(data[++low] < pivot );
//找到邮编第一个小于主元的数
while(data[--high] > pivot);
if(low < high){
Swap(&data[low],&data[high]);
}else{
break;
}
}
QuickSort(data,left,low-1);//递归快速排序左半部分
QuickSort(data,low+1,right);//递归快速排序右半部分
}全部代码
#include <iostream>
#include <cstdlib>
using namespace std;
//初始化数组
void SetArray(int* data,int size)
{
//srand(time(0));
cout<<"随机初始化"<<size<<"个数"<<endl;
for(int i = 0 ; i < size ; i++){
data[i] =rand()%100+1;
}
}
void Print(int* data ,int size)
{
for(int i = 0 ; i < size ; i++){
cout<<data[i]<<" ";
}
cout<<endl;
}
void Swap(int* a ,int* b)
{
int tmp = *a;
*a = *b;
*b = tmp;
}
int Median3(int* data ,int left , int right)
{
//这里swap函数是利用c++的引用方法
int mid = (left+right)/2;
if(data[left]>data[mid]){
Swap(&data[left],&data[mid]);
}
if(data[left]>data[right]){
Swap(&data[left],&data[right]);
}
if(data[mid]>data[right]){
Swap(&data[mid],&data[right]);
}
//这个时候已经满足
//data[left]<=data[mid]<=data[right]
return data[mid];
}
void QuickSort(int* data ,int left,int right)
{
if(left >= right){
return;
}
int pivot = Median3(data,left,right);
int low,high;
low = left;
high = right;
//将序列中比基准小的移到基准左边，大的移到右边
//以下是子集划分
while(1){
//找到左边第一个大于主元的数
while(data[++low] < pivot );
//找到邮编第一个小于主元的数
while(data[--high] > pivot);
if(low < high){
Swap(&data[low],&data[high]);
}else{
break;
}
}
QuickSort(data,left,low-1);//递归快速排序左半部分
QuickSort(data,low+1,right);//递归快速排序右半部分
}
//快速排序
void Quick_Sort(int* data ,int size)
{
QuickSort(data,0,size-1);
}
int main()
{
cout<<"请输入数组长度:"<<endl;
int size,*data;
cin>>size;
data = new int[size];
SetArray(data,size);
cout<<"快速排序前："<<endl;
Print(data,size);
cout<<"快速排序后："<<endl;
Quick_Sort(data,size);
Print(data,size);
SetArray(data,size);
cout<<"前："<<endl;
Print(data,size);
cout<<"后："<<endl;
Move(data,size);
Print(data,size);
cout<<"请输入一个数:"<<endl;
int k;
cin>>k;
SetArray(data,size);
Print(data,size);
cout<<"数组中第"<<k<<"小的数为："<<endl;
cout<<FindKth(data,0,size-1,k-1);
SetArray(data,size);
Print(data,size);
cout<<FindMax(data,size);
return 0;
} 截图：
这里写图片描述
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2017-09-24，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录