【数据结构与算法之排序与查找】快速排序

「爱情、让人受尽委屈。」 2024-03-25 16:38 75阅读 0赞

#### 【数据结构与算法之排序与查找】快速排序 ####

#### 文章目录 ####

*   *   *  【数据结构与算法之排序与查找】快速排序

快速排序是冒泡排序的一种改进，元素间比较的次数较少，排序效率较高。

【基本思想】通过一趟排序将待排序序列分割为前后两部分，其中一部分序列中的数据比另一部分序列中的数据小，然后使用同样的方法分别对两部分数据排序，直到整个序列有序。

【假设】假设待排序的序列为  ( k 1 , k 2 , . . . , k n ) (k\_1,k\_2,...,k\_n) (k1,k2,...,kn) ，首先从序列中任取一个元素，作为基准元素，然后将小于等于基准元素的所有元素都移到基准元素前面，把大于基准元素的所有元素都移到基准元素的后面，基准元素不属于任何子序列，它的位置就是该元素在序列中的最终位置，这个过程就称为一趟快排，或快排的一次划分。

举个栗子：

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

注意：快速排序一般适用于顺序表或数组序列的排序，不适合在链表结构上排序。

Java 实现代码：

public static void quickSort(int[] array, int s, int t) {
         // s和t 为当前待排序的子序列的首尾元素在数组array 中的下标
        int low, high;
        if (s < t) {
        
            low = s;
            high = t + 1;
    
            while (true) {
        
                // array[s] 为基准元素
                do low++;
                while (array[low] <= array[s] && low != t);
                do high--;
                while (array[high] >= array[s] && high != s);
    
                if (low < high) {
        
    
                    // 交换array[low] 和 array[high]
                    swap(array, low, high);
                } else {
        
                    break;
                }
            }
    
            swap(array, s, high); // 将基准元素与array[high] 交换
            quickSort(array, s, high - 1);
            quickSort(array, high + 1, t);
        }
    
    }
    
    public static void swap(int[] array, int low, int high) {
        
        int tmp = array[low];
        array[low] = array[high];
        array[high] = tmp;
    }

测试

public static void main(String[] args) {
        
    
        int[] array = {
        3, 12, 20, 1, 0, 5, 8, 19, 5};
        quickSort(array, 0, 8);
    
        for (int e : array) {
        
            System.out.print(e + " ");
        }
    
    }

运行结果

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

[c9afe858ff984c8fb462165781847df4.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/99062add130b4e3c95860e67cc66a732.png
[f067160dc89c4fe8a4e0727441f01382.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/0a7883cdc3a249aabc6bccd9155d35d1.png