public class quickSort {
创新互联公司主要从事成都网站建设、网站建设、网页设计、企业做网站、公司建网站等业务。立足成都服务钦北,十余年网站建设经验,价格优惠、服务专业,欢迎来电咨询建站服务:13518219792
public quickSort() {
}
public void printA(int[] a) {
for (int i = 0; i a.length; i++) {
System.out.print(a[i] + " ");
}
System.out.println();
}
public void chooseSort(int[] a, int left, int right) {
int smallest;
int flagIndex = 0;
int forSwap;
boolean flag;
for (int i = left; i right; i++) {
smallest = a[i];
// System.out.println("first" + smallest);
flagIndex = i;
flag = false;
for (int j = i + 1; j = right; j++) {
if (a[j] smallest) {
smallest = a[j];
flagIndex = j;
flag = true;
// System.out.println(smallest + " " + flagIndex);
}
}
if(flag){
forSwap = a[i];
a[i] = smallest;
a[flagIndex] = forSwap;
// System.out.println(smallest);
// printA(a);
// printA(a);
}
}
}
public void quickSort(int[] a, int left, int right) {
int index;
// printA(a);
if (left right right - left 10) { //可以优化如果数组元素小于10就用选择排序
index = partition(a, left, right);
quickSort(a, left, index - 1);
quickSort(a, index + 1, right);
} else {
chooseSort(a, left, right);
}
}
public int partition(int[] a, int left, int right) {
int result = getMiddle(a[left], a[right], a[(int) ((left + right) / 2)]);
int flagIndex;
if (result == 1) {
flagIndex = left;
} else if (result == 2) {
flagIndex = right;
} else {
flagIndex = (int) ((left + right) / 2);
}
int lowIndex, highIndex;
lowIndex = left - 1;
highIndex = right + 1;
int compareValue = a[flagIndex];
int k = a[left];
a[left] = compareValue;
a[flagIndex] = k;
// System.out.println(compareValue);
while (lowIndex + 1 != highIndex) {
if (a[lowIndex + 1] = compareValue) {
lowIndex++;
} else if (a[highIndex - 1] = compareValue) {
highIndex--;
} else {
k = a[lowIndex + 1];
a[++lowIndex] = a[highIndex - 1];
a[--highIndex] = k;
}
}
// printA(a);
a[left] = a[lowIndex];
a[lowIndex] = compareValue;
return lowIndex;
}
public int getMiddle(int a, int b, int c) {
if (a = b) {
if (b = c) {
return 2;
} else {
if (a = c) {
return 3;
} else {
return 1;
}
}
} else {
if (c = b) {
return 2;
} else {
if (a = c) {
return 1;
} else {
return 3;
}
}
}
// return 0;
}
}
java编程实现随机数组的快速排序步骤如下：
1、打开Eclipse，新建一个Java工程，在此工程里新建一个Java类；
2、在新建的类中声明一个产生随机数的Random变量，再声明一个10个长度的int型数组；
3、将产生的随机数逐个放入到数组中；
4、利用排序算法对随机数组进行排序。
具体代码如下：
import java.util.Random;
public class Demo {
public static void main(String[] args) {
int count = 0;
Random random = new Random();
int a[] = new int[10];
while(count 10){
a[count] = random.nextInt(1000);//产生0-999的随机数
count++;
}
for (int i = 0; i a.length - 1; i++) {
int min = i;
for (int j = i + 1; j a.length; j++) {
if (a[j] a[min]) {
min = j;
}
}
if (min != i) {
int b = a[min];
a[min] = a[i];
a[i] = b;
}
}
for (int c = 0; c a.length; c++) {
System.out.print(a[c] + " ");
}
}
}
快速排序：
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);
}
}
}
}
本人特地给你编的代码
亲测
public class QuickSort {
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){
// swap(a[j-1],a[i-1]);
i++;
temp=a[j-1];
a[j-1]=a[i-1];
a[i-1]=temp;
}
}
//swap(a[r-1,a[i+1-1]);
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(pr){
int q=Partition(a,p,r);
QuickSort(a,p,q-1);
QuickSort(a,q+1,r);
}
}
public static void main(String[] stra){
int a[]={23,53,77,36,84,76,93,13,45,23};
QuickSort(a,1,10);
for (int i=1;i=10;i++)
System.out.println(a[i-1]);
}
}
一趟快速怕序的具体做法是：附设两个指针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;
}
}
/**
* 快速排序
*/
private static void quickSort ( int[] array, int start, int end )
{
if (start end)
{
int key = array;
int i = start;
for ( int j = start + 1; j end + 1; j++ )
{
if (key array[j])
{
int temp = array[j];
array[j] = array[i + 1];
array[i + 1] = temp;
i++;
}
}
array = array[i];
array[i] = key;
quickSort (array, start, i - 1);
quickSort (array, i + 1, end);
}
}
int[] array = new int[] { 11, 213, 134, 65, 77, 78, 23, 43 };
quickSort (array, 0, array.length - 1);
System.out.println (Arrays.toString (array));
