快速排序及其代码实现

柔情只为你懂 2023-10-13 14:07 39阅读 0赞

#### 快速排序及其代码实现 ####

*  快速排序的定义
 *  快速排序是不稳定的
 *  快速排序的平均时间复杂度
 *  快速排序的代码实现

## 快速排序的定义 ##

快速排序是一种常用的排序算法，使用分治法的思想。

它的基本思想是选取一个基准元素，将数组分割成两个子数组，其中一个子数组的所有元素小于基准元素，另一个子数组的所有元素大于基准元素。

然后，对这两个子数组分别进行递归地快速排序，最后将排好序的子数组合并起来，即可得到一个有序的数组。

## 快速排序是不稳定的 ##

稳定的排序算法是指具有相同键值的元素在排序前后的相对位置不变，而快速排序在交换元素的过程中可能会改变相同键值元素的相对顺序。

## 快速排序的平均时间复杂度 ##

快速排序的平均时间复杂度为O(nlogn)。

在最好情况下，即每次选择的基准元素恰好将数组分成两个大小相等的子数组时，快速排序的时间复杂度为O(nlogn)。

但在最坏情况下，即每次选择的基准元素都是数组中的最小或最大元素，快速排序的时间复杂度为O(n^2)。

然而，通过一些优化技巧（如随机选择基准元素），可以减少最坏情况的出现概率。

## 快速排序的代码实现 ##

public class QuickSort {
        
        public static void quickSort(int[] array, int low, int high){
        
            if(low < high){
        
                int pivotIndex = partition(array, low, high); // 获取基准元素的索引
                quickSort(array, low, pivotIndex - 1); // 对基准元素左边的子数组进行快速排序
                quickSort(array, pivotIndex + 1, high); // 对基准元素右边的子数组进行快速排序
            }
        }
    
        private static int partition(int[] array, int low, int high){
        
            int pivot = array[high]; // 选择最后一个元素作为基准元素
            int i = low - 1;
    
            for(int j = low; j < high; j++){
        
                if(array[j] < pivot){
        
                    i++;
                    swap(array, i, j); // 将小于基准元素的元素交换到左侧
                }
            }
    
            swap(array, i + 1, high); // 将基准元素放到合适的位置
            return i + 1; // 返回基准元素的索引
        }
    
        private static void swap(int[] array, int i, int j){
        
            int temp = array[i];
            array[i] = array[j];
            array[j] = temp;
        }
    
        public static void main(String[] args) {
        
            int[] array = {
        5, 2, 9, 1, 7, 6, 3};
            quickSort(array, 0, array.length - 1);
    
            System.out.println("Sorted array: ");
            for(int num : array){
        
                System.out.print(num + " ");
            }
        }
    }

这是一个基本的快速排序实现，通过递归调用quickSort方法对子数组进行排序，而partition方法用于确定基准元素的位置，并进行元素的交换。最后，通过打印数组元素，可以验证排序结果。