快速排序算法全过程,快速排序

快速排序算法全过程,快速排序详细介绍

本文目录一览： 快速排序法

快速排序法一般指快速排序算法。
快速排序（Quicksort）是对冒泡排序的一种改进。
快速排序由C. A. R. Hoare在1960年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
排序流程
快速排序算法通过多次比较和交换来实现排序，其排序流程如下：?
(1)首先设定一个分界值，通过该分界值将数组分成左右两部分。?
(2)将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。此时，左边部分中各元素都小于或等于分界值，而右边部分中各元素都大于或等于分界值。?
(3)然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。
(4)重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。
快速排序（Quicksort）是对冒泡排序的一种改进。[1]
快速排序由C. A. R. Hoare在1960年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。[1]
中文名
快速排序算法
外文名
quick sort
别名
快速排序
提出者
C. A. R. Hoare
提出时间
1960年
快速
导航
排序步骤
程序调用举例
示例代码
性能分析
排序流程
快速排序算法通过多次比较和交换来实现排序，其排序流程如下：[2]
(1)首先设定一个分界值，通过该分界值将数组分成左右两部分。[2]
(2)将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。此时，左边部分中各元素都小于或等于分界值，而右边部分中各元素都大于或等于分界值。[2]
(3)然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。[2]
(4)重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。[2]
排序步骤
原理
设要排序的数组是A[0]……A[N-1]，首先任意选取一个数据（通常选
快排图
用数组的第一个数）作为关键数据，然后将所有比它小的数都放到它左边，所有比它大的数都放到它右边，这个过程称为一趟快速排序。值得注意的是，快速排序不是一种稳定的排序算法，也就是说，多个相同的值的相对位置也许会在算法结束时产生变动。[1]
一趟快速排序的算法是：[1]
1）设置两个变量i、j，排序开始的时候：i=0，j=N-1；[1]
2）以第一个数组元素作为关键数据，赋值给key，即key=A[0]；[1]
3）从j开始向前搜索，即由后开始向前搜索(j--)，找到第一个小于key的值A[j]，将A[j]和A[i]的值交换；[1]
4）从i开始向后搜索，即由前开始向后搜索(i++)，找到第一个大于key的A[i]，将A[i]和A[j]的值交换；[1]
5）重复第3、4步，直到i==j； (3,4步中，没找到符合条件的值，即3中A[j]不小于key,4中A[i]不大于key的时候改变j、i的值，使得j=j-1，i=i+1，直至找到为止。找到符合条件的值，进行交换的时候i， j指针位置不变。另外，i==j这一过程一定正好是i+或j-完成的时候，此时令循环结束）。[1]
排序演示
假设一开始序列{xi}是：5，3，7，6，4，1，0，2，9，10，8。
此时，ref=5，i=1，j=11，从后往前找，第一个比5小的数是x8=2，因此序列为：2，3，7，6，4，1，0，5，9，10，8。
此时i=1，j=8，从前往后找，第一个比5大的数是x3=7，因此序列为：2，3，5，6，4，1，0，7，9，10，8。
此时，i=3，j=8，从第8位往前找，第一个比5小的数是x7=0，因此：2，3，0，6，4，1，5，7，9，10，8。

快速排序算法

void QSort(SeqList L,int low,int high）改成void QSort(SeqList &L,int low,int high），加个&。
假设要排序的数组是A[1]……A[N]，首先任意选取一个数据（通常选用第一个数据）作为关键数据，然后将所有比它的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一躺快速排序。
1、设置两个变量I、J，排序开始的时候I：=1，J：=N；
2、以第一个数组元素作为关键数据，赋值给X，即X：=A[1]；
3、从J开始向前搜索，即由后开始向前搜索（J：=J-1），找到第一个小于X的值，两者交换；
4、从I开始向后搜索，即由前开始向后搜索（I：=I+1），找到第一个大于X的值，两者交换；
5、重复第3、4步，直到I=J。
原理
设要排序的数组是A[0]……A[N-1]，首先任意选取一个数据（通常选用数组的第一个数）作为关键数据，然后将所有比它小的数都放到它左边，所有比它大的数都放到它右边，这个过程称为一趟快速排序。值得注意的是，快速排序不是一种稳定的排序算法，也就是说，多个相同的值的相对位置也许会在算法结束时产生变动。
快速排序（Quicksort）是对冒泡排序的一种改进。
然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。
重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。
快速排序算法通过多次比较和交换来实现排序，其排序流程如下：
(1)首先设定一个分界值，通过该分界值将数组分成左右两部分。
(2)将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。此时，左边部分中各元素都小于或等于分界值，而右边部分中各元素都大于或等于分界值。

45,80,55，40,42,85快速排序第一次划分的结果 要过程越详细越好

快速排序过程即为如下三个步骤:
1.
选定序列中的一个元素，作为枢轴
2.
用该枢纽划分序列，使得位于枢轴左侧的序列都比枢纽小，位于枢轴右侧的数都比枢纽大
3.
对划分所得的序列重复1,2步，直到序列不可再分。
所以由上面的三个步骤可知:
1.快速排序每次都会将序列一分为二
2.划分完序列之后即确定了枢轴在最终有序序列所处的位置
快速排序第一次划分的结果，受到枢轴选择的影响，假设选择序列的第一个元素作为枢轴。
则枢轴为数字45，小于45的数将位于其左边，大于45的数将位于其右边，所以序列为:
(42,40)45(55,80,85)
1.
左右集合的内容在枢轴选定是即被确定
2.
左右集合中元素的次序收到具体的元素移动算法的影响，按照严版数据结构书中的移动方式其序列如上面所示。其步骤如下:
首先从右找到第一个比45小的元素42与45交换得到序列(42,80,55,40,45,85)
接着从左往右找到第一个比45大的元素80与45交换得到序列(42,45,55,40,80,85)
重复这个过程依次得到序列(42,40,55,45,80,85)、(42,40,45,55,80,85)即最终序列
注:这个过程移动过程并非是一定的，采用不同的元素移动算法可以得到不同的左右顺序序列。

快速排序算法原理与实现

基本原理
从序列中任选一个数作为“基准”；所有小于“基准”的数，都挪到“基准”的左边；所有大于等于“基准”的数，都挪到“基准”的右边。
在这次移动结束之后，该“基准”就处于两个序列的中间位置，不再参与后续的排序；针对“基准”左边和右边的两个子序列，不断重复上述步骤，直到所有子序列只剩下一个数为止。
1、选择“基准”，并将其从原始数组分离
先获取基准的索引值，再使用splice数组方法取出基准值。
Tips：该实例中， 基准的索引值 = parseInt（序列长度 / 2）。
Tips：splice方法会改变原始数组。例如，arr = [1, 2, 3]; 基准索引值为1，基准值为2，原始数组变为arr = [1, 3]。
2、遍历序列，拆分序列
与“基准”比较大小，并拆分为两个子序列，小于“基准”的数存储于leftArr数组当中，大于等于“基准”的数存储于rightArr数组当中。
Tips：当然，也可以将 小于等于“基准”的数存于leftArr，大于“基准”的数存于rightArr。
由于要遍历序列，将每一个数与“基准”进行大小比较，所以，需要借助for语句来实现
3、递归调用，遍历子序列并组合子序列的结果
定义一个函数，形参用于接收数组
function quickSort(arr) { }；
实现递归调用遍历子序列，用concat数组方法组合子序列的结果。
4、判断子序列的长度
递归调用的过程中，子序列的长度等于1时，则停止递归调用，返回当前数组。
扩展资料
一趟快速排序的算法是：
1）设置两个变量i、j，排序开始的时候：i=0，j=N-1；
2）以第一个数组元素作为关键数据，赋值给key，即key=A[0]；
3）从j开始向前搜索，即由后开始向前搜索(j--)，找到第一个小于key的值A[j]，将A[j]和A[i]互换；
4）从i开始向后搜索，即由前开始向后搜索(i++)，找到第一个大于key的A[i]，将A[i]和A[j]互换；
5）重复第3、4步，直到i=j； (3,4步中，没找到符合条件的值，即3中A[j]不小于key,4中A[i]不大于key的时候改变j、i的值，使得j=j-1，i=i+1，直至找到为止。
参考资料：百度百科 快速排序法
快速排序算法的原理与实现：
快速排序与归并排序已有,也使用分治思想。下面介绍下对一个典型的子数组A[p..r]进行快速排序的三步分治过程:分解:数组A[p..r]被划分为两个(可能为空)子数组A[p..q-1]和A[q+1..r],使得A[p..q-1]中的每一个元素都小于等于A[q],而A[q]也小于等于A[p..q-1]中的每个元素,其中,计算下标q也是划分过程的一部分。
解决:通过递归调用快速排序,对子数组A[p..q-1]和A[q+1..r]进行排序。
合并:因为子数组都是原址排序的,所以不需要合并操作:数组A[p..r]已经有序。
通俗点讲就是把数组根据一个参照值划分为两部分,左边部分小于等于参照值,右边部分大于等于参照值,然后再不断递归调用该方法,直到数组只有一个元素,就认为其是有序的.注意:划分过程,左边部分和右边部分可以是不均衡的。
例如：
//将数组排序成满足数组左边比中间值小,右边比中间值大的方法
int partition(int arr[], int left, int right)
{
int i = left, j = right;
int tmp;
//定义参照值为数组的中间值
int pivot = arr[(left + right) / 2];
while (i <= j) {
//当arr[i]小于参照值时,符合左边小的原则,不需调换位置,直接跳过,直到找到不满足条件的A[i]时终止该循环
while (arr[i] < pivot)i++;
//当arr[j]大于参照值时,符合右边大的原则,不需调换位置,直接跳过,直到找到不满足条件的A[j]时终止该循环
while (arr[j] > pivot)j--;
//i小于j时,完成a[i]和a[j]的交换
if (i <= j) {tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
i++;
j--;
} };
//返回的i就是满足i左边的值比i小.i右边的值比i大
return i;}
void quickSort(int arr[], int left, int right) {
int index = partition(arr, left, right);
// System.out.println("index"+index);
if (left < index - 1){quickSort(arr, left, index - 1);
// System.out.println(Arrays.toString(arr));}
if (index < right){quickSort(arr, index, right);
// System.out.println(Arrays.toString(arr));}}
@Test public void testQuickSort(){ int a[] = {222,5, 2, 4, 6, 1, 3, 11, 9, 10, 8, 7,0};quickSort(a,0,a.length - 1);
System.out.println("最终排序结果"+Arrays.toString(a));}
扩展资料：
快速排序（Quicksort）是对冒泡排序的一种改进。
快速排序由C. A. R. Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
参考链接：百度百科-快速排序算法
1、快速排序算法的原理：想必大家都学过和用过冒泡排序，这应该是大家成为程序员道路上学的第一个算法，那么我们的快速排序算法其实是在冒泡排序的基础上的一个改进，快速排序算法是利用一趟快速排序，一趟快排一般都是取第一个数作为准基数进行排序，将一串数据分成两个部分。
第一部分都比准基数小，第二部分都比准基数大。
如：（-------第一部分------准基数------第二部分------），也就这样以准基数分成了两个部分，接下来这两个部分继续使用一趟快排（可以用递归的方法），以此类推，最后数据显示是从小到大的排列顺序。
2、快速排序步骤：
我们先建立一组数据:
（1）根据一趟快排的规则，我们先定下一个准基数，通常准基数都是数据的第一位也就是这里的数字12。
（2）然后一趟快排是先从下标6向左进行和准基数12的比较，比较完一个后，然后再从下标0向右进行和准基数12的比较。
（3）我们进行比较的规则和操作是：从下标6向左进行和准基数12的比较，只要遇到的数据小于准基数12的时候我们就将这个数和准基数12进行替换，然后再执行从下标0向右进行和准基数12的比较.
如：我们从下标6向左进行和准基数12的比较，20>12，不满足一趟快排的规则，寻找下一位，1<12,所以我们将下标0的值和下标5的值进行替换替换后的结果为：
（4）执行完上一步之后，我们再从下标0向右进行和准基数12的比较，这里的规则是只要遇到的数据大于准基数12的时候我们就将这个数和准基数12进行替换，和上面一步恰恰相反。
如：我们再从下标0向右进行和准基数12的比较，30>12，所以我们将下标1的值和下标5的值进行替换。
（5）从左到右查找和从右到左的查找，都是通过下标来查找的，只要它们两者下标不相遇就可以一直进行排序，直到相遇后第一次一趟快排结束，不过，总有一次会相遇的。好了，执行完上一步之后，基本的套路也就生成了，接下来继续执行（3），（4）步骤，直到排序完成。
第一趟排序完成的结果为：
从上面第一次一趟快排结果我们可以看出从准基数那里将数据分成的两个部分，前面那一部分，1，5，5，都比准基数要小，后面的16，30，20，则比准基数要大。但是这还不算完，我们明显的看到排序并非从小到大。所以说我们需要把这整一条数据分成1，5，5和16，30，20这两个条数据再次进行一趟快排（递归），以此类推，直到排出一条规矩的数据为止。
最后的结果为：
3、快速排序代码实现：
public class QuickSort {
public static void main(String[] args) {
int arr[] = {49、38、65、97、76、13、27、49};
quickSort(arr, 0, 7);
System.out.println(Arrays.toString(arr));
}
public static void quickSort(int[] arr, int left, int right) {
if (left < right) {
int mid = partion(arr, left, right);
quickSort(arr, 0, mid - 1);
quickSort(arr, mid + 1, right);
}
}
public static void swap(int[] arr, int l, int r) {
int tmp = arr[l];
arr[l] = arr[r];
arr[r] = tmp;
}
public static int partion(int[] arr, int left, int right) {
while (left < right) {
while (left < right && arr[left] <= arr[right]) {
right--;
}
if (left
<right){
swap(arr, left, right);

}

while (left < right && arr[left] <= arr[right]) {

left++;

}

if (left
<right){
swap(arr, left, right);

}

}

return left;

}}

扩展资料：

快速排序由冒泡排序演变而来，冒泡排序原理：

1、比较相邻的元素。如果第一个比第二个大，就交换他们两个。

2、对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。

3、针对所有的元素重复以上的步骤，除了最后一个。

4、持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

参考资料：百度百科-快速排序

快速排序的原理：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

假设要排序的数组是A[1]……A[N]，首先任意选取一个数据（通常选用第一个数据）作为关键数据，然后将所有比它的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一躺快速排序。一躺快速排序的算法是：1）设置两个变量I、J，排序开始的时候I：=1，J：=N；2）以第一个数组元素作为关键数据，赋值给X，即X：=A[1]；3）从J开始向前搜索，即由后开始向前搜索（J：=J-1），找到第一个小于X的值，两者交换；4）从I开始向后搜索，即由前开始向后搜索（I：=I+1），找到第一个大于X的值，两者交换；5）重复第3、4步，直到I=J。

扩展资料

与普通快排不同的是，关键数据是一段buffer，首先将之前和之后的M/2个元素读入buffer并对该buffer中的这些元素进行排序，然后从被排序数组的开头（或者结尾）读入下一个元素，假如这个元素小于buffer中最小的元素，把它写到最开头的空位上；假如这个元素大于buffer中最大的元素，则写到最后的空位上。

否则把buffer中最大或者最小的元素写入数组，并把这个元素放在buffer里。保持最大值低于这些关键数据，最小值高于这些关键数据，从而避免对已经有序的中间的数据进行重排。完成后，数组的中间空位必然空出，把这个buffer写入数组中间空位。然后递归地对外部更小的部分，循环地对其他部分进行排序。

参考资料来源：百度百科—快速排序算法

快速排序的基本原理就是每一次把一个值放到它应该的位置上，然后序列被分为两部分，这个数前一部分后一部分，再对这两部分分别进行快速排序即可。

如此递归下去，但是对于基本有序的数列，你就不要快排了，那样效率会很低。

扩展资料：

算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。

如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。

算法中的指令描述的是一个计算，当其运行时能从一个初始状态和（可能为空的）初始输入开始，经过一系列有限而清晰定义的状态，最终产生输出并停止于一个终态。一个状态到另一个状态的转移不一定是确定的。随机化算法在内的一些算法，包含了一些随机输入。

形式化算法的概念部分源自尝试解决希尔伯特提出的判定问题，并在其后尝试定义有效计算性或者有效方法中成形。

这些尝试包括库尔特·哥德尔、Jacques Herbrand和斯蒂芬·科尔·克莱尼分别于1930年、1934年和1935年提出的递归函数，阿隆佐·邱奇于1936年提出的λ演算，1936年Emil Leon Post的Formulation 1和艾伦·图灵1937年提出的图灵机。即使在当前，依然常有直觉想法难以定义为形式化算法的情况。

参考资料：百度百科-算法

快速排序的基本思想就是从一个数组中任意挑选一个元素（通常来说会选择最左边的元素）作为中轴元素，将剩下的元素以中轴元素作为比较的标准，将小于等于中轴元素的放到中轴元素的左边，将大于中轴元素的放到中轴元素的右边。

然后以当前中轴元素的位置为界，将左半部分子数组和右半部分子数组看成两个新的数组，重复上述操作，直到子数组的元素个数小于等于1（因为一个元素的数组必定是有序的）。

以下的代码中会常常使用交换数组中两个元素值的Swap方法，其代码如下

public static void Swap(int[] A, int i, int j){

int tmp;

tmp = A[i];

A[i] = A[j];

A[j] = tmp;

扩展资料：

快速排序算法 的基本思想是：将所要进行排序的数分为左右两个部分，其中一部分的所有数据都比另外一 部分的数据小，然后将所分得的两部分数据进行同样的划分，重复执行以上的划分操作，直 到所有要进行排序的数据变为有序为止。

定义两个变量low和high，将low、high分别设置为要进行排序的序列的起始元素和最后一个元素的下标。第一次，low和high的取值分别为0和n-1，接下来的每次取值由划分得到的序列起始元素和最后一个元素的下标来决定。

定义一个变量key，接下来以key的取值为基准将数组A划分为左右两个部分，通 常，key值为要进行排序序列的第一个元素值。第一次的取值为A[0]，以后毎次取值由要划 分序列的起始元素决定。

从high所指向的数组元素开始向左扫描，扫描的同时将下标为high的数组元素依次与划分基准值key进行比较操作，直到high不大于low或找到第一个小于基准值key的数组元素，然后将该值赋值给low所指向的数组元素，同时将low右移一个位置。

如果low依然小于high，那么由low所指向的数组元素开始向右扫描，扫描的同时将下标为low的数组元素值依次与划分的基准值key进行比较操作，直到low不小于high或找到第一个大于基准值key的数组元素，然后将该值赋给high所指向的数组元素，同时将high左移一个位置。

重复步骤(3) (4)，直到low的植不小于high为止，这时成功划分后得到的左右两部分分别为A[low……pos-1]和A[pos+1……high]，其中，pos下标所对应的数组元素的值就是进行划分的基准值key，所以在划分结束时还要将下标为pos的数组元素赋值 为 key。

参考资料:快速排序算法_百度百科
</right){
</right){

快速排序算法的排序演示

程序员，数组排序，排序算法，插入排序，归并排序，基数排序，计数排序，桶排序
假设用户输入了如下数组： 下标 0 1 2 3 4 5 数据 6 2 7 3 8 9 创建变量i=0（指向第一个数据）, j=5(指向最后一个数据), k=6(赋值为第一个数据的值)。我们要把所有比k小的数移动到k的左面，所以我们可以开始寻找比6小的数，从j开始，从右往左找，不断递减变量j的值，我们找到第一个下标3的数据比6小，于是把数据3移到下标0的位置，把下标0的数据6移到下标3，完成第一次比较： 下标 0 1 2 34 5 数据 3 2 7 6 8 9 i=0 j=3 k=6接着，开始第二次比较，这次要变成找比k大的了，而且要从前往后找了。递加变量i，发现下标2的数据是第一个比k大的，于是用下标2的数据7和j指向的下标3的数据的6做交换，数据状态变成下表： 下标 0 1 2 3 4 5 数据 3 2 6 7 8 9 i=2 j=3 k=6称上面两次比较为一个循环。接着，再递减变量j，不断重复进行上面的循环比较。在本例中，我们进行一次循环，就发现i和j“碰头”了：他们都指向了下标2。于是，第一遍比较结束。得到结果如下，凡是k(=6)左边的数都比它小，凡是k右边的数都比它大： 下标 0 1 2 3 4 5 数据 3 2 6 7 8 9 如果i和j没有碰头的话，就递加i找大的，还没有，就再递减j找小的，如此反复，不断循环。注意判断和寻找是同时进行的。然后，对k两边的数据，再分组分别进行上述的过程，直到不能再分组为止。注意：第一遍快速排序不会直接得到最终结果，只会把比k大和比k小的数分到k的两边。为了得到最后结果，需要再次对下标2两边的数组分别执行此步骤，然后再分解数组，直到数组不能再分解为止（只有一个数据），才能得到正确结果。 在c++中可以用函数qsort（）可以直接为数组进行排序。 用 法:void qsort(void *base, int nelem, int width, int (*fcmp)(const void *,const void *));参数：　　1 待排序数组首地址　　2 数组中待排序元素数量　　3 各元素的占用空间大小　　4 指向函数的指针，用于确定排序的顺序

快速排序怎么排

.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:005px0;padding:5px;border:1pxsolid#d4d4d4;background-image:-webkit-linear-gradient(#fff,#e5eecc100px);background-image:linear-gradient(#fff,#e5eecc100px)}div.example_code{line-height:1.4em;width:98%;background-color:#fff;padding:5px;border:1pxsolid#d4d4d4;font-size:110%;font-family:Menlo,Monaco,Consolas,"AndaleMono","lucidaconsole","CourierNew",monospace;word-break:break-all;word-wrap:break-word}div.example_result{background-color:#fff;padding:4px;border:1pxsolid#d4d4d4;width:98%}div.code{width:98%;border:1pxsolid#d4d4d4;background-color:#f6f4f0;color:#444;padding:5px;margin:0}div.codediv{font-size:110%}div.codediv,div.codep,div.example_codep{font-family:"couriernew"}pre{margin:15pxauto;font:12px/20pxMenlo,Monaco,Consolas,"AndaleMono","lucidaconsole","CourierNew",monospace;white-space:pre-wrap;word-break:break-all;word-wrap:break-word;border:1pxsolid#ddd;border-left-width:4px;padding:10px15px}排序算法是《数据结构与算法》中最基本的算法之一。排序算法可以分为内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。以下是快速排序算法：快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序n个项目要Ο(nlogn)次比较。在最坏状况下则需要Ο(n2)次比较，但这种状况并不常见。事实上，快速排序通常明显比其他Ο(nlogn)算法更快，因为它的内部循环（innerloop）可以在大部分的架构上很有效率地被实现出来。快速排序使用分治法（Divideandconquer）策略来把一个串行（list）分为两个子串行（sub-lists）。快速排序又是一种分而治之思想在排序算法上的典型应用。本质上来看，快速排序应该算是在冒泡排序基础上的递归分治法。快速排序的名字起的是简单粗暴，因为一听到这个名字你就知道它存在的意义，就是快，而且效率高！它是处理大数据最快的排序算法之一了。虽然WorstCase的时间复杂度达到了O(n?)，但是人家就是优秀，在大多数情况下都比平均时间复杂度为O(nlogn)的排序算法表现要更好，可是这是为什么呢，我也不知道。好在我的强迫症又犯了，查了N多资料终于在《算法艺术与信息学竞赛》上找到了满意的答案：快速排序的最坏运行情况是O(n?)，比如说顺序数列的快排。但它的平摊期望时间是O(nlogn)，且O(nlogn)记号中隐含的常数因子很小，比复杂度稳定等于O(nlogn)的归并排序要小很多。所以，对绝大多数顺序性较弱的随机数列而言，快速排序总是优于归并排序。1.算法步骤从数列中挑出一个元素，称为"基准"（pivot）;重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；2.动图演示代码实现JavaScript实例functionquickSort(arr,left,right){varlen=arr.length,partitionIndex,left=typeofleft!='number'?0:left,right=typeofright!='number'?len-1:right;if(left
<right){partitionindex=partition(arr,left,right);quicksort(arr,left,partitionindex-1);quicksort(arr,partitionindex+1,right);}returnarr;}functionpartition(arr,left,right){ 分区操作varpivot="left,//设定基准值（pivot）index=pivot+1;for(vari=index;i<=right;i++){if(arr[i]<arr[pivot]){swap(arr,i,index);index++;}}swap(arr,pivot,index-1);returnindex-1;}functionswap(arr,i,j){vartemp=arr[i];arr[i]=arr[j];arr[j]=temp;}functionpartition2(arr,low,high){letpivot=arr[low];while(low<high){while(low
pivot){--high;}arr[low]=arr[high];while(low
<high&&arr[low]<=pivot){++low;}arr[high]=arr[low];}arr[low]=pivot;returnlow;}functionquicksort2(arr,low,high){if(low<high){letpivot=partition2(arr,low,high);quicksort2(arr,low,pivot-1);quicksort2(arr,pivot+1,high);}returnarr;}python实例defquicksort(arr,left=none,right=none):left=0ifnotisinstance(left,(int,float))elseleftright=len(arr)-1ifnotisinstance(right,(int,float))elserightifleft<right:partitionindex=partition(arr,left,right)quicksort(arr,left,partitionindex-1)quicksort(arr,partitionindex+1,right)returnarrdefpartition(arr,left,right):pivot=leftindex=pivot+1i=indexwhilei<=right:ifarr[i]<arr[pivot]:swap(arr,i,index)index+=1i+=1swap(arr,pivot,index-1)returnindex-1defswap(arr,i,j):arr[i],arr[j]=arr[j],arr[i]go实例funcquicksort(arr[]int)[]int{return_quicksort(arr,0,len(arr)-1)}func_quicksort(arr[]int,left,rightint)[]int{ifleft<right{partitionindex:=partition(arr,left,right)_quicksort(arr,left,partitionindex-1)_quicksort(arr,partitionindex+1,right)}returnarr}funcpartition(arr[]int,left,rightint)int{pivot:=leftindex:=pivot+1fori:=index;i<=right;i++{ifarr[i]<arr[pivot]{swap(arr,i,index)index+=1}}swap(arr,pivot,index-1)returnindex-1}funcswap(arr[]int,i,jint){arr[i],arr[j]=arr[j],arr[i]}c++实例 严蔚敏《数据结构》标准分割函数paritition1(inta[],intlow,inthigh){intpivot="A[low];while(low<high){while(low
=pivot){--high;}A[low]=A[high];while(low
<high&&a[low]<=pivot){++low;}a[high]=a[low];}a[low]=pivot;returnlow;}voidquicksort(inta[],intlow,inthigh) 快排母函数{if(low<high){intpivot="Paritition1(A,low,high);QuickSort(A,low,pivot-1);QuickSort(A,pivot+1,high);}}Java实例publicclassQuickSortimplementsIArraySort{@Overridepublicint[]sort(int[]sourceArray)throwsException{//对arr进行拷贝，不改变参数内容int[]arr=Arrays.copyOf(sourceArray,sourceArray.length);returnquickSort(arr,0,arr.length-1);}privateint[]quickSort(int[]arr,intleft,intright){if(left<right){intpartitionIndex=partition(arr,left,right);quickSort(arr,left,partitionIndex-1);quickSort(arr,partitionIndex+1,right);}returnarr;}privateintpartition(int[]arr,intleft,intright){//设定基准值（pivot）intpivot=left;intindex=pivot+1;for(inti=index;i<=right;i++){if(arr[i]<arr[pivot]){swap(arr,i,index);index++;}}swap(arr,pivot,index-1);returnindex-1;}privatevoidswap(int[]arr,inti,intj){inttemp=arr[i];arr[i]=arr[j];arr[j]=temp;}}PHP实例functionquickSort($arr){if(count($arr)<=1)return$arr;$middle=$arr[0];$leftArray=array();$rightArray=array();for($i=1;$i
$middle)$rightArray[]=$arr[$i];else$leftArray[]=$arr[$i];}$leftArray=quickSort($leftArray);$leftArray[]=$middle;$rightArray=quickSort($rightArray);returnarray_merge($leftArray,$rightArray);}C实例typedefstruct_Range{intstart,end;}Range;Rangenew_Range(ints,inte){Ranger;r.start=s;r.end=e;returnr;}voidswap(int*x,int*y){intt=*x;*x=*y;*y=t;}voidquick_sort(intarr[],constintlen){if(len<=0)return;//避免len等於_值_引_段__（SegmentFault）//r[]模_列表,p__量,r[p++]_push,r[--p]_pop且取得元素Ranger[len];intp=0;r[p++]=new_Range(0,len-1);while(p){Rangerange=r[--p];if(range.start>=range.end)continue;intmid=arr[(range.start+range.end)/2];//_取中___基__intleft=range.start,right=range.end;do{while(arr[left]

mid)--right;//__基__右_是否符合要求if(left<=right){swap(&arr[left],&arr[right]);left++;right--;//移_指_以__}}while(left<=right);if(range.start

left)r[p++]=new_Range(left,range.end);}}递归法实例voidswap(int*x,int*y){intt=*x;*x=*y;*y=t;}voidquick_sort_recursive(intarr[],intstart,intend){if(start>=end)return;intmid=arr[end];intleft=start,right=end-1;while(left
<right){while(arr[left]<mid&&left
=mid&&left

=arr[end])swap(&arr[left],&arr[end]);elseleft++;if(left)quick_sort_recursive(arr,start,left-1);quick_sort_recursive(arr,left+1,end);}voidquick_sort(intarr[],intlen){quick_sort_recursive(arr,0,len-1);}C++函数法sort(a,a+n);//排序a[0]-a[n-1]的所有数.迭代法实例//参考：http://www.dutor.net/index.php/2011/04/recursive-iterative-quick-sort/structRange{intstart,end;Range(ints=0,inte=0){start=s,end=e;}};template

//整_或浮__皆可使用,若要使用物件(class)_必__定"小於"(<)、"大於"(>)、"不小於"(>=)的_算子功能voidquick_sort(Tarr[],constintlen){if(len<=0)return;//避免len等於_值_宣告堆__列__//r[]模_堆_,p__量,r[p++]_push,r[--p]_pop且取得元素Ranger[len];intp=0;r[p++]=Range(0,len-1);while(p){Rangerange=r[--p];if(range.start>=range.end)continue;Tmid=arr[range.end];intleft=range.start,right=range.end-1;while(left
<right){while(arr[left]<mid&&left
=mid&&left

=arr[range.end])std::swap(arr[left],arr[range.end]);elseleft++;r[p++]=Range(range.start,left-1);r[p++]=Range(left+1,range.end);}}递归法实例template

voidquick_sort_recursi

</right){while(arr[left]<mid&&left

</right){while(arr[left]<mid&&left

</high&&a[low]
</high&&arr[low]<=pivot){++low;}arr[high]=arr[low];}arr[low]=pivot;returnlow;}functionquicksort2(arr,low,high){if(low<high){letpivot=partition2(arr,low,high);quicksort2(arr,low,pivot-1);quicksort2(arr,pivot+1,high);}returnarr;}python实例defquicksort(arr,left=none,right=none):left=0ifnotisinstance(left,(int,float))elseleftright=len(arr)-1ifnotisinstance(right,(int,float))elserightifleft<right:partitionindex=partition(arr,left,right)quicksort(arr,left,partitionindex-1)quicksort(arr,partitionindex+1,right)returnarrdefpartition(arr,left,right):pivot=leftindex=pivot+1i=indexwhilei<=right:ifarr[i]<arr[pivot]:swap(arr,i,index)index+=1i+=1swap(arr,pivot,index-1)returnindex-1defswap(arr,i,j):arr[i],arr[j]=arr[j],arr[i]go实例funcquicksort(arr[]int)[]int{return_quicksort(arr,0,len(arr)-1)}func_quicksort(arr[]int,left,rightint)[]int{ifleft<right{partitionindex:=partition(arr,left,right)_quicksort(arr,left,partitionindex-1)_quicksort(arr,partitionindex+1,right)}returnarr}funcpartition(arr[]int,left,rightint)int{pivot:=leftindex:=pivot+1fori:=index;i<=right;i++{ifarr[i]

快速排序

public class QuickSort { public static void sort(Comparable[] data, int low, int high) { // 枢纽元,一般以第一个元素为基准进行划分 int i = low; int j = high; if (low < high) { // 从数组两端交替地向中间扫描 Comparable pivotKey = data[low]; // 进行扫描的指针i,j;i从左边开始,j从右边开始 while (i < j) { while (i < j && data[j].compareTo(pivotKey) > 0) { j--; }// end while if (i < j) { // 比枢纽元素小的移动到左边 data[i] = data[j]; i++; }// end if while (i < j && data[i].compareTo(pivotKey) < 0) { i++; }// end while if (i < j) { // 比枢纽元素大的移动到右边 data[j] = data[i]; j--; }// end if }// end while // 枢纽元素移动到正确位置 data[i] = pivotKey; // 前半个子表递归排序 sort(data, low, i - 1); // 后半个子表递归排序 sort(data, i + 1, high); }// end if }// end sort public static void main(String[] args) { // 在JDK1.5版本以上,基本数据类型可以自动装箱 // int,double等基本类型的包装类已实现了Comparable接口 Comparable[] c = { 6,5,4,2,7,3,1,8}; sort(c, 0, c.length - 1); for (Comparable data : c) { System.out.println(data); } } }
你排序的过程中，在if (dest[--j] == null)这一句出现异常，因为没有检查j的取值，比如这时j=0，然后先--j那么就变成负的了，这时当然超出范围了。
建议改成if (j > 0 && dest[--j] == null)，同样 if (dest[++i] == null)也存在隐患，可以改成 if (i
<right && dest[++i]="=" null)
综述，并不是你设置数组范围大小引起的问题，而是在数组大了后，进行一系统交换或运算出现那种情况，因此才暴露出了问题。

基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

设要排序的数组是A[0]……A[N-1]，首先任意选取一个数据（通常选用第一个数据）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一趟快速排序。一趟快速排序的算法是：

1）设置两个变量I、J，排序开始的时候：I=0，J=N-1；

2）以第一个数组元素作为关键数据，赋值给key，即 key=A[0]；

3）从J开始向前搜索，即由后开始向前搜索（J=J-1），找到第一个小于key的值A[J]，并与A[I]交换；

4）从I开始向后搜索，即由前开始向后搜索（I=I+1），找到第一个大于key的A[I]，与A[J]交换；

5）重复第3、4、5步，直到 I=J； (3,4步是在程序中没找到时候j=j-1，i=i+1，直至找到为止。找到并交换的时候i， j指针位置不变。另外当i=j这过程一定正好是i+或j+完成的最后另循环结束) 6 5 4 2 7 3 1 8

以7为key进行排序:

第一次交换：6 5 4 2 3 7 1 8

第二次交换：6 5 4 2 3 1 7 8

至此完成第一趟排序得到{6 5 4 2 3 1} 7 {8}两个部分再按以上思想进行排序；

对于前一部分假设以4为key进行排序后半部分只有一个数就不要排了:

第一次交换：4 5 6 2 3 1

第二次交换：2 5 6 4 3 1

第三次交换：2 5 6 3 4 1

第四次交换：2 5 6 3 1 4

第五次交换：2 4 6 3 1 5

第六次交换：2 3 6 4 1 5

第七次交换：2 3 4 6 1 5

第八次交换：2 3 1 6 4 5

第九次交换：2 3 1 4 6 5

至此完成第二趟排序得到{2 3 1} 4 {6 5}两个部分再按以上思想进行排序；

前半部分得到{1 2 3},后半部分得到{5 6};

至此排序结束。

希望对LZ有帮助。

PHP快速排序算法实现的原理及代码详解

算法原理
下列动图来自五分钟学算法，演示了快速排序算法的原理和步骤。
步骤:
从数组中选个基准值
将数组中大于基准值的放同一边、小于基准值的放另一边，基准值位于中间位置
递归的对分列两边的数组再排序
代码实现
function
quickSort($arr)
{
$len
=
count($arr);
if
($len
<=
1)
{
return
$arr;
}
$v
=
$arr[0];
$low
=
$up
=
array();
for
($i
=
1;
$i
<
$len;
++$i)
{
if
($arr[$i]
>
$v)
{
$up[]
=
$arr[$i];
}
else
{
$low[]
=
$arr[$i];
}
}
$low
=
quickSort($low);
$up
=
quickSort($up);
return
array_merge($low,
array($v),
$up);
}
测试代码:
$startTime
=
microtime(1);
$arr
=
range(1,
10);
shuffle($arr);
echo
"before
sort:
",
implode(',
',
$arr),
"\n";
$sortArr
=
quickSort($arr);
echo
"after
sort:
",
implode(',
',
$sortArr),
"\n";
echo
"use
time:
",
microtime(1)
-
$startTime,
"s\n";
测试结果:
before
sort:
1,
7,
10,
9,
6,
3,
2,
5,
4,
8
after
sort:
1,
2,
3,
4,
5,
6,
7,
8,
9,
10
use
time:
0.0009009838104248s
时间复杂度
快速排序的时间复杂度在最坏情况下是O(N2)，平均的时间复杂度是O(N*lgN)。
这句话很好理解：假设被排序的数列中有N个数。遍历一次的时间复杂度是O(N)，需要遍历多少次呢？至少lg(N+1)次，最多N次。
1)
为什么最少是lg(N+1)次？快速排序是采用的分治法进行遍历的，我们将它看作一棵二叉树，它需要遍历的次数就是二叉树的深度，而根据完全二叉树的定义，它的深度至少是lg(N+1)。因此，快速排序的遍历次数最少是lg(N+1)次。
2)
为什么最多是N次？这个应该非常简单，还是将快速排序看作一棵二叉树，它的深度最大是N。因此，快读排序的遍历次数最多是N次。
您可能感兴趣的文章:PHP快速排序算法实例分析PHP四种排序算法实现及效率分析【冒泡排序,插入排序,选择排序和快速排序】PHP排序算法之快速排序(Quick
Sort)及其优化算法详解PHP递归实现快速排序的方法示例php
二维数组快速排序算法的实现代码PHP常用排序算法实例小结【基本排序，冒泡排序，快速排序，插入排序】PHP快速排序quicksort实例详解