Java八大排序算法之快速排序

BDplanDante 2019-08-04

一、动图演示

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

相关推荐