趣讲快速排序的两种方法

趣讲快速排序的两种方法

快速排序有很多方法，今天我们来讲讲其中的两种方法，一种是通过单方向比较实现的快速排序，另一种是利用双方向比较。这两种方法只是划分元素的方法不同。他们的递归部分是相同的。

void quick_sort_2( int arr[], int start, int end ){
    if(end < start){
        return;
    }
    int arrange_index = arrange(arr,start,end);
    
    quick_sort_2(arr,start,arrange_index-1);
    quick_sort_2(arr,arrange_index+1,end);
}

下面来看看这两种快速排序~

一、单方向比较快速排序

顾名思义，就是从一个方向开始进行比较，中途不需要更换比较的方向。

我们需要给函数设置三个参数，一个是要划分的数组，一个是开始元素下标，另一个是结束元素下标。先来看一看代码，我再讲述吧~

int arrange(int arr[],int start, int end){
    int index = start;
    for(int i=start;i<end;i++){
        if(arr[i]<arr[end]){
            if(index!=i){
                swap(&arr[i],&arr[index]);
            }
            index++;
        }
    }
    if(end!=index){
        swap(&arr[end],&arr[index]);
    }
    return index;
} 

我们将数组的最后一个元素arr[end]设置为用来划分的元素。

然后我们设置一个index变量，这个变量可以看作是用来区分比用来划分的元素arr[end]小的元素，在它之前的就是比用来划分的元素arr[end]小的。然后设置一个for循环，将初值设置为要划分的部分起始下标，一直到要划分的末尾下标结束。这样做是为了让每一个元素都能和用来划分的元素arr[end]比较。如果这个元素比arr[end]小，并且这个index不等于当前的i值，就将arr[i]与arr[index]进行交换，如果不比较i和index，就可能出现自己和自己交换的情况，在一些情况下出现减慢运行速度的情况。如果这个arr[i]小于arr[end]，那么就可以将index加一了，因为要么index与i相同，这个arr[i]是确定比用来划分的元素小，要么不相同，然后进行交换，交换过来的已经比用来划分的元素arr[end]小。

然后将这个用来划分的元素arr[end]与arr[index]交换，因为一般情况下这个arr[index]是比arr[end]大的。这里判断end是否等于index也是为了避免出现自己和自己交换的情况。

二、双方向比较快速排序

双方向的快速排序只是和单方向的划分策略不一致，思想大抵是相同的。

int arrange(int arr[], int start, int end){
    int x = arr[start];
    while(start<end){
        while(start<end && arr[end]>=x){
            end--;
        }
        arr[start] = arr[end];
        while(start<end && arr[start]<=x){
            start++;
        }
        arr[end] = arr[start];
    }
    if(start == end){
        arr[start] = x;
    }
    return start;
}

它是使用start和end将数组中的这些元素分成三部分，start前面的部分全是小于等于划分元素x的元素，而end后面的部分全是大于等于划分元素x的元素，在这中间是没有进行区分的元素。当start小于end，也就是划分没有结束时，就一直划分，直到start>=end，与此同时，先让end从右往左遍历，如果遇到比x小的值就停止，然后将其交给start，之后又让start从左往右遍历，直到遇到比x大的值才停止，然后将其交给end，这个end上的值之前已经给到先前的start位置上了。然后start的坐标与end的坐标重合了，这时将之前保存的要划分的元素x放置于此。然后返回这个要划分的元素索引值。

比较两种算法

他俩的时间复杂度是一样的，似乎看起来没什么区别。但是在实际应用中，这两种区别就比较大了，比如如果要给一个1TB的数据进行排序，这时候单方向比较的快速排序就明显好用很多。