趣讲快速排序的两种方法

趣讲快速排序的两种方法

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

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 的数据进行排序，这时候单方向比较的快速排序就明显好用很多。