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

如何用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 位置间的数据元素进行排序。

1. 关键是在数组中选择一个元素作为比较对象来将原先的数组分为2部分，一部分比这个元素小，另外一部分比这个元素大，然后分别在两个数组中各选取一个元素进行比较排序.

原理：

快速排序也是分治法思想的一种实现，他的思路是使数组中的每个元素与基准值（Pivot，通常是数组的首个值，A[0]）比较，数组中比基准值小的放在基准值的左边，形成左部；大的放在右边，形成右部；接下来将左部和右部分别递归地执行上面的过程：选基准值，小的放在左边，大的放在右边。。。直到排序结束。

步骤：

1.找基准值，设Pivot = a[0] 

2.分区（Partition）：比基准值小的放左边，大的放右边，基准值(Pivot)放左部与右部的之间。

3.进行左部（a[0] - a[pivot-1]）的递归，以及右部（a[pivot+1] - a[n-1]）的递归，重复上述步骤。

 

排序效果：

---

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

新干县13730076919： 哪位帮我讲讲java中的快速排序法 - ？
别滢前列： 快速排序是对冒泡排序的一种改进.它的基本思想是:通过一躺排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按次方法对这两部分数据分别进行快速排序,整个排序过程可以递归进...

新干县13730076919： 如何用java实现快速排序,简答讲解下原理 - ？
别滢前列： 快速排序思想: 通过对数据元素集合Rn 进行一趟排序划分出独立的两个部分.其中一个部分的关键字比另一部分的关键字小.然后再分别对两个部分的关键字进行一趟排序,直到独立的元素只有一个,此时整个元素集合有序. 快速排序的过程...

新干县13730076919： java中的快速排序法底层是如何实现的? - ？
别滢前列： 分为好几种,如果你看过源码的话,它是根据要排序的对象个数来进行区分的. 比如界定是N 当小于N的时候用的 是冒泡排序 当大于N的时候用的是快速排序如果是eclipse环境的话,在安装源码的前提下,很容易就能看到源码了. 其他问题百度一下,你就知道

新干县13730076919： 数据结构排序中的快速排序什么叫选取第一个中间一个和最后一个元素中的中间一个来作为基准 - ？
别滢前列： 为了避免出现较坏(复杂度较高)的情况出现,要选取一个较好的枢轴变量.对于较为随机的数组,可以选第一个数.一般也可以从前、中、后三个元素中选一个合适的作为枢轴变量.举一个例子:17...8...10,...表示省略的数.这时候,我们认为选10比较合适(8

新干县13730076919： 请问Java快速排序法是怎么算的? - ？
别滢前列： * 步骤为: * 1. 从数列中挑出一个元素,称为 ＂基准＂(pivot), * 2. 重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边).在这个分割之后,该基准是它的最后位置.这个称...

新干县13730076919： Java快速排序法是怎么算的? - ？
别滢前列：/*** 快速排序* 快速排序使用分治法(Divide and conquer)策略来把一个序列(list)分为两个子序列(sub-lists).* 步骤为:* 1. 从数列中挑出一个元素,称为 ＂基准＂(pivot),* 2. 重新排序数列,所有元素比基准值小的摆放在基准前面...

新干县13730076919： 数据结构里的快速排序怎样理解谁知道?？
别滢前列： 快速排序法的基本精神是在数列中找出适当的轴心,然后将数列一分为二,分别对左边与右边数列进行排序,而影响快速排序法效率的正是轴心的选择.

新干县13730076919： JAVA中有哪几种常用的排序方法 - ？
别滢前列： 1、冒泡排序 冒泡排序是一个比较简单的排序方法.在待排序的数列基本有序的情况下排序速度较快.若要排序的数有n个,则需要n-1轮排序,第j轮排序中,从第一个数开始,相邻两数比较,若不符合所要求的顺序,则交换两者的位置;直到第...

新干县13730076919： 数据结构 快速排序的原理是什么? - ？
别滢前列： 找一个值作为参考值,比参考值大的就放在右边,比参考值小的就放在左边.那么一趟完成后就将数组分成了两部分:参考值左边的都是小于参考值的数,参考值右边的都是大于参考值的数,然后分别递归求这两部分,最后得到的就是一个排好序的数组了.