快速排序java,如何用java实现快速排序，简答讲解下原理

快速排序java,如何用java实现快速排序，简答讲解下原理详细介绍

本文目录一览： java快速排序简单代码

.example-btn{color:#fff;background-color:#5cb85c;border-color:#4cae4c}.example-btn:hover{color:#fff;background-color:#47a447;border-color:#398439}.example-btn:active{background-image:none}div.example{width:98%;color:#000;background-color:#f6f4f0;background-color:#d0e69c;background-color:#dcecb5;background-color:#e5eecc;margin:0 0 5px 0;padding:5px;border:1px solid #d4d4d4;background-image:-webkit-linear-gradient(#fff,#e5eecc 100px);background-image:linear-gradient(#fff,#e5eecc 100px)}div.example_code{line-height:1.4em;width:98%;background-color:#fff;padding:5px;border:1px solid #d4d4d4;font-size:110%;font-family:Menlo,Monaco,Consolas,"Andale Mono","lucida console","Courier New",monospace;word-break:break-all;word-wrap:break-word}div.example_result{background-color:#fff;padding:4px;border:1px solid #d4d4d4;width:98%}div.code{width:98%;border:1px solid #d4d4d4;background-color:#f6f4f0;color:#444;padding:5px;margin:0}div.code div{font-size:110%}div.code div,div.code p,div.example_code p{font-family:"courier new"}pre{margin:15px auto;font:12px/20px Menlo,Monaco,Consolas,"Andale Mono","lucida console","Courier New",monospace;white-space:pre-wrap;word-break:break-all;word-wrap:break-word;border:1px solid #ddd;border-left-width:4px;padding:10px 15px} 排序算法是《数据结构与算法》中最基本的算法之一。排序算法可以分为内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。以下是快速排序算法：
快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序 n 个项目要 Ο(nlogn) 次比较。在最坏状况下则需要 Ο(n2) 次比较，但这种状况并不常见。事实上，快速排序通常明显比其他 Ο(nlogn) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。
快速排序使用分治法（Divide and conquer）策略来把一个串行（list）分为两个子串行（sub-lists）。
快速排序又是一种分而治之思想在排序算法上的典型应用。本质上来看，快速排序应该算是在冒泡排序基础上的递归分治法。
快速排序的名字起的是简单粗暴，因为一听到这个名字你就知道它存在的意义，就是快，而且效率高！它是处理大数据最快的排序算法之一了。虽然 Worst Case 的时间复杂度达到了 O(n?)，但是人家就是优秀，在大多数情况下都比平均时间复杂度为 O(n logn) 的排序算法表现要更好，可是这是为什么呢，我也不知道。好在我的强迫症又犯了，查了 N 多资料终于在《算法艺术与信息学竞赛》上找到了满意的答案：

快速排序的最坏运行情况是 O(n?)，比如说顺序数列的快排。但它的平摊期望时间是 O(nlogn)，且 O(nlogn) 记号中隐含的常数因子很小，比复杂度稳定等于 O(nlogn) 的归并排序要小很多。所以，对绝大多数顺序性较弱的随机数列而言，快速排序总是优于归并排序。
1. 算法步骤
从数列中挑出一个元素，称为 "基准"（pivot）;

重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；

递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；
2. 动图演示
代码实现 JavaScript 实例 function quickSort ( arr , left , right ) {
? ? var len = arr. length ,
? ? ? ? partitionIndex ,
? ? ? ? left = typeof left != 'number' ? 0 : left ,
? ? ? ? right = typeof right != 'number' ? len - 1 : right ;

? ? if ( left

java中排序方法有哪些

1、直接插入排序：最基本的插入排序，将第i个插入到前i-1个中的适当位置。
2、折半插入排序：因为是已经确定了前部分是有序序列，所以在查找插入位置的时候可以用折半查找的方法进行查找，提高效率。
3、
希尔排序：
又称缩小增量排序法。把待排序序列分成若干较小的子序列，然后逐个使用直接插入排序法排序，最后再对一个较为有序的序列进行一次排序，主要是为了减少移动的次数，提高效率。原理应该就是从无序到渐渐有序，要比直接从无序到有序移动的次数会少一些。
4、
冒泡排序：反复扫描待排序序列，在扫描的过程中顺次比较相邻的两个元素的大小，若逆序就交换位置。第一趟，从第一个数据开始，比较相邻的两个数据，（以升序为例）如果大就交换，得到一个最大数据在末尾；然后进行第二趟，只扫描前n-1个元素，得到次大的放在倒数第二位。以此类推，最后得到升序序列。如果在扫描过程中，发现没有交换，说明已经排好序列，直接终止扫描。所以最多进行n-1趟扫描。
5、快速排序：
思想：冒泡排序一次只能消除一个逆序，为了能一次消除多个逆序，采用快速排序。以一个关键字为轴，从左从右依次与其进行对比，然后交换，第一趟结束后，可以把序列分为两个子序列，然后再分段进行快速排序，达到高效。
此外还有选择、归并、分配排序等等及它们的子类排序
具体要看你是做什么样的排序，如果是集合排序，比如list的排序，可以使用楼上说的collections类的里静态方法，如果你要对数组进行排序，可以自己写排序算法，也可以直接使用java提供的arrays.sort方法，但要注意，如果数组里的元素都是对象，那么要求这些对象都要实现了comparable接口，包括list也是。

java 编写一个程序,输入3个整数,然后程序将对这三个整数按照从大到小进行排列

可以实现比较器Comparator来定制排序方案，同时使用Colletions.sort的方式进行排序，代码如下：
public void sortDesc(List

s){Collections.sort(s, new Comparator

() {public int compare(Long o1, Long o2) {Long result = o2 - o1;return result.intValue();}});s.forEach(item->{System.out.print(item +" ");});}

同时常用的比较排序算法主要有：冒泡排序，选择排序，插入排序，归并排序，堆排序，快速排序等。

java的冒泡排序实现如下：

public static void bubbleSort(int []arr) { for(int i =0;i
<arr.length-1;i++) { for(int j="0;j
arr[j+1]) { int temp = arr[j]; arr[j]=arr[j+1]; arr[j+1]=temp; } } } }还有非比较排序，时间复杂度可以达到O(n)，主要有：计数排序，基数排序，桶排序等。

Java数组排序 几种排序方法详细一点

MongoDB是一个介于关系数据库和非关系数据库之间的产品，是非关系数据库当中功能最丰富，最像关系数据库的。它支持的数据结构非常松散，是类似json的bson格式，因此可以存储比较复杂的数据类型。
　　JAVA中在运用数组进行排序功能时，一般有四种方法：快速排序法、冒泡法、选择排序法、插入排序法。
　　快速排序法主要是运用了Arrays中的一个方法Arrays.sort（）实现。
　　冒泡法是运用遍历数组进行比较，通过不断的比较将最小值或者最大值一个一个的遍历出来。
　　选择排序法是将数组的第一个数据作为最大或者最小的值，然后通过比较循环，输出有序的数组。
　　插入排序是选择一个数组中的数据，通过不断的插入比较最后进行排序。下面我就将他们的实现方法一一详解供大家参考。
　　<1>利用Arrays带有的排序方法快速排序
public class Test2{ public static void main(String[] args){ int[] a={5,4,2,4,9,1}; Arrays.sort(a); //进行排序 for(int i: a){ System.out.print(i); } } }　　<2>冒泡排序算法
public static int[] bubbleSort(int[] args){//冒泡排序算法 for(int i=0;i
<args.length-1;i++){ for(int j="i+1;j
args[j]){ int temp=args[i]; args[i]=args[j]; args[j]=temp; } } } return args; }　　<3>选择排序算法

public static int[] selectSort(int[] args){//选择排序算法 for (int i=0;i
<args.length-1 ;i++ ){ int min="i;" for (int j="i+1;j
args[j]){ min=j; } } if (min!=i){ int temp=args[i]; args[i]=args[min]; args[min]=temp; } } return args; }　　<4>插入排序算法

public static int[] insertSort(int[] args){//插入排序算法 for(int i=1;i

0;j--){ if (args[j]
<args[j-1]){ int temp="args[j-1];" args[j-1]="args[j];" args[j]="temp;" }else break; } return args; }

java编程实现随机数组的快速排序

package basic.javastu; public class NumberTest {
public static void main(String[] args) { // TODO Auto-generated method stub
int[] numb=new int[]{3,42,57,1,32,24};
int len=numb.length;
int i,j;
int temp;
System.out.println("排序前的数组各个值:");
for(i=0;i
<len;i++)
{

System.out.print(numb[i]+"\t");

}

System.out.println("\n");

for(i=1;i<=len;i++)

{

for(j=len-1;j>=1;j--)

{

if(numb[j]>numb[j-1])

{

temp=numb[j];

numb[j]=numb[j-1];

numb[j-1]=temp;

}

}

}

System.out.println("排序后的数组各个值:");

for(i=0;i
<len;i++)
{

System.out.print(numb[i]+"\t");

}

}

}

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] + " "); } }}
</len;i++)
</len;i++)

如何用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[start];
while (start < end) {
while (n[end] >= tmp && start < end)
end--;
if (start < end) {
n[start++] = n[end];
}
while (n[start] < tmp && start < end)
start++;
if (start < end) {
n[end--] = n[start];
}
}
n[start] = tmp;
return start;
}
在代码中有这样一个函数：
public static void quickSortSwap(int[] n, int l, int h)
该函数可以实现，元素集合中特定的 l 到 h 位置间的数据元素进行排序。

如何理解java数据结构中的快速排序方法

原理：
快速排序也是分治法思想的一种实现，他的思路是使数组中的每个元素与基准值（Pivot，通常是数组的首个值，A[0]）比较，数组中比基准值小的放在基准值的左边，形成左部；大的放在右边，形成右部；接下来将左部和右部分别递归地执行上面的过程：选基准值，小的放在左边，大的放在右边。。。直到排序结束。
步骤：
1.找基准值，设Pivot = a[0]
2.分区（Partition）：比基准值小的放左边，大的放右边，基准值(Pivot)放左部与右部的之间。
3.进行左部（a[0] - a[pivot-1]）的递归，以及右部（a[pivot+1] - a[n-1]）的递归，重复上述步骤。
排序效果：

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

//快速排序（交换排序），不稳定，时间复杂度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

array[i]){ //判断左边元素

i++;

}

array[j]=array[i];

}

array[i]=index;

quickSort(array, low, i-1); //进行递归

quickSort(array, i+1, high);

}

}

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

}

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]+" ")

}

}

一般都是 二分法 和冒泡

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

</a.length;i++)
</a[j])
</r)quicksort(left,r,a);
</pivot)l++;
</r)

</j){