快速排序(QuickSort)的确是该排序方法的一个恰如其是的命名,因为恰到好处时它是迄今为止在内排序方面最快的一种排序方法。快速排序的应用非常广泛,其中典型的应用就是UNIX系统调用库函数例程中的qsort函数。但是有趣的是快序排序往往由于最差性能时间代价而在默写应用中无法采用。
快速排序的算法;
1、选择一个轴值(piovt),把要排序的数组中小于轴值的元素换到轴值前面,比轴值大的元素换到轴值后面。
2、以上面的轴值为标志,将原来的一组数据分成两组,(这也称是该数组的一个分割(partition)),再分别对这个分割的两部分实行步骤1.最后则就排好了。
快排算法代码:
void QuickSort::QSort(int index1,int index2)
{
if(index2 <= index1) return;//结束条件
int piovt = FindPiovt(index1,index2);//寻找轴值
Swap(piovt,index2);
int k = Partition(index1,index2,p[index2]);//数组的分割
Swap(k,index2);
QSort(index1,k-1);
QSort(k+1,index2);
}
对于寻找轴值piovt,现在一般选择中间的额值,方便写算法。但是在实际中选择大小在中间的元素,算法比较复杂,但是这能提高快速排序的时间代价性能。
int QuickSort::FindPiovt(int x1,int x2)
{
return (x2+x1)/2;//在这里选择中间的值为轴值
}
对于分割算法。
1、先将轴值和最后一个元素交换。
2、从该分割的第一个元素开始向后找,从该分割倒数第二个元素向前找,向后找到比轴值大的向前找到比轴值小的元素,然后将两个元素交换。直到寻找的路线交叉,即向前找的元素到向后找元素的前面了。
3、此时在交换最后的左右标志值。
4、返回分割的标志位
int QuickSort::Partition(int l,int r,int& Piovt)
{
do
{
while(p[l]<Piovt)
{
l++;
}
while(r!=0&&p[--r]>Piovt)
{
}
Swap(l,r);
}while(l<r);
Swap(l,r);
ShowElem();
return l;
}
下面是完整代码
//QuickSort.h
#pragma once
#include<fstream>
#include<iostream>
using namespace std;
const int Max = 40;
class QuickSort
{
public:
QuickSort();//构造数据
~QuickSort();//释放内存
void QSort(int index1,int index2);//快速排序
int FindPiovt(int x1,int x2);//寻找轴值
void Swap(int i,int j);//交换下标为ij的数据
void ShowElem();//打印数据
int Partition(int l,int r,int &);//分割
int GetSize();//返回数据规模
private:
int *p;
int Size;
};
QuickSort::QuickSort()
{
p = new int[Max];
int a,i=0;
ifstream infile("f1.txt",ios::in);//这里实现文件操作也可以改成自己传入数据的代码
if(!infile)
{
cout<<"文件打开失败!"<<endl;
exit(0);
}
while(infile>>a)
{
p[i++]=a;
}
infile.close();
Size = i;
}
QuickSort::~QuickSort()
{
delete []p;
}
void QuickSort::QSort(int index1,int index2)
{
if(index2 <= index1) return;//结束条件
int piovt = FindPiovt(index1,index2);//寻找轴值
Swap(piovt,index2);
int k = Partition(index1,index2,p[index2]);//数组的分割
Swap(k,index2);
QSort(index1,k-1);
QSort(k+1,index2);
}
int QuickSort::FindPiovt(int x1,int x2)
{
return (x2+x1)/2;//在这里选择中间的值为轴值
}
void QuickSort::Swap(int i,int j)
{
int temp = p[i];
p[i] = p[j];
p[j] = temp;
cout<<"交换"<<p[i]<<"和"<<p[j]<<endl;//这只是显示排序过程方便检查
}
void QuickSort::ShowElem()
{
for(int i = 0;i< Size;i++)
{
std::cout<<p[i]<<" ";
if(9 == i%10)
std::cout<<std::endl;
}
}
int QuickSort::Partition(int l,int r,int& Piovt)
{
do
{
while(p[l]<Piovt)
{
l++;
}
while(r!=0&&p[--r]>Piovt)
{
}
Swap(l,r);
}while(l<r);
Swap(l,r);
ShowElem();
return l;
}
int QuickSort::GetSize()
{
return Size;
}
//main.cpp
#include<iostream>
using namespace std;
#include"QuickSort.h"
int main()
{
QuickSort qsort;
cout<<"原始数据:\n";
qsort.ShowElem();
cout<<"排序过程:\n";
qsort.QSort(0,qsort.GetSize()-1);
cout<<"最终结果:\n";
qsort.ShowElem();
return 0;
}
分享到:
相关推荐
快速排序快速排序 快速排序 快速排序 快速排序 快速排序
1、熟悉快速排序的串行算法 2、熟悉快速排序的并行算法 3、实现快速排序的并行算法 3.2 实验环境及软件 单台或联网的多台PC机,Linux操作系统,MPI系统。 3.3实验内容 1、快速排序的基本思想 2、单处理机上快速...
快速排序快速排序快速排序快速排序快速排序快速排序快速排序快速排序快速排序快速排序快速排序快速排序快速排序快速排序快速排序快速排序快速排序快速排序快速排序快速排序快速排序快速排序快速排序快速排序快速排序...
(1)用随机快速排序的方法,对输入的数值以从大到小的顺序进行快速排序。 (2)对随机快速排序和冒泡排序这两种排序方法进行比较,测试其在不同数值大小的情况下算法运行的时间复杂度。 二、 实验要求 快速排序...
快速排序,比较高效的排序算法之一。这是一个例子,一个关于快速排序的例子。
(1) 完成5种常用内部排序算法的演示,5种排序算法为:快速排序,直接插入排序,选择排序,堆排序,希尔排序; (2) 待排序元素为整数,排序序列存储在数据文件中,要求排序元素不少于30个; (3) 演示程序开始,...
全面的排序算法实现,包括插入排序、合并排序、堆排序、快速排序。 堆排序:HeapSort 讲解详见http://blog.csdn.net/fly_yr/article/details/8550701 插入排序:InSertion_Sort 讲解详见...
用函数实现快速排序,并输出每次分区后排序的结果 Input 第一行:键盘输入待排序关键的个数n 第二行:输入n个待排序关键字,用空格分隔数据 Output 每行输出每趟排序的结果,数据之间用一个空格分隔 Sample Input ...
C语言实现多种链表快速排序
快速排序是实际运用中用的最多的算法,虽然它在最坏的情况下会达到n^2,但它的平均性能非常好,期望时间复杂度为nlgn,而且隐含的常数因子非常小,并且是原址排序。 快速排序原理:从一组数中任意选出一个数,将...
(1) 冒泡排序和快速排序; (2) 插入排序和希尔排序; (3) 选择排序和堆排序; (4) 递归和非递归的归并排序。 2. 产生不同规模和分布的数据,以 Excel 生成算法执行时间 T(n)关于输入规模 n 的曲线的形式,...
快速排序是对冒泡排序的一种本质改进。它的基本思想是通过一趟 扫描后,使得排序序列的长度能大幅度地减少。在冒泡排序中,一次 扫描只能确保最大数值的数移到正确位置,而待排序序列的长度可能只 减少1。快速...
快速排序的并行实现,提高效率。快速排序算法并行化的一个简单思想是,对每次划分过后所得到的两个序列分别使用两个处理器完成递归排序。
选择排序 冒泡排序 插入排序 合并排序 快速排序算法原理及代码实现 不同排序算法时间效率的经验分析方法 验证理论分析与经验分析的一致性 当面临巨大数据量的排序的时候,还是优先选择合并排序算法和快速排序算法。...
1)实现快速排序算法。 2)要求输入待排序元素个数,利用随机函数生成指定数目的元素,元素值的 取值范围为[10, 1000000]。 3)运行快速排序程序对所生成元素进行排序,要求将元素的初始输入序列和 排序后的结果序列...
快速排序算法,C语言 快速排序(Quicksort)是对冒泡排序的一种改进。由C. A. R. Hoare在1962年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有...
冒泡排序和快速排序的时间性能 冒泡排序和快速排序的时间性能 冒泡排序和快速排序的时间性能 冒泡排序和快速排序的时间性能 冒泡排序和快速排序的时间性能
知道快速排序算法的思想,但是一直都没有动手写,今天写了下,发现还不是那么容易
按所推荐的程序在IE下跑了下,的确,排序耗时很小。 代码如下: [removed] /* * 洗牌 */ function ... /* * 快速排序,按某个属性,或按“获取排序依据的函数”,来排序. * @method soryBy * @static * @
快速排序算法是当前使用最多的排序算法之一,它的基本思想是分治法,选择一个划分元,将小于划分元的元素放在左边,将大于划分元的元素放在右边,针对左右子序列重复此过程,直到序列为空或者只有一个元素,这是基本...