Java八大排序算法之快速排序
BDplanDante 2019-08-04
一、动图演示
二、思路分析
快速排序的思想就是，选一个数作为基数（这里我选的是第一个数），大于这个基数的放到右边，小于这个基数的放到左边，等于这个基数的数可以放到左边或右边，看自己习惯，这里我是放到了左边，
一趟结束后，将基数放到中间分隔的位置，第二趟将数组从基数的位置分成两半，分割后的两个的数组继续重复以上步骤，选基数，将小数放在基数左边，将大数放到基数的右边，在分割数组，，，直到数组不能再分为止，排序结束。
例如从小到大排序:
1. 第一趟，第一个数为基数temp，设置两个指针left = 0，right = n.length，
①从right开始与基数temp比较，如果n[right]>基数temp，则right指针向前移一位，继续与基数temp比较，直到不满足n[right]>基数temp
②将n[right]赋给n[left]
③从left开始与基数temp比较，如果n[left]<=基数temp，则left指针向后移一位，继续与基数temp比较，直到不满足n[left]<=基数temp
④将n[left]赋给n[rigth]
⑤重复①-④步，直到left==right结束，将基数temp赋给n[left]
2. 第二趟，将数组从中间分隔，每个数组再进行第1步的操作，然后再将分隔后的数组进行分隔再快排，
3. 递归重复分隔快排，直到数组不能再分，也就是只剩下一个元素的时候，结束递归，排序完成
根据思路分析，第一趟的执行流程如下图所示：
三、负杂度分析
1. 时间复杂度：
最坏情况就是每一次取到的元素就是数组中最小/最大的，这种情况其实就是冒泡排序了(每一次都排好一个元素的顺序)
这种情况时间复杂度就好计算了，就是冒泡排序的时间复杂度：T[n] = n * (n-1) = n^2 + n;
最好情况下是O(nlog2n)，推导过程如下：
（递归算法的时间复杂度公式：T[n] = aT[n/b] + f(n) ）
所以平均时间复杂度为O（nlog2n）
2. 空间复杂度：
四、Java 代码如下
import java.util.Arrays;
public class quick{
public static void main(String[] args) {
int[] arr = new int[]{10,6,3,8,33,27,66,9,7,88};
f(arr,0,arr.length-1);
System.out.println(Arrays.toString(arr));
}
public static void f(int[] arr,int start,int end){
//直到start=end时结束递归
if(start<end){
int left = start;
int right = end;
int temp = arr[start];
while(left<right){
//右面的数字大于标准数时，右边的数的位置不变，指针向左移一个位置
while(left<right && arr[right]>temp){
right--;
}
//右边的数字小于或等于基本数，将右边的数放到左边
arr[left] = arr[right];
left++;
////左边的数字小于或等于标准数时，左边的数的位置不变，指针向右移一个位置
while(left<right && arr[left]<=temp){
left++;
}
//左边的数字大于基本数，将左边的数放到右边
arr[right] = arr[left];
}
//一趟循环结束，此时left=right，将基数放到这个重合的位置，
arr[left] = temp;
System.out.println(Arrays.toString(arr));
//将数组从left位置分为两半，继续递归下去进行排序
f(arr,start,left);
f(arr,left+1,end);
}
}
}
