八大排序算法——快速排序(动图演示 思路分析 实例代码Java 复杂度分析)

时间:2023-12-20 17:07:38

一、动图演示

八大排序算法——快速排序(动图演示  思路分析  实例代码Java  复杂度分析)

二、思路分析

快速排序的思想就是,选一个数作为基数(这里我选的是第一个数),大于这个基数的放到右边,小于这个基数的放到左边,等于这个基数的数可以放到左边或右边,看自己习惯,这里我是放到了左边,

一趟结束后,将基数放到中间分隔的位置,第二趟将数组从基数的位置分成两半,分割后的两个的数组继续重复以上步骤,选基数,将小数放在基数左边,将大数放到基数的右边,在分割数组,,,直到数组不能再分为止,排序结束。

例如从小到大排序:

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.  递归重复分隔快排,直到数组不能再分,也就是只剩下一个元素的时候,结束递归,排序完成

根据思路分析,第一趟的执行流程如下图所示:

八大排序算法——快速排序(动图演示  思路分析  实例代码Java  复杂度分析)

三、负杂度分析

1.  时间复杂度:

最坏情况就是每一次取到的元素就是数组中最小/最大的,这种情况其实就是冒泡排序了(每一次都排好一个元素的顺序)

这种情况时间复杂度就好计算了,就是冒泡排序的时间复杂度:T[n] = n * (n-1) = n^2 + n;

最好情况下是O(nlog2n),推导过程如下:

递归算法的时间复杂度公式:T[n] = aT[n/b] + f(n) 

八大排序算法——快速排序(动图演示  思路分析  实例代码Java  复杂度分析)

所以平均时间复杂度为O(nlog2n)

2.  空间复杂度:

  快速排序使用的空间是O(1)的,也就是个常数级;而真正消耗空间的就是递归调用了,因为每次递归就要保持一些数据:
  最优的情况下空间复杂度为:O(log2n);每一次都平分数组的情况
  最差的情况下空间复杂度为:O( n );退化为冒泡排序的情况
所以平均空间复杂度为O(log2n)

 四、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);
}
}
}