正文
java快速排序最优代码 java中快速排序算法
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
java排序，效率高的是哪种排序方法
和所有其他语言是一样的。应该还是快速排序效率最高。
public static void bubbleSort(int a[]) {
int len = a.length;
for (int i = 0; i len - 1; i++) {
for (int j = 0; j len - 1 - i; j++) {
if (a[j] a[j + 1]) {
int temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
}
}
}
}
public static void selectSort(int a[]) {
int temp = 0;
int len = a.length;
for (int i = 0; i len - 1; i++) {
int min = a[i];
int index = i;
for (int j = i + 1; j len; j++) {
if (min a[j]) {
min = a[j];
index = j;
}
}
temp = a[i];
a[i] = a[index];
a[index] = temp;
}
}
public static void insertSort(int a[]) {
int len = a.length;
for (int i = 1; i len; i++) {
int temp = a[i];// 待插入的值
int index = i;// 待插入的位置
while (index 0 a[index - 1] temp) {
a[index] = a[index - 1];// 待插入的位置重新赋更大的值
index--;// 位置往前移
}
a[index] = temp;
}
}
public static int partition(int a[], int low, int height) {
int key = a[low];
while (low height) {
while (low height a[height] = key)
height--;
a[low] = a[height];
while (low height a[low] = key)
low++;
a[height] = a[low];
}
a[low] = key;
return low;
}
public static void quickSort(int a[], int low, int height) {
if (low height) {
int result = partition(a, low, height);
quickSort(a, low, result - 1);
quickSort(a, result + 1, height);
}
}
测试结果
------------------------------------------
测试数据10000
冒泡排序：120ms
选择排序：32ms
插入排序：20ms
快速排序：7ms
------------------------------------------
测试数据100000
冒泡排序：13098ms
选择排序：2334ms
插入排序：1264ms
快速排序：23ms
效率差距很大啊！！！！
相关问答
Q1: Java 快速排序法的实例!
package quickSort;
import java.util.Arrays;
/**
*
*
* 快速排序的思想：分区法+挖坑填数法。
* 1、先从数列中取出一个数作为枢纽关键字，一般用第一个元素
* 2、分区过程，将比这个枢纽关键字大的数全放在它的右边，把小于或者等于的数全放在它左边
* 3、再对左右分区进行第二步的操作，也就是递归。知道各个区间只有一个数为止
*
* 快速排序是冒泡排序的一种改进，有很多快速排序的方法还是用每次在比较后都用冒泡排序
* 的方式交换，但是这样的效率要比只用一个枢纽关键字来控制交换的效率要大，所以下面是一种改进
*/
public class QuickSort {
public static void main(String args[])
{
int array[]={49,38,65,97,76,13,27,49};
System.out.println(Arrays.toString(array));
quickSort(array,0,array.length-1);
System.out.println(Arrays.toString(array));
}
/**
* 分区方法：负责每次递归执行未分区的数据，也就是每次分区后枢纽关键字左右两边的元素
* @param arr 要排序的数组
* @param low 数组中小的索引，用于向后扫描
* @param high 数组中大的索引，用于向前扫描
*/
public static void quickSort(int arr[],int low,int high)
{
if(lowhigh)
{
int mid = partition(arr,low,high);
//对枢纽关键字左边的分区进行分区
quickSort(arr,low,mid-1);
//对枢纽关键字右边的分区进行分区
quickSort(arr,mid+1,high);
}
}
/**
* 挖坑填数，即具体实现分区的方法，每次的结果是将数组分为比枢纽关键字小的在左边，
* 比枢纽关键字大的在右边
* @param array 要排序的数组
* @param low
* @param high
* @return 执行完分区后low的坐标值，用于下次递归的时候分区用
*/
public static int partition(int array[],int low,int high)
{
//将数组中第一个元素作为枢纽关键字，这个关键字将在本次分区过程中不变
int pivotKey = array[low];
int i=low,j=high;
if(lowhigh)
{
while(ij)
{
//从后向前扫描，如果array[j]=pivotKey，则下表j向前移动
while(ijarray[j]=pivotKey)
{
j--;
}
//array[j]pivotKey，则将array[j]挖出来填入array[i]，即刚才被pivotKey挖走的地方
if(ij)
{
array[i]=array[j];
i++;
}
//如果array[i]=pivotKey，则下表i向后移动
while(ijarray[i]=pivotKey)
{
i++;
}
//arry[i]pivotKey，将array[i]挖出来填入刚才被挖的array[j]
if(ij)
{
array[j]=array[i];
j--;
}
}
//如果到最后i=j的时候，也就是扫描完整个数组，则将枢纽关键字填入剩下的那个被挖的坑array[i]
array[i]=pivotKey;
}
//打印每次分区后的结果
System.out.println(Arrays.toString(array));
//将这个分区结束时的坐标i返回，用于下次执行时当做前分区的尾坐标，当做后分区的头坐标
return i;
}
}
Q2: 排序都有哪几种方法？用JAVA实现一个快速排序。
排序java快速排序最优代码的方法有java快速排序最优代码：插入排序（直接插入排序、希尔排序）java快速排序最优代码，交换排序（冒泡排序、快速排序）java快速排序最优代码，选择排序（直接选择排序、堆排序），归并排序，分配排序（箱排序、基数排序）
快速排序java快速排序最优代码的伪代码。
/ /使用快速排序方法对a[ 0 :n- 1 ]排序
从a[ 0 :n- 1 ]中选择一个元素作为m i d d l e，该元素为支点
把余下的元素分割为两段left 和r i g h t，使得l e f t中的元素都小于等于支点，而right 中的元素都大于等于支点
递归地使用快速排序方法对left 进行排序
递归地使用快速排序方法对right 进行排序
所得结果为l e f t + m i d d l e + r i g h t
Q3: java快速排序代码中SwapReferences（）方法是什么？代码怎么写？
/**
* 快速排序
*/
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));
Q4: 如何用java实现快速排序，简答讲解下原理
快速排序思想：
通过对数据元素集合Rn 进行一趟排序划分出独立的两个部分。其中一个部分的关键字比另一部分的关键字小。然后再分别对两个部分的关键字进行一趟排序，直到独立的元素只有一个，此时整个元素集合有序。
快速排序的过程，对一个元素集合R[ low ... high ] ,首先取一个数（一般是R[low] ）做参照 ， 以R[low]为基准重新排列所有的元素。
所有比R[low]小的放前面，所有比R[low] 大的放后面，然后以R[low]为分界，对R[low ... high] 划分为两个子集和，再做划分。直到low = high 。
比如：对R={37, 40, 38, 42, 461, 5, 7, 9, 12}进行一趟快速排序的过程如下(注:下面描述的内容中元素下表从 0 开始)：
开始选取基准 base = 37，初始位置下表 low = 0 ， high = 8 ， 从high=8，开始如果R[8] base , 将high位置中的内容写入到R[low]中, 将high位置空出来, low = low +1 ;
从low开始探测，由于low=1 ， R[low] base ,所以将R[low]写入到R[high] , high = high -1 ;
检测到low high ,所以第一趟快速排序仍需继续:
此时low=1，high=7，因为 R[high] base ,所以将 R[high] 写入到到R[low]中,low = low + 1;
从low开始探测,low = 2 , R[low] base ,所以讲R[low]写入到R[high]，high=high-1;
继续检测到 low 小于high
此时low=2，high=6，同理R[high] base ,将R[high] 写入到R[low]中，low=low+1;
从low继续探测,low = 3 , high=6 , R[low] base , 将R[low]写入到R[high]中，high = high-1;
继续探测到low小于high
此时low=3，high=5，同理R[high] base,将R[high]写入到R[low]中，low = low +1；
从low继续探测，low = 4，high=5，由于R[low] base , 将R[low]写入到R[high]中，high = high -1 ;
此时探测到low == high == 4 ；该位置即是base所在的位置，将base写入到该位置中.
然后再对子序列Rs1 = {12,9,7,5} 和 Rs2={461,42,38,40}做一趟快速排序，直到Rsi中只有一个元素，或没有元素。
快速排序的Java实现：
private static boolean isEmpty(int[] n) {
return n == null || n.length == 0;
}
// ///////////////////////////////////////////////////
/**
* 快速排序算法思想——挖坑填数方法：
*
* @param n 待排序的数组
*/
public static void quickSort(int[] n) {
if (isEmpty(n))
return;
quickSort(n, 0, n.length - 1);
}
public static void quickSort(int[] n, int l, int h) {
if (isEmpty(n))
return;
if (l h) {
int pivot = partion(n, l, h);
quickSort(n, l, pivot - 1);
quickSort(n, pivot + 1, h);
}
}
private static int partion(int[] n, int start, int end) {
int tmp = n;
while (start end) {
while (n
java快速排序最优代码的介绍就聊到这里吧，感谢你花时间阅读本站内容，更多关于java中快速排序算法、java快速排序最优代码的信息别忘了在本站进行查找喔。
= tmp start end)end--;
if (start end) {
n[start++] = n
java快速排序最优代码的介绍就聊到这里吧，感谢你花时间阅读本站内容，更多关于java中快速排序算法、java快速排序最优代码的信息别忘了在本站进行查找喔。
;}
while (n tmp start end)
start++;
if (start end) {
n[end--] = n;
}
}
n = tmp;
return start;
}
在代码中有这样一个函数：
public static void quickSortSwap(int[] n, int l, int h)
该函数可以实现，元素集合中特定的 l 到 h 位置间的数据元素进行排序。
java快速排序最优代码的介绍就聊到这里吧，感谢你花时间阅读本站内容，更多关于java中快速排序算法、java快速排序最优代码的信息别忘了在本站进行查找喔。
