Question

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

Answer 1

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();
}
}

Answer 2

//快速排序（交换排序），不稳定，时间复杂度nlog2n，空间复杂度log2n
class QuickSort{

public static void quickSort(int[] array,int low,int high){
if(low>=high){ //递归出口
return;
}
int index=array[low]; //设置key进行划分
int i=low;
int j=high;
while(i<j){
while(i<j && index<array[j]){ //判断右边元素
j--;
}
array[i]=array[j];
while(i<j && index>array[i]){ //判断左边元素
i++;
}
array[j]=array[i];
}
array[i]=index;
quickSort(array, low, i-1); //进行递归
quickSort(array, i+1, high);
}

}

Answer 3

public void quickSort(int left,int right,int a[])
{
int l=left;
int r=right;
int pivot=a[(l+r)/2];//转轴数
int temp=0;
while(l<r)
{
while(a[l]<pivot)l++;
while(a[r]>pivot)r--;

if(l>=r)break;

temp=a[l];
a[l]=a[r];
a[r]=temp;

if(a[l]==pivot)r--;
if(a[r]==pivot)l++;
}
if(l==r)
{
l++;
r--;
}
if(left<r)quickSort(left,r,a);
if(right>l)quickSort(l,right,a);
}

Answer 4

java希尔排序：
public class shellsort{
int [] a={15,24,25,68,12,10,45,18,27}
iint temp;
for(int k=a.length/2; k>0; k/=2)
{
for(int j=i; j>=k; j-=k)
{
if(a[j-k]<a[j])
{
temp=a[i];
a[j-k]=a[j];
a[j]=temp;
}
}
}
for(int i=0;i<a.length;i++)
{
System.out.println(a[i]+" ")
}
}

Answer 5

一般都是 二分法 和冒泡