首页 > 代码库 > 快速排序
快速排序
如果说希尔排序是简单插入排序的升级，堆排序是简单选择排序的升级，那么快速排序就是冒泡排序的升级了。相对于冒泡排序，快速排序增大了记录比较和移动的距离，将关键字较大的记录移动到后面，较小的移动到前面，从而减少总的比较和移动次数。
快速排序的基本思想：通过每一趟排序都将待排序的记录按照选定的关键字分成两部分，其中一部分记录的关键字均比另一部分的小，然后通过迭代然后在将每部分单独再分成两部分，如此循环，直到被分成的无法再分为止。
快速排序中每一趟排序的算法是：
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、将一部分递归用迭代替换
快速排序
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。