如果说希尔排序是简单插入排序的升级,堆排序是简单选择排序的升级,那么快速排序就是冒泡排序的升级了。相对于冒泡排序,快速排序增大了记录比较和移动的距离,将关键字较大的记录移动到后面,较小的移动到前面,从而减少总的比较和移动次数。
快速排序的基本思想:通过每一趟排序都将待排序的记录按照选定的关键字分成两部分,其中一部分记录的关键字均比另一部分的小,然后通过迭代然后在将每部分单独再分成两部分,如此循环,直到被分成的无法再分为止。
快速排序中每一趟排序的算法是:
1)设置两个变量i、j,排序开始的时候:i=0,j=N-1;
2)以第一个数组元素作为关键数据,赋值给pivokey;
3)从j开始向前搜索,即由后开始向前搜索(j--),找到第一个小于pivokey的值L[j],将L[j]和L[i]互换;
4)从i开始向后搜索,即由前开始向后搜索(i++),找到第一个大于pivokey的L[i],将L[i]和L[j]互换;
5)重复第3、4步,直到i=j;
注意每一趟排序都要返回排序后关键字pivokey的位置,以便递归调用
快速排序按照上面的步骤就是,先进行一次上述的排序,然后得到key值的位置后,再将low到pivokey值位置,和pivokey值位置+1到high的位置分别进行上述排序,直到low和high相等为止。
基本的快速排序代码如下:
// 快速排序.cpp : 定义控制台应用程序的入口点。
//
#include "stdafx.h"
#include<iostream>
using namespace std;
void swap(int *L,int a, int b)
{
int temp;
temp=L[a];
L[a]=L[b];
L[b]=temp;
}
//将L数组中待排序记录[low..high]从L[low]为节点分成两部分,其中一部分的数据均比另一部分小,返回两部分的中间下标
int partition(int *L,int low,int high)
{
int pivokey=L[low];
while(low<high)
{
while(low<high&&L[high]>=pivokey)
{
high--;
}
swap(L,low,high);
while(low<high && L[low]<=pivokey)
{
low++;
}
swap(L,low,high);
}
return low;
}
void Qsort(int *L,int low,int high)
{
int pivor;
if(low<high)
{
pivor=partition(L,low,high);
Qsort(L,low,pivor);
Qsort(L,pivor+1,high);
}
}
void Quicksort(int *L,int n)
{
Qsort(L,0,n-1);
}
int _tmain(int argc, _TCHAR* argv[])
{
int a[9]={1,5,56,45,654,4,2,4,6};
Quicksort(a,9);
for(int i=0;i<9;i++)
{
cout<<a[i]<<' ';
}
return 0;
}
快速排序还有一些可以优化的部分:
1、pivokey值的选取
上述快速排序中pivokey的值总是取记录中的第一个数据,如果它的大小刚好位于序列的中间位置,则排序效率很高,但是如果正好其值是记录中最大或最小的,这是快速排序的效率就和普通的冒泡排序差不多了,所以要尽量选取记录中中间大小的pivokey值。而对于基本有序的记录,第一个数据很有可能在边上,所以可以每次选取记录左端,右端和中间三个数据,然后进行排序,选择中间大小的作为pivokey。
2、使用替换代替交换
partition函数中的swap函数都用替换的方式。
3、记录中数据较小时,由于递归会影响性能,那么这是还不如使用插入排序
设定个记录长度的阈值,当被排序记录小于阈值时,直接使用插入排序,否则使用快速排序
4、将一部分递归用迭代替换
下面是按照1、2进行优化后的快速排序程序
// 优化后的快速排序.cpp : 定义控制台应用程序的入口点。
//
#include "stdafx.h"
#include<iostream>
using namespace std;
void swap(int *L,int a, int b)
{
int temp;
temp=L[a];
L[a]=L[b];
L[b]=temp;
}
//将L数组中待排序记录[low..high]从L[low]为节点分成两部分,其中一部分的数据均比另一部分小,返回两部分的中间下标
int partition(int *L,int low,int high)
{
////优化1:尽量选取中间大小的pivokey
int m=low+(low+high)/2;
if(L[low]>L[high])//先保证左边比右边小
{
swap(L,low, high);
}
if(L[m]>L[high])//再保证中间比右边小
{
swap(L,m, high);
}
if(L[m]>L[low])//最后保证左边的数就是最中间的值
{
swap(L,m, high);
}
//////////////////////////////////////
int pivokey=L[low];
int temp= pivokey;//用于优化2
while(low<high)
{
while(low<high&&L[high]>=pivokey)
{
high--;
}
//swap(L,low,high);
L[low]=L[high];//优化2
while(low<high && L[low]<=pivokey)
{
low++;
}
//swap(L,low,high);
L[high]=L[low];//优化2
}
L[low]=temp;//优化2
return low;
}
void Qsort(int *L,int low,int high)
{
int pivor;
if(low<high)
{
pivor=partition(L,low,high);
Qsort(L,low,pivor);
Qsort(L,pivor+1,high);
}
}
void Quicksort(int *L,int n)
{
Qsort(L,0,n-1);
}
int _tmain(int argc, _TCHAR* argv[])
{
int a[9]={1,5,56,45,654,4,2,4,6};
Quicksort(a,9);
for(int i=0;i<9;i++)
{
cout<<a[i]<<' ';
}
return 0;
}
这两天发现这位大神总结的快速排序比较容易理解在此给出连接:http://blog.csdn.net/morewindows/article/details/6684558