java快速排序简单代码 快速排序法java代码实现

请用java语言编写排序程序。

参考代码如下，可以按需求自己修改

成都创新互联-专业网站定制、快速模板网站建设、高性价比西峰网站开发、企业建站全套包干低至880元,成熟完善的模板库,直接使用。一站式西峰网站制作公司更省心,省钱,快速模板网站建设找我们，业务覆盖西峰地区。费用合理售后完善，10余年实体公司更值得信赖。

import java.util.Date;

public class SortThread {

public static void main(String[] args) {

//产生一个随机数组

int[] ary = getArray();

//启动冒泡排序线程

new Thread(new MaoPao(ary)).start();

//启动快速排序线程

new Thread(new KuaiSu(ary)).start();

}

private static int[] getArray() {

//建议数字n不要超过1百万，十万左右就好了

int n = (int) (Math.random()*1000000)+11;

int[] ary= new int[n];

System.out.println("n的值是" + n);

for (int i = 0; i  ary.length; i++) {

ary[i] = (int) (Math.random()*100000);

}

return ary;

}

}

//冒泡排序

class MaoPao implements Runnable {

int[] ary;

public MaoPao(int[] ary) {

this.ary = ary;

}

@Override

public void run() {

long st = System.currentTimeMillis();

System.out.println(new Date() + "冒泡排序线程：开始执行排序");

for (int i = 0; i  ary.length - 1; i++) {

for (int j = 0; j  ary.length - i - 1; j++) {

if (ary[j]  ary[j + 1]) {

int temp = ary[j];

ary[j] = ary[j + 1];

ary[j + 1] = temp;

}

}

}

long et = System.currentTimeMillis();

System.out.println(new Date() + "冒泡排序线程完成排序,耗费时间" + (et - st) + "毫秒");

for (int i = 0; i  ary.length; i++) {

System.out.println(ary[i]+" ");

}

}

}

//快速排序

class KuaiSu implements Runnable {

int[] ary;

public KuaiSu(int[] ary) {

this.ary = ary;

}

@Override

public void run() {

long st = System.currentTimeMillis();

System.out.println(new Date() + "快速排序线程：开始执行排序");

quickSort(ary, 1, ary.length);

long et = System.currentTimeMillis();

System.out.println(new Date() + "快速排序线程排序完成,耗费时间" + (et - st) + "毫秒");

for (int i = 0; i  ary.length; i++) {

System.out.println(ary[i]+" ");

}

}

public static int Partition(int a[], int p, int r) {

int x = a[r - 1];

int i = p - 1;

int temp;

for (int j = p; j = r - 1; j++) {

if (a[j - 1] = x) {

i++;

temp = a[j - 1];

a[j - 1] = a[i - 1];

a[i - 1] = temp;

}

}

temp = a[r - 1];

a[r - 1] = a[i + 1 - 1];

a[i + 1 - 1] = temp;

return i + 1;

}

public static void quickSort(int a[], int p, int r) {

if (p  r) {

int q = Partition(a, p, r);

quickSort(a, p, q - 1);

quickSort(a, q + 1, r);

}

}

}

java 编写一个程序,输入3个整数,然后程序将对这三个整数按照从大到小进行排列

可以实现比较器Comparator来定制排序方案，同时使用Colletions.sort的方式进行排序，代码如下：

public void sortDesc(ListLong s){

Collections.sort(s, new ComparatorLong() {

public int compare(Long o1, Long o2) {

Long result = o2 - o1;

return result.intValue();

}

});

s.forEach(item-{

System.out.print(item +" ");

});

}

同时常用的比较排序算法主要有：冒泡排序，选择排序，插入排序，归并排序，堆排序，快速排序等。

java的冒泡排序实现如下：

public static void bubbleSort(int []arr) {        for(int i =0;iarr.length-1;i++) {            for(int j=0;jarr.length-i-1;j++) {//-1为了防止溢出                if(arr[j]arr[j+1]) {                    int temp = arr[j];                                         arr[j]=arr[j+1];                                         arr[j+1]=temp;            }            }            }    }

还有非比较排序，时间复杂度可以达到O(n)，主要有：计数排序，基数排序，桶排序等。

写一个简单的JAVA排序程序

// 排序

public class Array

{

public static int[] random(int n) //产生n个随机数，返回整型数组

{

if (n0)

{

int table[] = new int[n];

for (int i=0; itable.length; i++)

table[i] = (int)(Math.random()*100); //产生一个0～100之间的随机数

return table; //返回一个数组

}

return null;

}

public static void print(int[] table) //输出数组元素

{

if (table!=null)

for (int i=0; itable.length; i++)

System.out.print(" "+table[i]);

System.out.println();

}

public static void insertSort(int[] table) //直接插入排序

{ //数组是引用类型，元素值将被改变

System.out.println("直接插入排序");

for (int i=1; itable.length; i++) //n-1趟扫描

{

int temp=table[i], j; //每趟将table[i]插入到前面已排序的序列中

// System.out.print("移动");

for (j=i-1; j-1 temptable[j]; j--) //将前面较大元素向后移动

{

// System.out.print(table[j]+", ");

table[j+1] = table[j];

}

table[j+1] = temp; //temp值到达插入位置

System.out.print("第"+i+"趟: ");

print(table);

}

}

public static void shellSort(int[] table) //希尔排序

{

System.out.println("希尔排序");

for (int delta=table.length/2; delta0; delta/=2) //控制增量，增量减半，若干趟扫描

{

for (int i=delta; itable.length; i++) //一趟中若干组，每个元素在自己所属组内进行直接插入排序

{

int temp = table[i]; //当前待插入元素

int j=i-delta; //相距delta远

while (j=0 temptable[j]) //一组中前面较大的元素向后移动

{

table[j+delta] = table[j];

j-=delta; //继续与前面的元素比较

}

table[j+delta] = temp; //插入元素位置

}

System.out.print("delta="+delta+" ");

print(table);

}

}

private static void swap(int[] table, int i, int j) //交换数组中下标为i、j的元素

{

if (i=0 itable.length j=0 jtable.length i!=j) //判断i、j是否越界

{

int temp = table[j];

table[j] = table[i];

table[i] = temp;

}

}

public static void bubbleSort(int[] table) //冒泡排序

{

System.out.println("冒泡排序");

boolean exchange=true; //是否交换的标记

for (int i=1; itable.length exchange; i++) //有交换时再进行下一趟，最多n-1趟

{

exchange=false; //假定元素未交换

for (int j=0; jtable.length-i; j++) //一次比较、交换

if (table[j]table[j+1]) //反序时，交换

{

int temp = table[j];

table[j] = table[j+1];

table[j+1] = temp;

exchange=true; //有交换

}

System.out.print("第"+i+"趟: ");

print(table);

}

}

public static void quickSort(int[] table) //快速排序

{

quickSort(table, 0, table.length-1);

}

private static void quickSort(int[] table, int low, int high) //一趟快速排序，递归算法

{ //low、high指定序列的下界和上界

if (lowhigh) //序列有效

{

int i=low, j=high;

int vot=table[i]; //第一个值作为基准值

while (i!=j) //一趟排序

{

while (ij vot=table[j]) //从后向前寻找较小值

j--;

if (ij)

{

table[i]=table[j]; //较小元素向前移动

i++;

}

while (ij table[i]vot) //从前向后寻找较大值

i++;

if (ij)

{

table[j]=table[i]; //较大元素向后移动

j--;

}

}

table[i]=vot; //基准值的最终位置

System.out.print(low+".."+high+", vot="+vot+" ");

print(table);

quickSort(table, low, j-1); //前端子序列再排序

quickSort(table, i+1, high); //后端子序列再排序

}

}

public static void selectSort(int[] table) //直接选择排序

{

System.out.println("直接选择排序");

for (int i=0; itable.length-1; i++) //n-1趟排序

{ //每趟在从table[i]开始的子序列中寻找最小元素

int min=i; //设第i个数据元素最小

for (int j=i+1; jtable.length; j++) //在子序列中查找最小值

if (table[j]table[min])

min = j; //记住最小元素下标

if (min!=i) //将本趟最小元素交换到前边

{

int temp = table[i];

table[i] = table[min];

table[min] = temp;

}

System.out.print("第"+i+"趟: ");

print(table);

}

}

private static void sift(int[] table, int low, int high) //将以low为根的子树调整成最小堆

{ //low、high是序列下界和上界

int i=low; //子树的根

int j=2*i+1; //j为i结点的左孩子

int temp=table[i]; //获得第i个元素的值

while (j=high) //沿较小值孩子结点向下筛选

{

if (jhigh table[j]table[j+1]) //数组元素比较（改成为最大堆）

j++; //j为左右孩子的较小者

if (temptable[j]) //若父母结点值较大（改成为最大堆）

{

table[i]=table[j]; //孩子结点中的较小值上移

i=j; //i、j向下一层

j=2*i+1;

}

else

j=high+1; //退出循环

}

table[i]=temp; //当前子树的原根值调整后的位置

System.out.print("sift "+low+".."+high+" ");

print(table);

}

public static void heapSort(int[] table)

{

System.out.println("堆排序");

int n=table.length;

for (int j=n/2-1; j=0; j--) //创建最小堆

sift(table, j, n-1);

// System.out.println("最小堆？ "+isMinHeap(table));

for (int j=n-1; j0; j--) //每趟将最小值交换到后面，再调整成堆

{

int temp = table[0];

table[0] = table[j];

table[j] = temp;

sift(table, 0, j-1);

}

}

public static void mergeSort(int[] X) //归并排序

{

System.out.println("归并排序");

int n=1; //已排序的子序列长度，初值为1

int[] Y = new int[X.length]; //Y数组长度同X数组

do

{

mergepass(X, Y, n); //一趟归并，将X数组中各子序列归并到Y中

print(Y);

n*=2; //子序列长度加倍

if (nX.length)

{

mergepass(Y, X, n); //将Y数组中各子序列再归并到X中

print(X);

n*=2;

}

} while (nX.length);

}

private static void mergepass(int[] X, int[] Y, int n) //一趟归并

{

System.out.print("子序列长度n="+n+" ");

int i=0;

while (iX.length-2*n+1)

{

merge(X,Y,i,i+n,n);

i += 2*n;

}

if (i+nX.length)

merge(X,Y,i,i+n,n); //再一次归并

else

for (int j=i; jX.length; j++) //将X剩余元素复制到Y中

Y[j]=X[j];

}

private static void merge(int[] X, int[] Y, int m, int r, int n) //一次归并

{

int i=m, j=r, k=m;

while (ir jr+n jX.length) //将X中两个相邻子序列归并到Y中

if (X[i]X[j]) //较小值复制到Y中

Y[k++]=X[i++];

else

Y[k++]=X[j++];

while (ir) //将前一个子序列剩余元素复制到Y中

Y[k++]=X[i++];

while (jr+n jX.length) //将后一个子序列剩余元素复制到Y中

Y[k++]=X[j++];

}

public static void main(String[] args)

{

// int[] table = {52,26,97,19,66,8,49};//Array.random(9);{49,65,13,81,76,97,38,49};////{85,12,36,24,47,30,53,91,76};//;//{4,5,8,1,2,7,3,6};// {32,26,87,72,26,17};//

int[] table = {13,27,38,49,97,76,49,81}; //最小堆

System.out.print("关键字序列: ");

Array.print(table);

// Array.insertSort(table);

// Array.shellSort(table);

// Array.bubbleSort(table);

// Array.quickSort(table);

// Array.selectSort(table);

// Array.heapSort(table);

// Array.mergeSort(table);

System.out.println("最小堆序列? "+Array.isMinHeap(table));

}

//第9章习题

public static boolean isMinHeap(int[] table) //判断一个数据序列是否为最小堆

{

if (table==null)

return false;

int i = table.length/2 -1; //最深一棵子树的根结点

while (i=0)

{

int j=2*i+1; //左孩子

if (jtable.length)

if (table[i]table[j])

return false;

else

if (j+1table.length table[i]table[j+1]) //右孩子

return false;

i--;

}

return true;

}

}

/*

程序运行结果如下：

关键字序列: 32 26 87 72 26 17 8 40

直接插入排序

第1趟排序: 26 32 87 72 26 17 8 40

第2趟排序: 26 32 87 72 26 17 8 40

第3趟排序: 26 32 72 87 26 17 8 40

第4趟排序: 26 26 32 72 87 17 8 40 //排序算法稳定

第5趟排序: 17 26 26 32 72 87 8 40

第6趟排序: 8 17 26 26 32 72 87 40

第7趟排序: 8 17 26 26 32 40 72 87

关键字序列: 42 1 74 25 45 29 87 53

直接插入排序

第1趟排序: 1 42 74 25 45 29 87 53

第2趟排序: 1 42 74 25 45 29 87 53

第3趟排序: 1 25 42 74 45 29 87 53

第4趟排序: 1 25 42 45 74 29 87 53

第5趟排序: 1 25 29 42 45 74 87 53

第6趟排序: 1 25 29 42 45 74 87 53

第7趟排序: 1 25 29 42 45 53 74 87

关键字序列: 21 12 2 40 99 97 68 57

直接插入排序

第1趟排序: 12 21 2 40 99 97 68 57

第2趟排序: 2 12 21 40 99 97 68 57

第3趟排序: 2 12 21 40 99 97 68 57

第4趟排序: 2 12 21 40 99 97 68 57

第5趟排序: 2 12 21 40 97 99 68 57

第6趟排序: 2 12 21 40 68 97 99 57

第7趟排序: 2 12 21 40 57 68 97 99

关键字序列: 27 38 65 97 76 13 27 49 55 4

希尔排序

delta=5 13 27 49 55 4 27 38 65 97 76

delta=2 4 27 13 27 38 55 49 65 97 76

delta=1 4 13 27 27 38 49 55 65 76 97

关键字序列: 49 38 65 97 76 13 27 49 55 4 //严书

希尔排序

delta=5 13 27 49 55 4 49 38 65 97 76

delta=2 4 27 13 49 38 55 49 65 97 76 //与严书不同

delta=1 4 13 27 38 49 49 55 65 76 97

关键字序列: 65 34 25 87 12 38 56 46 14 77 92 23

希尔排序

delta=6 56 34 14 77 12 23 65 46 25 87 92 38

delta=3 56 12 14 65 34 23 77 46 25 87 92 38

delta=1 12 14 23 25 34 38 46 56 65 77 87 92

关键字序列: 84 12 43 62 86 7 90 91

希尔排序

delta=4 84 7 43 62 86 12 90 91

delta=2 43 7 84 12 86 62 90 91

delta=1 7 12 43 62 84 86 90 91

关键字序列: 32 26 87 72 26 17

冒泡排序

第1趟排序: 26 32 72 26 17 87

第2趟排序: 26 32 26 17 72 87

第3趟排序: 26 26 17 32 72 87

第4趟排序: 26 17 26 32 72 87

第5趟排序: 17 26 26 32 72 87

关键字序列: 1 2 3 4 5 6 7 8

冒泡排序

第1趟排序: 1 2 3 4 5 6 7 8

关键字序列: 1 3 2 4 5 8 6 7

冒泡排序

第1趟排序: 1 2 3 4 5 6 7 8

第2趟排序: 1 2 3 4 5 6 7 8

关键字序列: 4 5 8 1 2 7 3 6

冒泡排序

第1趟排序: 4 5 1 2 7 3 6 8

第2趟排序: 4 1 2 5 3 6 7 8

第3趟排序: 1 2 4 3 5 6 7 8

第4趟排序: 1 2 3 4 5 6 7 8

第5趟排序: 1 2 3 4 5 6 7 8

关键字序列: 38 26 97 19 66 1 5 49

0..7, vot=38 5 26 1 19 38 66 97 49

0..3, vot=5 1 5 26 19 38 66 97 49

2..3, vot=26 1 5 19 26 38 66 97 49

5..7, vot=66 1 5 19 26 38 49 66 97

关键字序列: 38 5 49 26 19 97 1 66

0..7, vot=38 1 5 19 26 38 97 49 66

0..3, vot=1 1 5 19 26 38 97 49 66

1..3, vot=5 1 5 19 26 38 97 49 66

2..3, vot=19 1 5 19 26 38 97 49 66

5..7, vot=97 1 5 19 26 38 66 49 97

5..6, vot=66 1 5 19 26 38 49 66 97

关键字序列: 49 38 65 97 76 13 27 49

0..7, vot=49 49 38 27 13 49 76 97 65

0..3, vot=49 13 38 27 49 49 76 97 65

0..2, vot=13 13 38 27 49 49 76 97 65

1..2, vot=38 13 27 38 49 49 76 97 65

5..7, vot=76 13 27 38 49 49 65 76 97

关键字序列: 27 38 65 97 76 13 27 49 55 4

low=0 high=9 vot=27 4 27 13 27 76 97 65 49 55 38

low=0 high=2 vot=4 4 27 13 27 76 97 65 49 55 38

low=1 high=2 vot=27 4 13 27 27 76 97 65 49 55 38

low=4 high=9 vot=76 4 13 27 27 38 55 65 49 76 97

low=4 high=7 vot=38 4 13 27 27 38 55 65 49 76 97

low=5 high=7 vot=55 4 13 27 27 38 49 55 65 76 97

关键字序列: 38 26 97 19 66 1 5 49

直接选择排序

第0趟排序: 1 26 97 19 66 38 5 49

第1趟排序: 1 5 97 19 66 38 26 49

第2趟排序: 1 5 19 97 66 38 26 49

第3趟排序: 1 5 19 26 66 38 97 49

第4趟排序: 1 5 19 26 38 66 97 49

第5趟排序: 1 5 19 26 38 49 97 66

第6趟排序: 1 5 19 26 38 49 66 97

最小堆

关键字序列: 81 49 76 27 97 38 49 13 65

sift 3..8 81 49 76 13 97 38 49 27 65

sift 2..8 81 49 38 13 97 76 49 27 65

sift 1..8 81 13 38 27 97 76 49 49 65

sift 0..8 13 27 38 49 97 76 49 81 65

13 27 38 49 97 76 49 81 65

sift 0..7 27 49 38 65 97 76 49 81 13

sift 0..6 38 49 49 65 97 76 81 27 13

sift 0..5 49 65 49 81 97 76 38 27 13

sift 0..4 49 65 76 81 97 49 38 27 13

sift 0..3 65 81 76 97 49 49 38 27 13

sift 0..2 76 81 97 65 49 49 38 27 13

sift 0..1 81 97 76 65 49 49 38 27 13

sift 0..0 97 81 76 65 49 49 38 27 13

最大堆

关键字序列: 49 65 13 81 76 27 97 38 49

sift 3..8 49 65 13 81 76 27 97 38 49

sift 2..8 49 65 97 81 76 27 13 38 49

sift 1..8 49 81 97 65 76 27 13 38 49

sift 0..8 97 81 49 65 76 27 13 38 49

97 81 49 65 76 27 13 38 49

sift 0..7 81 76 49 65 49 27 13 38 97

sift 0..6 76 65 49 38 49 27 13 81 97

sift 0..5 65 49 49 38 13 27 76 81 97

sift 0..4 49 38 49 27 13 65 76 81 97

sift 0..3 49 38 13 27 49 65 76 81 97

sift 0..2 38 27 13 49 49 65 76 81 97

sift 0..1 27 13 38 49 49 65 76 81 97

sift 0..0 13 27 38 49 49 65 76 81 97

关键字序列: 52 26 97 19 66 8 49

归并排序

子序列长度n=1 26 52 19 97 8 66 49

子序列长度n=2 19 26 52 97 8 49 66

子序列长度n=4 8 19 26 49 52 66 97

关键字序列: 13 27 38 49 97 76 49 81 65

最小堆序列? true

*/

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

求使用java实现的快排算法

① 代码：

public class quicksortdemo {

private int array[];

private int length;

public void sort(int[] inputArr) {

if (inputArr == null || inputArr.length == 0) {

return;

}

this.array = inputArr;

length = inputArr.length;

quickSort(0, length - 1);

}

private void quickSort(int lowerIndex, int higherIndex) {

int i = lowerIndex;

int j = higherIndex;

// calculate pivot number

int pivot = array[lowerIndex+(higherIndex-lowerIndex)/2];

// Divide into two arrays

while (i = j) {

while (array[i]  pivot) {

i++;

}

while (array[j]  pivot) {

j--;

}

if (i = j) {

swap(i, j);                

i++;

j--;

}

}

// call quickSort() method recursively

if (lowerIndex  j)

quickSort(lowerIndex, j);

if (i  higherIndex)

quickSort(i, higherIndex);

}

private void swap(int i, int j) {

int temp = array[i];

array[i] = array[j];

array[j] = temp;

}

public static void main(String a[]){

quicksortdemo sorter = new quicksortdemo();

int[] input = {24,2,45,20,56,75,2,56,99,53,12};

sorter.sort(input);

for(int i:input){

System.out.print(i);

System.out.print(" ");

}

}

}

② 运行：

c:\java quicksortdemo

2 2 12 20 24 45 53 56 56 75 99

请问一下java快速排序源代码

快速排序：

package org.rut.util.algorithm.support;

import org.rut.util.algorithm.SortUtil;

/**

* @author treeroot

* @since 2006-2-2

* @version 1.0

*/

public class QuickSort implements SortUtil.Sort{

/* (non-Javadoc)

* @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])

*/

public void sort(int[] data) {

quickSort(data,0,data.length-1);

}

private void quickSort(int[] data,int i,int j){

int pivotIndex=(i+j)/2;

//swap

SortUtil.swap(data,pivotIndex,j);

int k=partition(data,i-1,j,data[j]);

SortUtil.swap(data,k,j);

if((k-i)1) quickSort(data,i,k-1);

if((j-k)1) quickSort(data,k+1,j);

}

/**

* @param data

* @param i

* @param j

* @return

*/

private int partition(int[] data, int l, int r,int pivot) {

do{

while(data[++l]pivot);

while((r!=0)data[--r]pivot);

SortUtil.swap(data,l,r);

}

while(lr);

SortUtil.swap(data,l,r);

return l;

}

}

改进后的快速排序：

package org.rut.util.algorithm.support;

import org.rut.util.algorithm.SortUtil;

/**

* @author treeroot

* @since 2006-2-2

* @version 1.0

*/

public class ImprovedQuickSort implements SortUtil.Sort {

private static int MAX_STACK_SIZE=4096;

private static int THRESHOLD=10;

/* (non-Javadoc)

* @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])

*/

public void sort(int[] data) {

int[] stack=new int[MAX_STACK_SIZE];

int top=-1;

int pivot;

int pivotIndex,l,r;

stack[++top]=0;

stack[++top]=data.length-1;

while(top0){

int j=stack[top--];

int i=stack[top--];

pivotIndex=(i+j)/2;

pivot=data[pivotIndex];

SortUtil.swap(data,pivotIndex,j);

//partition

l=i-1;

r=j;

do{

while(data[++l]pivot);

while((r!=0)(data[--r]pivot));

SortUtil.swap(data,l,r);

}

while(lr);

SortUtil.swap(data,l,r);

SortUtil.swap(data,l,j);

if((l-i)THRESHOLD){

stack[++top]=i;

stack[++top]=l-1;

}

if((j-l)THRESHOLD){

stack[++top]=l+1;

stack[++top]=j;

}

}

//new InsertSort().sort(data);

insertSort(data);

}

/**

* @param data

*/

private void insertSort(int[] data) {

int temp;

for(int i=1;idata.length;i++){

for(int j=i;(j0)(data[j]data[j-1]);j--){

SortUtil.swap(data,j,j-1);

}

}

}

}