快速排序--学习

快速排序

排序原理

1、先假定一个分界值，通过该分界值将数组分成左右两个部分；

2、将大于或等于分界值的数据放到数组右边，小于分界值的数据放到数组的左边，此时左边部分中各元素都小于或等于分界值，而右边 部分中各元素都大于或等于分界值。

3、然后，左边和右边的数据可以独立排序，对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放 置最小值，右边放置最大值，右侧的数组数据也可以做类似处理。

4、重复上述过程，可以看出，这是一个递归定义，通过递归将左侧部分排好序后，在递归排好右侧部分的顺序、当左侧和右侧两个部分 的数据排序完毕后，整个数组的排序也就完成了。

原始数据

0	1	2	3	4	5	6	7	8
6	1	2	7	9	3	4	5	8

最终代码

public class QuickSort {
    public static void main(String[] args) {
        int[] value = {6,1,2,7,9,3,4,5,8};
        new QuickSort().sort(value);
        for (int item : value) {
            System.out.print(item + ",");
        }
    }


    public void sort(int[] value){
        int right = value.length - 1;
        System.out.println("right:" + right);
        this.quickSort(value, 0, right);
    }

    public void quickSort(int[] value, int left, int right){
        int l = left;
        int r = right;
        int baseValue = value[(left+right)/2];
        int temp;

        while (l < r){
            while (value[l] < baseValue){
                l = l + 1;
            }

            while (value[r] > baseValue){
                r = r - 1;
            }

            if (l >= r){
                break;
            }

            System.out.println("l:" + l + "  r:" + r);
            //交换
            temp = value[r];
            value[r] = value[l];
            value[l] = temp;

            if (value[l] == baseValue){
                r = r -1;
            }

            if (value[r] == baseValue){
                l = l + 1;
            }
        }

        if (l == r){
            l = l + 1;
            r = r - 1;
        }

        if (left < r){
            quickSort(value, left, r);
        }

        if (right > l){
            quickSort(value, l, right);
        }
    }
}

流程分析

上面蓝色箭头代表左指针，右边箭头代表右指针，下面粉红色箭头代表分界值指针。

先从（0,8）这个区间开始, 判断左侧索引是否小于右侧索引，成立则继续执行

让左边指针不停的向右移动，只要数字比参考值小，就继续向右移动，小于或者等于参考值则停下。

让右边指针不停的向左移动，只要数字比参考值大，就继续向左移动，小于或者等于参考值则停下。

	......
        
while (l < r){      			//----> l代表左侧索引，----->r代表右侧索引                       
            while (value[l] < baseValue){	//baseValue代表参考值，参考值计算为(l+r) / 2
                l = l + 1;
            }

            while (value[r] > baseValue){
                r = r - 1;
            }

            if (l >= r){
                break;
            }

    ......

左边指针停在 数字（9）上面，说明数字大于或者等于参考值

右边指针停在数字（8）上面，说明数字小于或者等于参考值

判断左指针是否大于或者等于右边指针，如果大于或者相同则停止操作，如果不同则交换两个数字

	......
            
while (l < r){
            while (value[l] < baseValue){
                l = l + 1;
            }

            while (value[r] > baseValue){
                r = r - 1;
            }

            if (l >= r){  //就是这个判断
                break;
            }
     
        	//此时左边指针的数字大于参考值，右边指针的数字小于参考值
            temp = value[r];
            value[r] = value[l];
            value[l] = temp;   
     
     ......

左指针显然没有大于或者等于右边指针，交换数字（9）和（8）的位置

此时判断左边指针的值是否和参考值相等，如果相等就将右边指针向左移动一位

判断右边指针的值是否和参考值相等，如果相等就将左边指针向右移动一位

规律：左边相等，右边指针向左移动一位，右边相等，左边指针向右移动一位

while (l < r){
            while (value[l] < baseValue){
                l = l + 1;
            }

            while (value[r] > baseValue){
                r = r - 1;
            }

            if (l >= r){
                break;
            }

            temp = value[r];
            value[r] = value[l];
            value[l] = temp;

    		//如果左指针的数和参考值相等，则将右指针向左移动一位
            if (value[l] == baseValue){
                r = r -1;
            }

    		//如果右指针的数和参考值相等，则将左指针向右移动一位
            if (value[r] == baseValue){
                l = l + 1;
            }
        }

​ 左边指针右移一位，继续向右移动，只要数字比参考值小，就继续向右移动，小于或者等于参考值则停下。

while (l < r){							//当l<r时，可以继续执行外层的while循环
    
    //左指针右移继续寻找
      while (value[l] < baseValue){
         l = l + 1;
     }

    //右指针此时与参考值相同，不会移动
      while (value[r] > baseValue){
      	r = r - 1;
	 }
} 

找到数字9

判断左指针是否大于或者等于右边指针，如果大于或者相同则停止操作，如果不同则交换两个数字

很显然，左边指针和右边指针相同，停止本次操作

  if (l >= r){
       break;
  }

两边指针相同 ，需要将左边指针向右移动一位，将右边指针向左移动一位（看下图）

若左侧索引小于右边指针，则确定排序范围是（左侧索引，右边指针） ----------->也就是（0,8）,这里递归调用了自身

若右侧索引大于左边指针，则确定排序范围（左边指针，右侧索引） --------------------->这里显然就不成立，递归回来不会再调用自身方法

提示这里有递归，判断右侧索引大于左侧指针这一步还没有执行，给个编号：未执行步骤一

 public void quickSort(int[] value, int left, int right){
        int l = left;		//------------------------------->这次left：0
        int r = right;		//------------------------------->这次right：7
        int baseValue = value[(left+right)/2];
        int temp;

        while (l < r){
            while (value[l] < baseValue){
                l = l + 1;
            }

            while (value[r] > baseValue){
                r = r - 1;
            }

            if (l >= r){
                break;
            }

            //交换
            temp = value[r];
            value[r] = value[l];
            value[l] = temp;

            if (value[l] == baseValue){
                r = r -1;
            }

            if (value[r] == baseValue){
                l = l + 1;
            }
        }

        if (l == r){
            l = l + 1;
            r = r - 1;
        }

        if (left < r){					//left：0，r：7
            quickSort(value, left, r); // ---->本次执行的是这一步
        }

        if (right > l){
            quickSort(value, l, right); // ----->这一步还没有执行
        }
    }

在（左侧索引，右边指针）这个区间里进行排序也就是（0,7）

	......
        
while (l < r){                    //这里显然是成立的         
            while (value[l] < baseValue){
                l = l + 1;
            }

            while (value[r] > baseValue){
                r = r - 1;
            }

            if (l >= r){
                break;
            }

    ......

条件满足

左边指针依然向右移动，只要数字比参考值小，就继续向右移动，小于或者等于参考值则停下。

右边指针依然向左移动，只要数字比参考值大，就继续向左移动，小于或者等于参考值则停下。

while (value[l] < baseValue){
     l = l + 1;
}
while (value[r] > baseValue){
     r = r - 1;
}

左边指针停在 数字（7）上面，说明数字大于或者等于参考值

右边指针停在数字（5）上面，说明数字小于或者等于参考值

左边指针小于右边指针，交换两个数字的位置

if (l >= r){ //不成立，不需要退出循环
    break;
}

右边指针 = 参考数字，左侧指针向左移动一位，并继续向右寻找

 if (value[l] == baseValue){
       r = r -1;
}

 if (value[r] == baseValue){
       l = l + 1;
}

找到 数字8

if (l >= r){ // 条件不成立
    break;
}

左边指针小于右边指针，交换两个数字的位置

此时，左边指针的值 = 参考值 右边指针向左移动一位，并且继续向左移动，直到寻找到小于或者等于参考值的数

这里外层循环while(l<r)成立，继续循环

找到数字4

if (l >= r){ // 条件不成立
    break;
}

左边指针小于右边指针，交换两个数字的位置

此时，右边指针的值 = 参考值，左侧指针向右移动，寻找大于或者等于参考值的数

找到数字7

if (l >= r){
   break;
}

两边指针相同 ，需要将左边指针向右移动一位，将右边指针向左移动一位

若左侧索引小于右边指针，则确定排序范围是（左侧索引，右边指针）----------------------------->也就是（0,7）

若右侧索引大于左边指针，则确定排序范围（左边指针，右侧索引）------------------------->

if (l == r){
  	l = l + 1;
  	r = r - 1;
}

提示这里有递归，判断右侧索引大于左侧指针这一步还没有执行，

public void quickSort(int[] value, int left, int right){
        int l = left;
        int r = right;
        int baseValue = value[(left+right)/2];
        int temp;

        while (l < r){
            while (value[l] < baseValue){
                l = l + 1;
            }

            while (value[r] > baseValue){
                r = r - 1;
            }

            if (l >= r){
                break;
            }

            //交换
            temp = value[r];
            value[r] = value[l];
            value[l] = temp;

            if (value[l] == baseValue){
                r = r -1;
            }

            if (value[r] == baseValue){
                l = l + 1;
            }
        }

        if (l == r){
            l = l + 1;
            r = r - 1;
        }

        if (left < r){					//left:0 r:5
            quickSort(value, left, r); // ---->本次执行的是这一步
        }

        if (right > l){
            quickSort(value, l, right); // ----->这一步还没有执行
        }
    }

在（左侧索引，右边指针）这个区间里进行排序也就是（0,5）

条件成立

	......
        
while (l < r){                             
            while (value[l] < baseValue){
                l = l + 1;
            }

            while (value[r] > baseValue){
                r = r - 1;
            }

            if (l >= r){
                break;
            }

    ......

左边指针依然向右移动，只要数字比参考值小，就继续向右移动，小于或者等于参考值则停下。

右边指针依然向左移动，只要数字比参考值大，就继续向左移动，小于或者等于参考值则停下。

这里外层循环显然成立

找到数字6和数字2

左边指针小于右边指针

if (l >= r){
   break;
}-

交换位置，右边指针向左移动一位，并继续寻找

找到数字2和数字1

左指针小于右指针

交换位置，左侧指针右移一位，继续寻找

找到数字2

两边指针相同 ，需要将左边指针向右移动一位，将右边指针向左移动一位

移动之后，左指针大于右指针，停止操作。

外层while循环不成立，退出循环 while（l<r）

开始执行递归，执行未操作步骤三

当时的执行区间是（0,5）right的值是5，在上一步左边指针向后移动一位，此时left的值是2

所以未执行步骤三的区间是（2,5）

这里的外层循环显然是成立的

这里很显然我们左边指针停在数字6上面，右边指针停在3上面，交换两个数字

找到数字后的判断不成立，向下执行，交换位置
    if (l >= r){
        break;
    }

很显然下面要找的数字是 5 和 4

显然外层循环成立
    while(l<r)
找到数字后的循环判断不成立，交换位置
    if (l >= r){
         break;
     }

交换位置，这里右边指针的值 = 参考值，左指针向右移动一位

if (l >= r){	//找到数之后的判断，成立
    break;		//退出循环
}

//这里两个指针重合，左指针向右移动，右指针向左移动
if (l == r){
   l = l + 1;
   r = r - 1;
}

if (left < r){	left:2 r:3
    quickSort(value, left, r);	------>调用自身
}

if (right > l){
    quickSort(value, l, right);	------>这个暂时没有执行
}

很显然，我们这轮操作什么都没有做，就退出了循环

退出循环后的r:1, l:3

        if (left < r){		//--------left:2   r:1
            quickSort(value, left, r);
        }

        if (right > l){		//------right:3   l:3
            quickSort(value, l, right);
        }

if (right > l){
    quickSort(value, l, right); //递归执行：right：5，l:5
}

if (right > l){
    quickSort(value, l, right);//递归执行：right：7，l:7
}

if (right > l){
    quickSort(value, l, right);//递归执行：right：8，l:9
}

到此，执行完毕，执行main方法中的打印语句