快速排序

如果说希尔排序是简单插入排序的升级,堆排序是简单选择排序的升级,那么快速排序就是冒泡排序的升级了。相对于冒泡排序,快速排序增大了记录比较和移动的距离,将关键字较大的记录移动到后面,较小的移动到前面,从而减少总的比较和移动次数。

快速排序的基本思想:通过每一趟排序都将待排序的记录按照选定的关键字分成两部分,其中一部分记录的关键字均比另一部分的小,然后通过迭代然后在将每部分单独再分成两部分,如此循环,直到被分成的无法再分为止。

快速排序中每一趟排序的算法是:

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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏抠抠空间

集合 (set) 的增删改查及 copy()方法

简介: 集合是无序的,不重复的数据集合,它里面的元素是可哈希的(不可变类型),但是集合本身是不可哈希(所以集合做不了字典的键)的。以下是集合最重要的两点: 1、...

30411
来自专栏十月梦想

ES6语法基础之const用法

在特殊情况下呢,const声明的不是一个常规的量或者字符串而是一个对象情况会怎么样呢?

1842
来自专栏从流域到海域

《笨办法学Python》 第32课手记

《笨办法学Python》 第32课手记 本节课讲for循环和list,list里类似于c中的数组,但有区别很大。C语言中的数组是数据类型相同的值的集合,list...

2059
来自专栏吾爱乐享

java学习之数组元素排序,冒泡排序和选择排序

1164
来自专栏C/C++基础

C++11 原生字符串

原生字符串(Raw String)指不进行转义“所见即所得”的字符串。很多编程语言早已支持原生字符串,如C#、Python、Shell等。C++作为一门高级程序...

1782
来自专栏lgp20151222

Class.forName()用法详解

主要功能 Class.forName(xxx.xx.xx)返回的是一个类 Class.forName(xxx.xx.xx)的作用是要求JVM查找并加载指定的类,...

1831
来自专栏Petrichor的专栏

python: map函数

对 sequence 中的 item 依次执行 function(item),将 执行结果 组成一个 List 返回。

2222
来自专栏noteless

[四] java虚拟机JVM编译器编译代码简介 字节码指令实例 代码到底编译成了什么形式

前文已经对虚拟机进行过了简单的介绍,并且也对class文件结构,以及字节码指令进行了详尽的说明

1822
来自专栏python百例

37-生成密码/验证码

此文件名为:randpass.py 思路: 1、设置一个用于随机取出字符的基础字符串,本例使用大小写字母加数字 2、循环n次,每次随机取出一个字符 3、...

981
来自专栏Java学习网

Java面试中最常见的10个问题,Java底层知识,花点时间学习一下

1.什么是 Java 虚拟机?为什么 Java 被称作是“平台无关的编程语言”? Java 虚拟机是一个可以执行 Java 字节码的虚拟机进程。Java 源文...

2675

扫码关注云+社区

领取腾讯云代金券