一遍掌握，快速排序的入门理解

àì夳堔傛蜴生んèń 2024-04-01 16:45 29阅读 0赞

## 前言 ##

快速排序，是一种常用的排序算法，  
因其易于理解且时间复杂度较低的特性而备受程序员青睐。  
平均复杂度为o（n lgn）。许多编程语言都有内置（优化过）的快速排序算法，例如java、c++等。  
虽然日常开发中，我们可以直接调用这些内置函数。但是，快速排序因其重要地位，我们仍然有必要掌握好。

## 原理分析 ##

快速排序的基本原理，是分段进行排序。

快速排序需要从排序的数组中选中一个key值，或者说基准值。

每一次进行排序，都会根据选择的key值（通常是排序数组开头的值，即下面的begin）将数组根据元素大小切成左边数组和右边数组两部分。

这个切开的过程，常见的实现方式是使用双指针（例如begin表示左指针，end表示右指针）。

我们让begin从头开始遍历，找到一个大于key值的数字后停下。而end从尾部开始遍历，找到一个小于key值的位置后停下。然后把两个指针索引的数字交换。

**双指针的遍历要注意顺序问题，默认情况我们选取的参考值key是数组索引0的数字，那么逻辑上就应该先让end指针向前遍历，这样才能确保左边数组一定都小于key值。否则，begin指针将会在一个大于key值的位置停下，这个数会与key交换，但是显然也被归到了左边数组**

如此反复，直至两个指针相遇，然后让key值与begin或end交换（begin此时等于end，因此哪个都一样），此时交换也就结束了。

大于key值的数字都被换到了右边，小于key值的数字则都换到了左边。

切开的两部分，左边的子数组都是小于key值的数，右边则都是大于key值的数。这样一来，右边数组里的任一个数都会大于从左边数组里拿出的任一个数。

两个数组的相对大小确定之后，显然，我们发现，接下来只需要分别对左数组和右数组分别排序，拼起来就能得到一个排好序的数组，也就是我们的目的。

这样一来，我们可以发散思维,如果我们继续对子数组应用这种排序，不断的切开数组，那么最终子数组内部的元素个数就会变为1（即每一个元素都被正确的排序），排序也就结束了。

## 案例分析 ##

例如：有一个数组\{3，6，7，4，2，5，1\}，我们尝试来手动模拟一下快速排序的过程。  
数组长度为7.  
首先我们选择3作为key值，begin从索引0开始向后遍历，end从索引6开始前遍历。  
过程如下：  
1）begin=1，end=6，满足交换条件。将6与1交换  
……  
2）begin=2，end=4，满足交换条件，将7与2交换  
……  
3）begin=2，end=2,将begin与key交换，即1与3交换  
4）结束  
此时左边数组为\{2，1，3\}，右边数组为\{4，7，5，6\}。

右边的任意元素都大于左边任一元素。

接下来可以分别对两个子数组进行重复的操作，最后即能得到排好序的数组。

## 参考代码 ##

以下是使用java实现的参考代码：

public void sort(int[] array,int begin,int end){
        
            int len=end-begin+1;
            //长度大于1时才排序
            if(len>1) {
        
                int pos = cut(array, begin,end);
                sort(array, begin, pos - 1);
                sort(array, pos + 1, end);
            }
        }
        public int cut(int[] array,int begin,int end){
        
            int key=begin;//划分值
            while(begin<end){
        
                //后端中找到一个小于key位置的值
                while(begin<end && array[end]>=array[key]){
        
                    --end;
                }
                //前段中找到一个大于key位置的值
                while(begin<end && array[begin]<=array[key]){
        
                    ++begin;
                }
                if(begin<end){
        
                    swap(array,begin,end);
                }
            }
            //左右指针相遇位置与key交换
            swap(array,begin,key);
            return begin;
        }
        public void swap(int[] array,int v1,int v2){
        
            //交换两个变量的值
            array[v1]=array[v1]+array[v2];
            array[v2]=array[v1]-array[v2];
            array[v1]=array[v1]-array[v2];
        }