/*需求:根据东尼霍尔1962年提出的快速排序原理写出快速排序算法
有了它妈妈再也不用担心我的数学成绩了
分析:将数组分成两组 一组比另一组所有的数值都大
1.定义两个助手 助手1和助手2 助手1在最左侧 助手2在最右侧
2.定义一个基准元素,基准元素一般为最左侧的元素
3.定义一个空位坐标(其实就是一个索引)默认在最左侧
4.助手1喊话要求助手2从右往左找出一个比基准元素小的值
5.助手2开始从右往左找,当发现比基准元素大的时候助手2就向左移动一位直到找到为止
6.助手2站在比基准元素小的值的地方忽然喊话"我找到了",于是他们一起将这个比基准元素小的值赋值给了空位坐标
7.这个时候空位坐标已经被占而助手2站的位置却空了 于是助手2将它的索引告诉了空位坐标并把他的下标赋值给了空位坐标
8.这个时候助手2喊话了 要求助手1从左往右找一个比基准元素大的值
9助手1开始行动当助手1遇到比基准元素小的值的时候就向右移动一位直到与找到比基准值大的值为止
10.助手1站在比基准元素大的值的地方突然喊话"我找到了",于是他们一起将这个比基准元素大的值赋值给了空位坐标
11.这个时候空位坐标已经被占用而助手1站在的位置却空了,于是助手1将它所在的坐标告诉了空位坐标并且把下标值赋值给了空位坐标
12就是这样多轮寻找后助手1跟助手2碰面,助手1就跟助手2商量,你右边的都比基准值大而我左边的都比基准值小要不我们就把基准值放到我们站的位置吧 他们一拍即合
13最后调用快速排序方法分别对助手1左边和助手2右边的两组值进行排序
14排序成功
*/
class QuickSort {
public static void main(String[] args) {
int [] arr={3,6,1,8,4,9,4,5,7,87,66,22,33,55,11,43,24,55,36,3,5,53,79,53,1,5,7,4};
for (int i=0;i<arr.length ;i++ ){
System.out.print(arr[i]+" ");
}
System.out.println();
quickSort(arr,0,arr.length-1);
for (int i=0;i<arr.length ;i++ ){
System.out.print(arr[i]+" ");
}
}
public static void quickSort(int[]arr,int start,int end ){ //参数为数组和助手1和助手2
int i=start; //助手1
int j=end; //助手2
int pivot = arr[i]; //基准值
int emplyIndex=i; //空位下标
//首先让助手2从右往左依次判断如果大于基准值则助手2向左移动一位
//直到找到比基准值小的值将值放到空位下标然后将助手2的位置定义为空位下标的位置
//至少要有两个值排序才有意义 所以比较1是否小于j
while(i<j){ // while外循环 直到所有的值都排序完为止 i<j是因为大于和等于就说明不成立或只有一个元素
while (i<j&&pivot<=arr[j]){ //while内循环当前值如果大于等于基准值,助手2就向左移动一位
j--; //助手2向左移动一位
}
if (i<j){ //判断是否符合排序条件
arr[emplyIndex]=arr[j]; //助手2不移动则说明已找到比基准值小的值并将这个值移动到空位下标所在的位置
emplyIndex=j; //因为将找到的值赋值给了空位坐标的值所以这个地方没有值 就将那个位置设置为空位下标也就是助手2所在的位置
}
while (i<j&&pivot>=arr[i]){ //这一组是用助手1从左往右找比比基准值大的值 如果比基准值小那么助手1的位置就向右移动一位直到找到比在基准值大的值
i++;
}
if (i<j){
arr[emplyIndex]=arr[i]; //不移动则说明已找到比基准值大的值那么就将这个值赋值给刚才移走空下来的空位下标
emplyIndex=i; //移走后原来这个位置已经没有值了 于是就将这个位置设置成空值下标
}
} //大循环结束 助手1和助手2不止一轮的排序 直到把助手1和助手2碰面位置
//这个时候i和j相遇于是就将基础元素放到空位坐标上面
arr[emplyIndex]=pivot;
if (i-start>1){ //i和j以及基准元素都在一个位置我们判断的是数组是否有两个元素是否能够排序 i在基准值位置只要减去第一个元素的位置大于1就说明只少有两个元素
quickSort(arr,0,i-1); //调用快速排序方法从0开始排序最大值是基准元素前的一个元素
}
if (end-j>1){ //i和j跟基准元素都在一个位置上我们判断的是j右边的元素所以只要end-j大于1就证明不低于两个元素符合排序
quickSort(arr,j+1,end); //调用快速排序方法 从基准元素右边一个开始排起到最后
}
}
}
|
|
收藏
淘帖
踩
