快速排序哪位大神讲解一下 - 黑马程序员技术交流社区

package com.demo.test;
/**
* @author 史云龙
* 完成数组的快速排序
* 数组【100,40,60,87,34,11,56,0】
*快速排序：
*从小到大排列
*/
public class QuickSort {
/**
* @param args
* 主函数
*/
public static void main(String[] args) {
int[] array = {100,40,60,87,34,11,56,0};
sop("未进行快速排序的数组：");
print(array);
sop("已经进行快速排序的数组：");
sort(array,0,array.length-1);
print(array);
}
/**
* @param array【需要排序的数组】
* @param low【最低位】
* @param high【最高位】
* 快速排序[从小到大排序]
* 算法说明：
* 1、设置两个变量，low,high,初始排序时，low=0，high=array.length-1;
* 第6步中，由于需要对分成的两部分数组继续进行排序，
* 需要定义两个变化的值来分别初始low和high，这里定义为l、h;
* 2、以第l个数组元素作为关键数据，赋值给key，即key=array[l]
* 3、从h开始向前搜索，即由后向前搜索，找到第一个小于key的值array[h]，
* 将array[h]和array[l]互换，此后key为array[h]
* 4、从l开始向后搜索，即由前向后搜索，找到第一个大于key的值array[l]，
* 将array[l]和array[h]互换，此后key为array[l]
* 5、第一次排序结束后，如果l<h，则重复第3、4两步。
* 6、如果l>h是排序结束，左侧即【low----l】不一定是符合顺序的，则对左侧排序。
* 同时右侧【h----high】也不一定是符合顺序的，则对左侧进行排序的
* 由于此时l>=h，对左侧排序时将l进行-1，
* 对右侧进行排序时，将h进行+1,保证不会重复。
* （1）l>h即l=h+1,不可能有其他情况，因为l=h+1时，循环已经结束。
* 从新开始的排序的两段数组顺序可以看做为【low-h】【l-high】,完全包含这个数组。
* （2）l=h，
* 从新开始的排序的两段数组顺序可以看做为【low-l-1】【l=h】【h+1-high】,完全包含这个数组。
* 此时array[l]==array[h]大于左侧的数据，小于右侧的数据，可以不用重新排序。
*
*
*/
public static void sort(int[] array ,int low,int high){
//如果最小位置大于最大位置，直接返回。
if(low>=high)
return;
if((high-low)==1){
if(array[low]>array[high]){
swap(array,low,high);
}
return;
}
//默认排序的KEY值
int key = array[low];
//将最低值赋给一个变量，用于一次排序后进行后续排序分组
int l = low;
//将最高值赋给一个变量，作用同上
int h=high;
//如果l<h,则一直进行循环
while(l<h){
//从最后向前找，找到比key小的第一个数
//如果l<h,且key比array[h]小，则一直循环
//直到h小于等于l或此时h处的值比key小，则结束循环
//找到比key小的值向前移动
while(l<h&&key<array[h])
h--;
/*
与上述两行代码相同
while(l<h){
if(array[h]<key)
break;
h--;
}
*/
//交换l和h处位置的数据，key则是array[l]，交换，
//然后key就和array[h]相等，及此时key变换为array[h]
//交换的目的是将小点的数向前方移动
swap(array,l,h);
//从前向后找，找到比key（即array[h]）大的数
//如果l<h,且key(array[h])比array[l]大，则一直循环
//直到l大于等于h或此时l出的值比key大，则结束循环
//找到比key大的值向后移动
while(l<h&&key>array[l]){
l++;
}
/*
与上述两行代码相同
while(l<h){
if(array[l]>key)
break;
l++;
}
*/
//交换l和h处位置的数据，key则是array[h]，交换，
//然后key就和array[l]相等，及此时key变换为array[l]
//交换的目的是将小点的数向前方移动
swap(array,l,h);
}
//对数组的两部分继续排序
sort(array,low,l-1);
sort(array,h+1,high);
}
/**
* @param b【传入数组并进行打印】
*/
public static void print(int[] b){
for (int i=0;i<b.length;i++){
sop(b[i]);
if(i==b.length-1){
sop("\n");
}else{
sop(" , ");
}
}
}
/**
* @param array
* @param i
* @param j
* 将符合条件的数组数据交换位置
*/
public static void swap(int[] array,int i,int j){
int temp = array[i];
array[i]=array[j];
array[j]=temp;
}
/**
* @param obj[将obj输出]
*/
public static void sop(Object obj){
System.out.print(obj);
}
}

复制代码