大家好，又见面了，我是全栈君。
今天大鹏哥跟大家一起学习下交换排序中的高速排序。
高速排序是对冒泡排序的一种改进。它的基本思想是。通过一趟排序将待排记录切割成独立的两部分，当中一部分记录的keyword均比还有一部分的keyword小。则可分别对这两部分记录继续进行排序，以达到真个序列有序。
高速排序基本步骤：
Step1、定义两个变量low和high，他们的初值分别为low和high，此外另一个变量pivotkey。
Step2、首先从high所指位置向前搜索找到第一个keyword小于pivotkey的记录和pivotkey交换。
Step3、从low所指位置向后搜索。找到第一个keyword大鱼pivotkey的记录和pivotkey交换。
Step4、反复以上步骤直到low=high为止。
待排序列：49 38 65 97 76 13 27 49
1、附设low和high以及设枢轴记录的keyword为pivotkey：
49 38 65 97 76 13 27 49
↑(low) ↑(high)
↑(pivotkey)
2、从high所指位置向前搜索，找到第一个小于pivotkey的记录（此处为27）和枢轴记录互相交换：
27 38 65 97 76 13 49 49
↑(low) ↑(high)
↑(pivotkey)
3、从low所指位置向后搜索，找到第一个大于pivotkey的记录（此处为65）和枢轴记录互相交换：
27 38 49 97 76 13 65 49
↑(low) ↑(high)
↑(pivotkey)
4、反复2、3步直至low=high为止。
27 38 13 97 76 49 65 49
↑(low) ↑(high)
↑(pivotkey)
27 38 13 49 76 97 65 49
↑(low) ↑(high)
↑(pivotkey)
27 38 13 49 76 97 65 49
↑(low=high)
↑(pivotkey)
上面给出的是一趟快排过程，整个快排过程可递归进行，上述操作完毕后，再分别对两个子序列进行高速排序。
Java实现例如以下：
public class QuickSort {
public static void main(String[] args) {
// TODO Auto-generatedmethod stub
int[] a={49,38,65,97,76,13,27,49};
int pivotloc,low=0,high=a.length-1;
System.out.print(“排序前:”);
for(int x:a){
System.out.print(x+“,”);
}
if(low<high){
pivotloc = quickSort(a,low,high);
quickSort(a,low,pivotloc-1);
quickSort(a,pivotloc+1,high);
}
System.out.print(“排序后:”);
for(int x:a){
System.out.print(x+“,”);
}
}
private static int quickSort(int[] a, int low, int high) {
int pivotkey=a[low];
while(low<high){
while(low<high&&a[high]>=pivotkey)
high–;
a[low]=a[high];
while(low<high&&a[low]<=pivotkey)
low++;
a[high]=a[low];
}
a[low]=pivotkey;
return low;
}
}
高速排序的时间复杂度为O(NlogN)。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/116541.html原文链接：https://javaforall.net
