转载http://158067568.iteye.com/blog/914049
快排是分治法的一个应用,快排主要是通过一个设定枢轴,然后以这个枢轴为标杆,将待排序列按大小分成比枢轴大的,和比枢轴小的两部分。然后在对划分完的子序列进行快排,知道子序列中元素的个数为
1
位置。
快速排序实现
快排是程序员必须掌握的,举一个例子来解释,如下图:
<!--[endif]-->
首先选定枢轴,一般设置
low
所对应的元素位置为枢轴,如图选定的枢轴为
26
。
在高位指针始终不小于低位指针的前提下:
高位指针开始判断其是否比枢轴值大,如果符合,高位指针减
1
,继续寻找,直到找到不符合的情况,然后把该值赋给此时低位所在位置。
低位指针开始判断其是否比枢轴值小,如果符合,低位指针加
1
,继续寻找,直到找到不符合情况,然后将该值赋给此时高位指针所指位置。
如此反复,知道低位与高位指针重合,此时,在讲当前的枢轴值赋给低位指针所指的值。这样就完成了一次排序。
此时枢轴值就到了其最终位置上,然后继续对以枢轴为轴的两部分进行排序。
JAVA
实现快速排序
-
package
cn.edu.heut.zcl;
-
-
public
class
QuickSort {
-
-
-
-
-
-
-
-
public
static
void
quiteSort(
int
[] o ,
int
low ,
int
hight ){
-
if
(low < hight){
-
int
povitePosition = adjust(o,low,hight);
-
quiteSort( o , low , povitePosition - 1
);
-
quiteSort( o , povitePosition + 1
, hight );
-
}
-
}
-
-
-
-
-
-
-
-
private
static
int
adjust(
int
[] o ,
int
low ,
int
hight ){
-
int
pivote = o[low];
-
while
(low < hight){
-
while
(hight > low && compare( pivote , o[hight] ) <=
0
){
-
hight -- ;
-
}
-
o[low] = o[hight] ;
-
while
(low < hight && compare( pivote , o[low] ) >=
0
){
-
low ++ ;
-
}
-
o[hight] = o[low];
-
}
-
o[low] = pivote ;
-
return
low;
-
}
-
-
-
-
-
-
-
-
private
static
int
compare(
int
num1,
int
num2) {
-
return
num1 - num2 ;
-
}
-
-
-
-
public
static
void
main(String[] args) {
-
int
[] i = {
26
,
53
,
48
,
15
,
13
,
46
,
32
,
15
};
-
quiteSort(i, 0
, i.length-
1
);
-
for
(
int
ii:i){
-
System.out.print(ii+" "
);
-
}
-
}
-
}
分享到:
相关推荐
### 快速排序知识点解析 #### 一、快速排序简介 快速排序是一种高效的排序算法,由英国计算机科学家托尼·霍尔(Tony Hoare)在1960年提出。它采用分治策略来把一个序列分为较小和较大的两个子序列,然后递归地...
快速排序是一种高效的排序算法,由英国计算机科学家C.A.R. Hoare在1960年提出,它的基本思想是通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,然后分别对这两部分记录...
快速排序快速排序 快速排序 快速排序 快速排序 快速排序
快速排序是一种高效的排序算法,在计算机科学和数学中被广泛研究。其基本原理是分治法策略,即将一组数据分为两个子序列并分别进行排序。快速排序期望的时间复杂度为O(nlogn),但在最坏的情况下,它的时间复杂度可...
快速排序是一种高效的排序算法,由英国计算机科学家C.A.R. Hoare在1960年提出。它的基本思想是分治法(Divide and Conquer),即把一个大问题分解成若干个小问题来解决,最终将小问题的结果合并得到原问题的解。在这...
本主题将深入探讨四种常见的排序算法:堆排序、快速排序以及两种未在标题中明确提到但同样重要的排序方法——基数排序和计数排序。 首先,让我们详细了解一下堆排序。堆排序是一种基于比较的排序算法,利用了数据...
快速排序是一种高效的排序算法,由英国计算机科学家C.A.R. Hoare在1960年提出。它的基本思想是分治法,通过一趟排序将待排序的数据分割成独立的两部分,其中一部分的所有数据都比另一部分的所有数据都要小,然后再按...
快速排序是一种高效的排序算法,由英国计算机科学家C.A.R. Hoare在1960年提出。它的基本思想是分治策略,通过一趟排序将待排序的数据分割成独立的两部分,其中一部分的所有数据都比另一部分的所有数据都要小,然后再...
(1)用随机快速排序的方法,对输入的数值以从大到小的顺序进行快速排序。 (2)对随机快速排序和冒泡排序这两种排序方法进行比较,测试其在不同数值大小的情况下算法运行的时间复杂度。 二、 实验要求 快速排序...
快速排序是一种高效的排序算法,由英国计算机科学家C.A.R. Hoare在1960年提出。它的基本思想是分治法(Divide and Conquer),通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的...
冒泡排序和快速排序的时间性能 冒泡排序和快速排序是两种常用的排序算法,它们的时间性能是开发者和研究人员所关心的热点话题。在本文中,我们将对冒泡排序和快速排序的时间性能进行深入分析和比较。 冒泡排序是一...
快速排序是一种高效的排序算法,由英国计算机科学家托尼·霍尔于1960年提出。它采用分治策略来把一个序列分为较小的两个子序列,然后递归地对子序列进行排序,最终合并得到有序序列。快速排序在平均情况下的时间...
快速排序是一种高效的排序算法,由英国计算机科学家C.A.R. Hoare在1960年提出。它基于分治法的策略,通过选取一个基准值并重新排列数组,将问题分解为较小的部分,然后递归地对这些部分进行排序,最终达到整个序列...
在本文中,我们将深入探讨基于FPGA的并行快速排序算法,特别关注“位宽可设”的特性。这种算法能够高效地处理大量数据,并且在硬件实现上具有很高的灵活性。我们将从以下几个方面来阐述这个主题: 一、快速排序算法...
快速排序是一种高效的排序算法,由英国计算机科学家C.A.R. Hoare在1960年提出。它基于分治策略,通常比其他O(n^2)时间复杂度的排序算法更快,平均时间复杂度为O(n log n)。在本项目中,“快速排序演示程序/vc++/mfc...
(1) 完成5种常用内部排序算法的演示,5种排序算法为:快速排序,直接插入排序,选择排序,堆排序,希尔排序; (2) 待排序元素为整数,排序序列存储在数据文件中,要求排序元素不少于30个; (3) 演示程序开始,...
根据给定文件的信息,我们可以总结出以下关于“数据结构 快速排序 输出每一趟结果”的知识点: ### 一、快速排序的基本概念 快速排序是一种高效的排序算法,采用分治法策略来把一个序列分为较小和较大的两个子序列...
快速排序和冒泡排序是两种常见的排序算法,它们在计算机科学中扮演着重要的角色,特别是在数据处理和优化程序性能方面。本篇文章将深入探讨这两种排序算法的原理、效率以及它们在C#编程语言中的实现。 首先,让我们...