Java算法：快速排序

我就是我 2024-02-19 08:48 12阅读 0赞

#### 一、快速排序 ####

快速排序算法是对**冒泡排序**算法的一种改进算法，在当前所有内部排序算法中，快速排序算法被认为是最好的排序算法之一。

基本思想：通过一趟排序将待排记录分隔成独立的左右两部分，左边的子序列中所有数据都比右边子序列中的数据小，然后对左右两个子序列继续进行排序，直到整个序列有序。

快速排序使用**分而治之 divide and conquer（D&C）**法来把一个串（list）分为两个子串（sub-lists）

#### 二、快速排序步骤 ####

> 1.  从数组中按照一定的规则选择一个元素作为基准值
> 2.  把基准值与其他元素进行比较，将元素分成两部分，把所有比基准值小的值放在左侧，所有比基准值大的放在右侧。即进行区域划分
> 3.  通过递归上述操作，再次将左右两区域进行区域划分，完成排序.

#### 三、java实现快速排序 ####

public static void main(String[] args) {
            //调用数据
            Integer[] datas =getData();
            System.out.println("排序前的数组："+Arrays.toString(datas));
            sort(datas, 0, datas.length-1);
            System.out.println("排序后的数组："+ Arrays.toString(datas));
    
        }
    
    
    
        /**
         * （1） 生成1-100范围的随机数10个
         */
        private static Integer[] getData() {
            Set<Integer> sets = new HashSet<>();
            Random random = new Random();
            while (true) {
                //生成1-100的随机数
                int ran = random.nextInt(100) + 1;
                //添加
                sets.add(ran);
                //判断生成10个数据
                if (sets.size() >= 10) {
                    break;
                }
            }
            // 将Set转换成数组
            Integer[] arr = sets.toArray(new Integer[sets.size()]);
            return arr;
        }
    
        /**
         * @param arrs   数组无序
         * @param before （子）序列最前面的索引
         * @param after  （子）序列最后面的索引
         */
        public static void sort(Integer[] arrs, int before, int after) {
            int left = before; //左边
            int right = after; //右边
            int key = arrs[before]; //基准值
            //循环比较
            while (right > left) {
                //(1)从后往前比较
                while (right > left && arrs[right] >= key)  //如果没有比关键值小的，比较下一个，直到有比关键值小的交换位置，然后又从前往后比较
                    right--;
                //判断有比关键值小的交换位置
                if (arrs[right] <= key) {
                    int temp = arrs[right];
                    arrs[right] = arrs[left];
                    arrs[left] = temp;
                }
                //(2)从前往后比较
                while (right > left && arrs[left] <= key)//如果没有比关键值大的，比较下一个，直到有比关键值大的交换位置
                    left++;
                //判断有比关键值大的交换位置
                if (arrs[left] >= key) {
                    int temp = arrs[left];
                    arrs[left] = arrs[right];
                    arrs[right] = temp;
                }
            }
            // 此时第一次循环比较结束，关键值的位置已经确定了。
            // 左边的值都比关键值小，右边的值都比关键值大，
            // 但是两边的顺序还有可能是不一样的，进行下面的递归调用
            //递归关键值左右二边的子序列
            if (left > before) {
                //递归左边子序列
                sort(arrs, before, left - 1);
    
            }
            if (right < after) {
                //递归右边子序列
                sort(arrs, right + 1, after);
            }
        }
    }

![a5d9f9470da94292a7249dc421f247b0.png][]

#### 四、性能分析 ####

**优点：**效率高，时间复杂度平均为O(nlogn)，快速排序是最快的排序算法，耗费的资源少，最佳情况下，空间复杂度为O(logn)，每一次都平分数组的情况，代码较为简单。

**缺点**：不稳定，初始序列有序或基本有序时，时间复杂度降为O(n^2)。

[a5d9f9470da94292a7249dc421f247b0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/19/6cd79c7bbe814804ae52b81209d555f2.png