- package com.xzf.test.quicksort;
- /**
- * 快速排序
- * @author xzf
- *
- */
- public class QuickSort {
- private int k = 100;
- /**
- * 确定划分元位置,对数组原址重排
- * @param A 初始数组
- * @param p
- * @param r
- * @return 划分元位置
- */
- public int partition(int A[] , int p , int r)
- {
- int x = A[r];
- int i = p - 1;
- int tmp = 0;
- for(int j = p ; j < r ; j++)
- {
- if(A[j] <= x)
- {
- i ++;
- tmp = A[i];
- A[i] = A[j];
- A[j] = tmp;
- }
- }
- tmp = A[i+1];
- A[i+1] = A[r];
- A[r] = tmp;
- return i+1;
- }
- /**
- * 随机化版本数组划分
- * @param A
- * @param p
- * @param r
- * @return
- */
- public int randomizedPartition(int A[] , int p , int r)
- {
- int i = (int)Math.random() * (r - p + 1) + p;
- int tmp = A[i];
- A[i] = A[r];
- A[r] = tmp;
- return partition(A, p, r);
- }
- /**
- * 普通快速排序
- * @param A 初始数组
- * @param p
- * @param r
- */
- public 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);
- }
- }
- /**
- * 带插入排序的快速排序
- * @param A 初始数组
- * @param p
- * @param r
- */
- public void quickSortWithInsertion(int A[] , int p , int r)
- {
- if(r-p > k)
- {
- int q = partition(A, p, r);
- System.out.println(q);
- quickSortWithInsertion(A, p, q-1);
- quickSortWithInsertion(A, q+1, r);
- }
- }
- /**
- * 随机化版本快速排序
- * @param A
- * @param p
- * @param r
- */
- public void randomizedQuickSort(int A[] , int p , int r)
- {
- if(p < r)
- {
- int q = randomizedPartition(A, p, r);
- randomizedQuickSort(A, p, q-1);
- randomizedQuickSort(A, q+1, r);
- }
- }
- /**
- * 插入排序
- * @param A
- * @param p
- * @param r
- */
- public void InsertSort(int[] A, int p, int r)
- {
- int i, j;
- for(i = p + 1; i <= r; i++)
- {
- int temp = A[i];
- j = i;
- while(j >= p+1 && A[j-1] > temp)
- {
- A[j] = A[j-1];
- j--;
- }
- A[j] = temp;
- }
- }
- /**
- * 打印结果
- * @param A
- * @return
- */
- public String printResult(int A[])
- {
- String result = "";
- for(int i = 0; i < A.length; i++)
- {
- result += A[i] + ",";
- }
- System.out.println("In print:" + result);
- return result.replace(',', ' ');
- }
- /**
- * @param args
- */
- public static void main(String[] args) {
- //数组大小
- /*int size = 1000;
- System.out.println("程序运行结果(循环10次求平均运行时间)。单位:ms");
- System.out.print("数据大小\\t\\t普通版本\\t\\t随机化版本\\t带插入排序版本\\n");
- System.out.println("-----------------------------------------------------------");
- QuickSort quickSort = new QuickSort();
- for(int p=0; p<3; p++)
- {
- //改变数组大小
- size = size * 10;
- //原始数组
- int[] A = new int[size];
- //辅助数组
- int[] tempA = new int[size];
- //生成初始数据
- for(int i = 0; i < A.length; i++)
- {
- //随机生成数据
- A[i] = (int)(Math.random()*1000);
- //数据有序生成
- //A[i] = i % 5000;
- }
- //quickSort.printResult(A);
- long runTime1[] = new long[10];
- long runTime2[] = new long[10];
- long runTime3[] = new long[10];
- //循环操作,求取平均运行时间
- for(int m=0; m<runTime1.length; m++)
- {
- //恢复初始数据
- for(int i = 0; i < A.length; i++)
- {
- tempA[i] = A[i];
- }
- //普通版本快速排序
- long startTime1=System.currentTimeMillis(); //获取开始时间
- quickSort.quickSort(tempA, 0, tempA.length - 1);
- long endTime1=System.currentTimeMillis(); //获取结束时间
- //quickSort.printResult(tempA);
- runTime1[m] = endTime1-startTime1;
- //恢复初始数据
- for(int i = 0; i < A.length; i++)
- {
- tempA[i] = A[i];
- }
- //随机化版本快速排序
- long startTime2=System.currentTimeMillis();
- quickSort.randomizedQuickSort(tempA, 0, tempA.length - 1);
- long endTime2=System.currentTimeMillis();
- //quickSort.printResult(tempA);
- runTime2[m] = endTime2-startTime2;
- //恢复初始数据
- for(int i = 0; i < A.length; i++)
- {
- tempA[i] = A[i];
- }
- //带k值的普通版本快速排序
- long startTime3=System.currentTimeMillis();
- quickSort.quickSortWithInsertion(tempA, 0, tempA.length - 1);
- quickSort.InsertSort(tempA, 0, tempA.length - 1);
- long endTime3=System.currentTimeMillis();
- //quickSort.printResult(tempA);
- runTime3[m] = endTime3-startTime3;
- }
- //求平均运行时间
- double aveRunTime1 = 0;
- double aveRunTime2 = 0;
- double aveRunTime3 = 0;
- for(int m=0; m<runTime1.length; m++)
- {
- aveRunTime1 += runTime1[m];
- aveRunTime2 += runTime2[m];
- aveRunTime3 += runTime3[m];
- }
- aveRunTime1 = aveRunTime1 / runTime1.length;
- aveRunTime2 = aveRunTime2 / runTime2.length;
- aveRunTime3 = aveRunTime3 / runTime3.length;
- //打印运行时间
- System.out.print(size + "\\t\\t" + aveRunTime1 +"\\t\\t" + aveRunTime2 + "\\t\\t" + aveRunTime3 + "\\n");
- }*/
- //测试K值大小对带插入排序版本的结果影响
- QuickSort quickSort = new QuickSort();
- int size = 10000; //数组大小
- int key[] = new int[]{5,7,9,11,12,13,14,15,16,17,18,19,20,21,22,
- 23,24,25,28,30,33,35,50,80,95,100,150,200};
- //原始数组
- int[] A = new int[size];
- //辅助数组
- int[] tempA = new int[size];
- //生成初始数据
- for(int i = 0; i < A.length; i++)
- {
- //随机生成数据
- A[i] = (int)(Math.random()*1000000);
- //数据有序生成
- //A[i] = i % 5000;
- }
- System.out.println("测试K值大小对带插入排序版本的结果影响。数组大小为1000000。");
- for(int m=0; m<key.length; m++)
- {
- //对K赋值
- quickSort.k = key[m];
- //恢复初始数据
- for(int i = 0; i < A.length; i++)
- {
- tempA[i] = A[i];
- }
- long startTime3=System.currentTimeMillis();
- quickSort.quickSortWithInsertion(tempA, 0, tempA.length - 1);
- quickSort.InsertSort(tempA, 0, tempA.length - 1);
- long endTime3=System.currentTimeMillis();
- System.out.println(quickSort.k + "\\t\\t" + (endTime3-startTime3));
- }
- }
- }
- //该片段来自于http://www.codesnippet.cn/detail/2212201411383.html
来源: http://www.codesnippet.cn/detail/2212201411383.html