首页 > 代码库 > 快速排序算法小结
快速排序算法小结
快速排序是对冒泡排序的一种改进。它的基本思想是：通过一躺排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一不部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
假设要排序的数组是a[6],长度为7，首先任意选取一个数据（通常选用第一个数据）作为关键数据，然后将所有比它的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一躺快速排序。一躺快速排序的算法是：
1）、设置两个变量i，j，排序开始的时候i=0；j=6；
2）以第一个数组元素作为关键数据，赋值给key，即key=a[0]；
3）、从j开始向前搜索，即由后开始向前搜索（j--），找到第一个小于key的值，两者交换；
4）、从i开始向后搜索，即由前开始向后搜索（i++），找到第一个大于key的值，两者交换；
5）、重复第3、4步，直到i=j；此时将key赋值给a[i]；
例如：待排序的数组a的值分别是：（初始关键数据key=49）
a[0] a[1] a[2] a[3] a[4] a[5] a[6]
49 38 65 97 76 13 27
进行第一次交换后： 27 38 65 97 76 13 49
进行第二次交换后： 27 38 49 97 76 13 65
进行第三次交换后： 27 38 13 97 76 49 65
进行第四次交换后： 27 38 13 49 76 97 65
此时完成了一趟循环，将49赋值给a[3]，数据分为三组，分别为{27,38,13}{49}{76,96,65}，利用递归，分别对第一组和第三组进行排序，则可得到一个有序序列，这就是快速排序算法。
Java代码如下：
class Quick
{
public void sort(int a[], int low, int high){
int i=low;
int j=high;
int key=a[low];
if (low < high) {
// 枢纽元素
System.out.println("枢纽元素是：" + key + ",low:" + low + ",high:" + high);
while(i<j)
{
while(i<j&&key<=a[j])
{
j--;
}
// a[i]=a[j];
//这三行可以与前面一行互换，实现的功能相同。
int temp=a[j];
a[j]=a[i];
a[i]=temp;
while(i<j&&key>=a[i])
{
i++;
}
// a[j]=a[i];
//下面三行与上面一行功能相同
int temp1=a[j];
a[j]=a[i];
a[i]=temp1;
a[i]=key; //此处不可遗漏
// System.out.println("a["+i+"]="+a[i]);
}
sort(a,low,i-1);
sort(a,i+1,high);
}
}
} main函数如下：
public class HalfSerarch {
public static void main(String[] args) {
int len=10;
int [] a=new int[len];
System.out.println("排序前的数组为：");
for(int i=0;i<10;i++)
{
int t=(int) (Math.random()*100);
a[i]=t;
System.out.println("a["+i+"]="+a[i]);
}
Quick qc=new Quick();
qc.sort(a, 0, a.length-1);
System.out.println("排序后的数组为：");
for(int i=0;i<a.length;i++)
{
System.out.println("a["+i+"]="+a[i]);
}
}
<strong><span style="font-size:14px;">}</span></strong>结果如下：排序前的数组为： a[0]=54 a[1]=36 a[2]=83 a[3]=1 a[4]=0 a[5]=28 a[6]=88 a[7]=72 a[8]=82 a[9]=58 枢纽元素是：54,low:0,high:9 枢纽元素是：28,low:0,high:3 枢纽元素是：1,low:0,high:1 枢纽元素是：83,low:5,high:9 枢纽元素是：58,low:5,high:7 枢纽元素是：82,low:6,high:7 排序后的数组为： a[0]=0 a[1]=1 a[2]=28 a[3]=36 a[4]=54 a[5]=58 a[6]=72 a[7]=82 a[8]=83 a[9]=88
至此初步学习了快速排序算法，如果对你有帮助，记得点赞哦~
快速排序算法小结