精选文章 快速排序法(三)

快速排序法(三)

作者:iteye_12023 时间: 2021-07-06 09:10:36
iteye_12023 2021-07-06 09:10:36
【摘要】
                    [b]說明[/b]
之前說過軸的選擇是快速排序法的效率關鍵之一,在這邊的快速排序法的軸選擇方式更加快了快速排序法的效率,它是來自演算法名書 Introduction to Algorithms 之中。
[b]解法[/b]
先說明這個快速排序法的概念,它以最右邊(或最左邊)的值s作比較的標準,將整個數列分為三個部份,一個是小於s的部份,一個是大於s的部...
[b]說明[/b]
之前說過軸的選擇是快速排序法的效率關鍵之一,在這邊的快速排序法的軸選擇方式更加快了快速排序法的效率,它是來自演算法名書 Introduction to Algorithms 之中。
[b]解法[/b]
先說明這個快速排序法的概念,它以最右邊(或最左邊)的值s作比較的標準,將整個數列分為三個部份,一個是小於s的部份,一個是大於s的部份,一個是未處理的部份,如下所示 :
[img]http://caterpillar.onlyfun.net/Gossip/AlgorithmGossip/images/quickSort3-1.jpg[/img]

在排序的過程中,i 與 j 都會不斷的往右進行比較與交換,最後數列會變為以下的狀態:
[img]http://caterpillar.onlyfun.net/Gossip/AlgorithmGossip/images/quickSort3-2.jpg[/img]

然後將s的值置於中間,接下來就以相同的步驟會左右兩邊的數列進行排序的動作,如下所示:
[img]http://caterpillar.onlyfun.net/Gossip/AlgorithmGossip/images/quickSort3-3.jpg[/img]

整個演算的過程,直接摘錄書中的虛擬碼來作說明:

QUICKSORT(A, p, r) 
if p < r
then q <-> QUICKSORT(A, p, q-1)
QUICKSORT(A, q+1, r)
end QUICKSORT

PARTITION(A, p, r)
x <-> i <-> for j <-> do if A[j] <=> then i <-> exchange A[i]<->A[j]
exchange A[i+1]<->A[r]
return i+1
end PARTITION



一個實際例子的演算如下所示:
[img]http://caterpillar.onlyfun.net/Gossip/AlgorithmGossip/images/quickSort3-4.jpg[/img]
public class Sort {
public static void quick(int[] number) {
sort(number, 0, number.length-1);
}

private static void sort(int[] number, int left, int right) {
if(left < right) {
int q = partition(number, left, right);
sort(number, left, q-1);
sort(number, q+1, right);
}

}

private static int partition(int number[], int left, int right) {
int i = left - 1;
for(int j = left; j < right; j++) {
if(number[j] <=> i++;
swap(number, i, j);
}
}
swap(number, i+1, right);
return i+1;
}

private static void swap(int[] number, int i, int j) {
int t = number[i];
number[i] = number[j];
number[j] = t;
}
}
勿删,copyright占位
您找到想要的结果了吗?
快速排序法(三)
提交成功!非常感谢您的反馈,我们会继续努力做到更好
分享文章到微博
分享文章到朋友圈

上一篇:Koogra 操作 Excel2007 VB.NET 版

下一篇:判断数据库,函数名,表名,存储过程名称等是否存在

您可能感兴趣

  • CRC查表法——表的由来 【转载】

    原文地址:http://www.xjtudll.cn/Exp/273/ On-line CRC calculation and free library https://www.lammertbies.nl/comm/info/crc-calculation.html 为了更容易理解这篇文章,拿出纸笔跟着算一遍吧。文中的一些假定:a0,a1,b...

  • C#面试题:快速排序法

    快速排序法:找到一个基准点key,和left,right,比较,比key小的值放到key的坐边,比key大的值,放到key的右边。 采用递归方式,重复执行判断,直到排序完成。 //快速排序法法 //排序找出基准点。       private static int SortID (int[] arr, int left, int right) ...

  • Java实现快速排序(快排)

    快速排序是冒泡排序的改进版,也是最好的一种内排序,在很多面试题中都会出现,也是作为程序员必须掌握的一种排序方法。 快速排序由C. A. R. Hoare在1962年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归...

  • 驱动专题:源码编写 3 简单button驱动(中断法+休眠唤醒机制)及测试程序

    汇总地址:https://blog.csdn.net/chichi123137/article/details/80946381 简单按键驱动,采用中断法 驱动程序如下,third_drv.c #include <linux/module.h> #include <linux/kernel.h> #include <linux/fs.h> #i...

  • 深入理解拉格朗日乘子法(Lagrange Multiplier) 和KKT条件(转)

    关于鞍点的定义可以参考论文 《鞍点定理在Lagrange乘数法上的应用》 下面这篇文章的重点是是提到了鞍点  在学习之前,先说一些题外话,由于博主学习模式识别没多久,所以可能对许多问题还没有深入的认识和正确的理解,如有不妥,还望海涵,另请各路前辈不吝赐教。        好啦,我们开始学习吧。。        同样假设有样本集: 由于线性...

  • POJ 1094 Sorting It All Out(入度法求拓扑排序,成环判断)

    题目来源:http://poj.org/problem?id=1094 问题描述 Sorting It All Out Time Limit: 1000MS   Memory Limit: 10000K Total Submissions: 39161   Accepted: 13808 Description An ascending...

  • 简单理解java快速排序法

    首先,下面的代码是我学了网上大神教的快速排序法修改的,代码里每一部分都有注释,不多说了,直接上代码,简单粗暴 public class QuickSort {      public static void main(String[] args) {          /*           * 思想:二分法           * 建议:不太理...

  • 分支定界算法+近邻法的matlab实现

    分支定界算法的步骤: 1 (初始化): B= ∞,L=0(当前水平) ,p=0(当前结点) 2(当前结点展开):将当前结点的所有直接后继结点放入一个目录表(活动表)中,对它们计算并存储D(x, Mp) 3 (规则...

CSDN

CSDN

中国开发者社区CSDN (Chinese Software Developer Network) 创立于1999年,致力为中国开发者提供知识传播、在线学习、职业发展等全生命周期服务。
快速排序法(三)介绍:华为云为您免费提供快速排序法(三)在博客、论坛、帮助中心等栏目的相关文章,同时还可以通过 站内搜索 查询更多快速排序法(三)的相关内容。| 移动地址: 快速排序法(三) | 写博客