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

发布网友 发布时间：2022-04-23 12:40

我来回答

共5个回答

热心网友 时间：2022-06-13 03:40

快速排序：

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(l<r);
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(top>0){
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(l<r);
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;i<data.length;i++){
for(int j=i;(j>0)&&(data[j]<data[j-1]);j--){
SortUtil.swap(data,j,j-1);
}
}
}

}

热心网友 时间：2022-06-13 04:58

C语言的可以吗？JAVA不太懂，不过算法是差不多的！主要函数实现：

void QuickSort(SeqList R，int low，int high)
{ //对R[low..high]快速排序
int pivotpos； //划分后的基准记录的位置
if(low<high){//仅当区间长度大于1时才须排序
pivotpos=Partition(R，low，high)； //对R[low..high]做划分
QuickSort(R，low，pivotpos-1)； //对左区间递归排序
QuickSort(R，pivotpos+1，high)； //对右区间递归排序
}
} //QuickSort

热心网友 时间：2022-06-13 06:33

String[] arr = {"c","a","b"};
java.util.Arrays.sort(arr);//排序(支持String)
System.out.println(java.util.Arrays.toString(arr)); //输出排序

热心网友 时间：2022-06-13 08:24

是字母还是数字？？
package com.icescut.classic.algorithm;
public class BubbleSort {
public static void main(String[] args) {
int[] array = {10,-3,5,34,-34,5,0,9}; //test data
sort(array);
for(int el : array) {
System.out.print(el + " ");
}
}
static void sort(int[] array) {
int length = array.length;
int temp;
boolean isSort;
for(int i = 1; i < length; i++) {
isSort = false;
for(int j = 0; j < length - i; j++) {
if(array[j] > array[j+1]) {
//交换
temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
isSort = true;
}
}
if(!isSort) break; //如果没有发生交换，则退出循环
}
}
}