java快速排序算法代码

1. 如何用java实现快速排序，简答讲解下原理

快速排序思想：
通过对数据元素集合Rn 进行一趟排序划分出独立的两个部分。其中一个部分的关键字比另一部分的关键字小。然后再分别对两个部分的关键字进行一趟排序，直到独立的元素只有一个，此时整个元素集合有序。
快速排序的过程，对一个元素集合R[ low ... high ] ,首先取一个数（一般是R[low] ）做参照 ， 以R[low]为基准重新排列所有的元素。
所有比R[low]小的放前面，所有比R[low] 大的放后面，然后以R[low]为分界，对R[low ... high] 划分为两个子集和，再做划分。直到low >= high 。
比如：对R={37, 40, 38, 42, 461, 5, 7, 9, 12}进行一趟快速排序的过程如下(注:下面描述的内容中元素下表从 0 开始)：
开始选取基准 base = 37，初始位置下表 low = 0 ， high = 8 ， 从high=8，开始如果R[8] < base , 将high位置中的内容写入到R[low]中, 将high位置空出来, low = low +1 ;
从low开始探测，由于low=1 ， R[low] > base ,所以将R[low]写入到R[high] , high = high -1 ;
检测到low < high ,所以第一趟快速排序仍需继续:
此时low=1，high=7，因为 R[high] < base ,所以将 R[high] 写入到到R[low]中,low = low + 1;
从low开始探测,low = 2 , R[low] >base ,所以讲R[low]写入到R[high]，high=high-1;
继续检测到 low 小于high
此时low=2，high=6，同理R[high] < base ,将R[high] 写入到R[low]中，low=low+1;
从low继续探测,low = 3 , high=6 , R[low] > base , 将R[low]写入到R[high]中，high = high-1;
继续探测到low小于high
此时low=3，high=5，同理R[high] < base,将R[high]写入到R[low]中，low = low +1；
从low继续探测，low = 4，high=5，由于R[low] > base , 将R[low]写入到R[high]中，high = high -1 ;
此时探测到low == high == 4 ；该位置即是base所在的位置，将base写入到该位置中.
然后再对子序列Rs1 = {12,9,7,5} 和 Rs2={461,42,38,40}做一趟快速排序，直到Rsi中只有一个元素，或没有元素。
快速排序的Java实现：
private static boolean isEmpty(int[] n) {

return n == null || n.length == 0;
}

// ///////////////////////////////////////////////////
/**
* 快速排序算法思想——挖坑填数方法：
*
* @param n 待排序的数组
*/
public static void quickSort(int[] n) {
if (isEmpty(n))
return;
quickSort(n, 0, n.length - 1);
}

public static void quickSort(int[] n, int l, int h) {
if (isEmpty(n))
return;
if (l < h) {
int pivot = partion(n, l, h);
quickSort(n, l, pivot - 1);
quickSort(n, pivot + 1, h);
}
}

private static int partion(int[] n, int start, int end) {
int tmp = n[start];
while (start < end) {
while (n[end] >= tmp && start < end)
end--;
if (start < end) {
n[start++] = n[end];
}
while (n[start] < tmp && start < end)
start++;
if (start < end) {
n[end--] = n[start];
}
}
n[start] = tmp;
return start;
}
在代码中有这样一个函数：
public static void quickSortSwap(int[] n, int l, int h)
该函数可以实现，元素集合中特定的 l 到 h 位置间的数据元素进行排序。

2. java快速排序简单代码

.example-btn{color:#fff;background-color:#5cb85c;border-color:#4cae4c}.example-btn:hover{color:#fff;background-color:#47a447;border-color:#398439}.example-btn:active{background-image:none}div.example{width:98%;color:#000;background-color:#f6f4f0;background-color:#d0e69c;background-color:#dcecb5;background-color:#e5eecc;margin:0 0 5px 0;padding:5px;border:1px solid #d4d4d4;background-image:-webkit-linear-gradient(#fff,#e5eecc 100px);background-image:linear-gradient(#fff,#e5eecc 100px)}div.example_code{line-height:1.4em;width:98%;background-color:#fff;padding:5px;border:1px solid #d4d4d4;font-size:110%;font-family:Menlo,Monaco,Consolas,"Andale Mono","lucida console","Courier New",monospace;word-break:break-all;word-wrap:break-word}div.example_result{background-color:#fff;padding:4px;border:1px solid #d4d4d4;width:98%}div.code{width:98%;border:1px solid #d4d4d4;background-color:#f6f4f0;color:#444;padding:5px;margin:0}div.code div{font-size:110%}div.code div,div.code p,div.example_code p{font-family:"courier new"}pre{margin:15px auto;font:12px/20px Menlo,Monaco,Consolas,"Andale Mono","lucida console","Courier New",monospace;white-space:pre-wrap;word-break:break-all;word-wrap:break-word;border:1px solid #ddd;border-left-width:4px;padding:10px 15px} 排序算法是《数据结构与算法》中最基本的算法之一。排序算法可以分为内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。以下是快速排序算法：

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序 n 个项目要 Ο(nlogn) 次比较。在最坏誉渣宏状况下则需要 Ο(n2) 次比较，但这种状况并不常见。事实上，快速排序梁灶通常明显比其他 Ο(nlogn) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。

快速排序使用分治法（Divide and conquer）策略来把一个串行（list）分为两个子串行（sub-lists）。

快速排序又是一种分而治之思想在排序算法上的典型应用。本质上来看，快速排序应该算是在冒庆册泡排序基础上的递归分治法。

快速排序的名字起的是简单粗暴，因为一听到这个名字你就知道它存在的意义，就是快，而且效率高！它是处理大数据最快的排序算法之一了。虽然 Worst Case 的时间复杂度达到了 O(n?)，但是人家就是优秀，在大多数情况下都比平均时间复杂度为 O(n logn) 的排序算法表现要更好，可是这是为什么呢，我也不知道。好在我的强迫症又犯了，查了 N 多资料终于在《算法艺术与信息学竞赛》上找到了满意的答案：

快速排序的最坏运行情况是 O(n?)，比如说顺序数列的快排。但它的平摊期望时间是 O(nlogn)，且 O(nlogn) 记号中隐含的常数因子很小，比复杂度稳定等于 O(nlogn) 的归并排序要小很多。所以，对绝大多数顺序性较弱的随机数列而言，快速排序总是优于归并排序。
1. 算法步骤
从数列中挑出一个元素，称为 "基准"（pivot）;

重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；

递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；
2. 动图演示
代码实现 JavaScript 实例 function quickSort ( arr , left , right ) {
    var len = arr. length ,
        partitionIndex ,
        left = typeof left != 'number' ? 0 : left ,
        right = typeof right != 'number' ? len - 1 : right ;

    if ( left

3. java中快速排序的算法举个例子

package person.test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Random;

/**
* class name: RapidSort
* description: Java快速排序法：数组和集合
* @author Jr
*
*/
public class RapidSort {
private Random ran = new Random(); // 声明一个全局变量ran，用来随机生成整数

/**
* method name: sortArray
* description: 对数组的快速排序，只能用于int[]类型的数组
* @return
*/
private void sortArray() {
int[] array = new int[10]; // 声明数组长度为10
for (int i = 0 ; i < array.length; i++) {
array[i] = ran.nextInt(10) + 1; // 数组赋值
}
Arrays.sort(array);
System.out.println(Arrays.toString(array));
}

/**
* method name: sortList
* description: 对集合的快速排序，可以用于List<Object>类型数组，
* 隐含意思就是对所有类型数组都适用
* @return
*/
private void sortList() {
List<Integer> list = new ArrayList<Integer>();
for (int i = 0 ; i < 10; i++) {
list.add(ran.nextInt(10) + 1); // 给集合赋10个值
}
Collections.sort(list);
System.out.println(list);
}

public static void main(String[] args) {
RapidSort rs = new RapidSort();
rs.sortArray();
rs.sortList();
}
}

4. java问题

只要加到比较方法之中就可以
如：比较方法如下
for(int i=0;i<100;i++)
for(int j=i;j<100;j++){
if(array[i]>array[j]){
int temp=array[i];
array[i]=array[j];
array[j]=temp;
}
}
把：：
比较次数compare_count、交换次数exchange_count、探测次数probe_count）加到里面就可以

for(int i=0,compare_count=0;i<100;i++)
for(int j=i;j<100;j++){
if(array[i]>array[j]){
compare_count++;
int temp=array[i];
array[i]=array[j];
array[j]=temp;
exchange_count++;
}
}

就可以了
各种排序方法的综合比较

一、时间性能

按平均的时间性能来分，有三类排序方法：
时间复杂度为O(nlogn)的方法有：快速排序、堆排序和归并排序，其中以快速排序为最好；

时间复杂度为O(n2)的有：直接插入排序、起泡排序和简单选择排序，其中以直接插入为最好，特别是对那些对关键字近似有序的记录序列尤为如此；

时间复杂度为O(n)的排序方法只有，基数排序。

当待排记录序列按关键字顺序有序时，直接插入排序和起泡排序能达到O(n)的时间复杂度;而对于快速排序而言，这是最不好的情况，此时的时间性能蜕化为O(n2)，因此是应该尽量避免的情况。
简单选择排序、堆排序和归并排序的时间性能不随记录序列中关键字的分布而改变。
二、空间性能

指的是排序过程中所需的辅助空间大小。

1. 所有的简单排序方法(包括：直接插入、起泡和简单选择)和堆排序的空间复杂度为O(1)；

2. 快速排序为O(logn )，为栈所需的辅助空间;

3. 归并排序所需辅助空间最多，其空间复杂度为O(n );

4.链式基数排序需附设队列首尾指针，则空间复杂度为O(rd )。

三、排序方法的稳定性能

1. 稳定的排序方法指的是，对于两个关键字相等的记录，它们在序列中的相对位置，在排序之前和经过排序之后，没有改变。

2. 当对多关键字的记录序列进行LSD方法排序时，必须采用稳定的排序方法。

3. 对于不稳定的排序方法，只要能举出一个实例说明即可。

4. 快速排序和堆排序是不稳定的排序方法。

四、关于“排序方法的时间复杂度的下限”

本章讨论的各种排序方法，除基数排序外，其它方法都是基于“比较关键字”进行排序的排序方法，可以证明，这类排序法可能达到的最快的时间复杂度为O(n logn )。(基数排序不是基于“比较关键字”的排序方法,所以它不受这个限制)。

可以用一棵判定树来描述这类基于“比较关键字”进行排序的排序方法。

例如，对三个关键字进行排序的判定树如下：

描述排序的判定树有两个特点：

1.树上的每一次“比较”都是必要的;

2.树上的叶子结点包含所有可能情况。

则由上图所示“判定树的深度为4”可以推出“至多进行三次比较”即可完成对三个关键字的排序。反过来说，由此判定树可见，考虑最坏情况，“至少要进行三次比较”才能完成对三个关键字的排序。

对三个关键字进行排序的判定树深度是唯一的。即无论按什么先后顺序去进行比较，所得判定树的深度都是3。

当关键字的个数超过3之后，不同的排序方法其判定树的深度不同。例如，对4个关键字进行排序时，直接插入的判定树的深度为6, 而折半插入的判定树的深度为5。

可以证明，对4个关键字进行排序，至少需进行5次比较。因为，4个关键字排序的结果有4!=24种可能，即排序的判定树上必须有24个叶子结点，其深度的最小值为6。

一般情况下，对n个关键字进行排序，可能得到的结果有n! 种，由于含n! 个叶子结点的二叉树的深度不小于 , 则对n个关键字进行排序的比较次数至少是

。利用斯蒂林近似公式

所以，基于“比较关键字”进行排序的排序方法，可能达到的最快的时间复杂度为O(n logn )。

快速排序是对冒泡排序的一种改进。它的基本思想是：通过一躺排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一不部分的所有数据都要小，然后再按次方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

假设要排序的数组是A[1]……A[N]，首先任意选取一个数据（通常选用第一个数据）作为关键数据，然后将所有比它的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一躺快速排序。一躺快速排序的算法是：

1）、设置两个变量I、J，排序开始的时候I：=1，J：=N；

2）以第一个数组元素作为关键数据，赋值给X，即X：=A[1]；

3）、从J开始向前搜索，即由后开始向前搜索（J：=J-1），找到第一个小于X的值，两者交换；

4）、从I开始向后搜索，即由前开始向后搜索（I：=I+1），找到第一个大于X的值，两者交换；

5）、重复第3、4步，直到I=J；

例如：待排序的数组A的值分别是：（初始关键数据X：=49）

A[1] A[2] A[3] A[4] A[5] A[6] A[7]：

49 38 65 97 76 13 27

进行第一次交换后： 27 38 65 97 76 13 49

( 按照算法的第三步从后面开始找

进行第二次交换后： 27 38 49 97 76 13 65

( 按照算法的第四步从前面开始找>X的值，65>49,两者交换，此时I：=3 )

进行第三次交换后： 27 38 13 97 76 49 65

( 按照算法的第五步将又一次执行算法的第三步从后开始找

进行第四次交换后： 27 38 13 49 76 97 65

( 按照算法的第四步从前面开始找大于X的值，97>49,两者交换，此时J：=4 )

此时再执行第三不的时候就发现I=J，从而结束一躺快速排序，那么经过一躺快速排序之后的结果是：27 38 13 49 76 97 65，即所以大于49的数全部在49的后面，所以小于49的数全部在49的前面。

快速排序就是递归调用此过程——在以49为中点分割这个数据序列，分别对前面一部分和后面一部分进行类似的快速排序，从而完成全部数据序列的快速排序，最后把此数据序列变成一个有序的序列，根据这种思想对于上述数组A的快速排序的全过程如图6所示：

初始状态 {49 38 65 97 76 13 27}

进行一次快速排序之后划分为 {27 38 13} 49 {76 97 65}

分别对前后两部分进行快速排序 {13} 27 {38}

结束 结束 {49 65} 76 {97}

49 {65} 结束

结束

图6 快速排序全过程

1）、设有N（假设N=10）个数，存放在S数组中；
2）、在S[1。。N]中任取一个元素作为比较基准，例如取T=S[1]，起目的就是在定出T应在排序结果中的位置K，这个K的位置在：S[1。。K-1]<=S[K]<=S[K+1..N]，即在S[K]以前的数都小于S[K]，在S[K]以后的数都大于S[K]；

3）、利用分治思想（即大化小的策略）可进一步对S[1。。K-1]和S[K+1。。N]两组数据再进行快速排序直到分组对象只有一个数据为止。 1 2 3 4 5 6 7 8 9 10

如具体数据如下，那么第一躺快速排序的过程是：

数组下标：

45 36 18 53 72 30 48 93 15 36

5） 36 36 18 15 30 45 48 93 72 534） 36 36 18 15 45 30 48 93 72 533） 36 36 18 15 72 30 48 93 45 532） 36 36 18 45 72 30 48 93 15 53

program kuaisu(input,output);
const n=10;
var
s:array[1..10] of integer;
k,l,m:integer;

procere qsort(lx,rx:integer);
var
I,j,t:integer;
Begin
I:lx;j:rx;t:s[I];
Repeat
While (s[j]>t) and (j>I) do
Begin
k:=k+1;
j:=j-1
end;
if I<j then
begin
s[I]:=s[j];I:=I+1;l:=l+1;
while (s[I]<t) and (I<j) do
begin
k:=k+1;
I:=I+1
End;
If I<j then
begin
S[j]:=s[I];j:=j-1;l:=l+1;
End;
End;
Until I=j;
S[I]:=t;I:=I+1;j:=j-1;l:=l+1;
If lx<j then qsort(lx,j);
If I<rx then qsort(I,rx)
End;{过程qsort结束}

Begin
Writeln('input 10 integer num:');
For m:=1 to n do read(s[m]);
K:=0;l:=0;
Qsort(l,n);
Writeln('排序后结果是：')；
For m:=1 to n do write(s[m]:4)
End.

通过一躺排序将45放到应该放的位置K，这里K=6，那么再对S[1。。5]和S[6。。10]分别进行快速排序。程序代码如下：<49,两者交换，此时J:=6>

5. 求java快速排序的正确代码

一趟快速怕序的具体做法是：附设两个指针low和high,他们的初值分别为low和high,设枢轴记录的关键字为privotkey,则首先从high所指位置向前搜索找到第一个关键字小于pivotkey的记录和枢轴记录互相交换,然后从low所指向的位置起向后搜索,找到第一个关键字大于privotkey的记录和枢轴记录互相交换，重复这两步直至low==high位置.

import java.util.concurrent.Executor;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
public class 快速排序_1 {
public static void main(String[] args) throws InterruptedException {
int test[] = {15,23,56,7,13,52,20,7};
new 快速排序_1().qSort(test, 0, test.length-1);
for(int k:test) System.out.println(k);
}
public void qSort(int []array,int low,int high){
if(low
int privot=partition(array,low,high);
qSort(array,low,privot-1);
qSort(array,privot+1,high);
}
}
public int partition(int [] array,int low,int high){
/**
* 选择 low位置 作为曲轴(支点)
*/
int pivot=array[low];
int temp=0;
/**
* 如果 low
*/
while(low
/**
* 先从 high端 开始判断
*/
while(low=pivot) high--;
/**
* 进行 置换操作
*/
if(low
array[low]=array[high];
low++;
}
/**
* 从 low 端判断
*/
while(low
/**
* 进行 置换操作
*/
if(low
array[high]=array[low];
high--;
}
}
array[low]=pivot;
return low;
}
}

6. Java的排序算法有哪些

排序： 插入，冒泡，选择，Shell,快速排序

7. java怎么让数组的数字从大到小排序

将数字从大到小排序的方法：

例如简一点的冒泡排序，将第一个数字和后面的数字逐个比较大小，如果小于，则互换位置，大于则不动。此时，第一个数为数组中的最大数。然后再将第二个数与后面的数逐个比较，以次类推。

示例代码如下：
publicclassTest{

publicstaticvoidmain(String[]args){
int[]array={12,3,1254,235,435,236,25,34,23};
inttemp;
for(inti=0;i<array.length;i++){
for(intj=i+1;j<array.length;j++){
if(array[i]<array[j]){
temp=array[i];
array[i]=array[j];
array[j]=temp; //两个数交换位置
}
}
}
for(inti=0;i<array.length;i++){
System.out.print(array[i]+"");
}
}
}

数组对于每一门编程语言来说都是重要的数据结构之一，当然不同语言对数组的实现及处理也不尽相同。

Java 语言中提供的数组是用来存储固定大小的同类型元素。

你可以声明一个数组变量，如 numbers[100] 来代替直接声明 100 个独立变量 number0，number1，....，number99

(7)java快速排序算法代码扩展阅读

Java中利用数组进行数字排序一般有4种方法：

1、选择排序是先将数组中的第一个数作为最大或最小数，然后通过循环比较交换最大数或最小数与一轮比较中第一个数位置进行排序。

2、冒泡排序也是先将数组中的第一个数作为最大或最小数，循环比较相邻两个数的大小，满足条件就互换位置，将最大数或最小数沉底。

3、快速排序法主要是运用Arrays类中的Arrays.sort方法（）实现。

4、插入排序是选择一个数组中的数据，通过不断的插入比较最后进行排序。