简单算法之快速排序

缺乏、安全感 2023-10-09 15:38 35阅读 0赞

#### 快速排序 ####

###### 算法介绍 ######

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序 n 个项目要 Ο(nlogn) 次比较。在最坏状况下则需要 Ο(n2) 次比较，但这种状况并不常见。事实上，快速排序通常明显比其他 Ο(nlogn) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。

快速排序使用分治法（Divide and conquer）策略来把一个串行（list）分为两个子串行（sub-lists）。

快速排序又是一种分而治之思想在排序算法上的典型应用。本质上来看，快速排序应该算是在冒泡排序基础上的递归分治法。

###### 排序动态图 ######

![在这里插入图片描述][0231ccf3e8f9488c84e6485c2911750e.gif_pic_center]

###### 算法原理 ######

取出第一个数的下标做为左下标（left），左下标上的数为基准数（base），取出最后一个数为右下标（right），从右right开始判断它上面的数是否有base小，right自减，直到找到比base小的数为止，然后开始从左边算，left自增，直到找到比base大的数，找到之后交换他们两个数的位置，循环此操作，直到left=right，然后将base 与 left（或right任意一个）交换值，这样base就是到了他该到的位置上，base从中间隔开把这个数组分隔成了两段，然后使用将递归继续传入参数执行以上操作。

###### 代码块 ######

public class QuickSort {
        
        public static void main(String[] args) {
        
            int[] arr = {
        5,1,4,2,3,9,6,8,7};
            quickSort(arr,0,arr.length-1);
            System.out.println(Arrays.toString(arr));
        }
    
        public static void quickSort(int[] arr,int left,int right){
        
            //保存左下标和右下标，以便递归调用
            int start = left;
            int end = right;
            //递归结束条件
            if(left>right){
        
                return;
            }
            //保存基准数
            int base = arr[left];
            while (left<right){
        
                //找到比基准数小的数的下标
                while (left<right){
        
                    if(arr[right] < base)break;
                    right--;
                }
                //找到比基准数大的数的下标
                while (left<right){
        
                    if(arr[left] > base)break;
                    left++;
                }
                //交换它们的值
                int temp = arr[left];
                arr[left] = arr[right];
                arr[right] = temp;
            }
            //交换基准数与left（或right）下标的值
            int temp = arr[start];
            arr[start] = arr[left];
            arr[left] = temp;
            //递归循环
            quickSort(arr, start, left-1);
            quickSort(arr, left+1, end);
        }
    }

###### 运行结果 ######

![在这里插入图片描述][d8878e5f8efb494cbb85b501de92a15f.png_pic_center]

[0231ccf3e8f9488c84e6485c2911750e.gif_pic_center]: https://img-blog.csdnimg.cn/0231ccf3e8f9488c84e6485c2911750e.gif#pic_center
[d8878e5f8efb494cbb85b501de92a15f.png_pic_center]: https://img-blog.csdnimg.cn/d8878e5f8efb494cbb85b501de92a15f.png#pic_center