算法基础：快排优化：为什么快排都会TLE

本是古典何须时尚 2022-11-21 11:28 280阅读 0赞

在算法训练中，快排应该是基础中的基础了，直接使用前面介绍的快排，无论是单向循环还是双向循环方式，在特定的数据序列下，都有可能出现TLE（Time Limit Exceeded）超时，这篇文章对原因和基准值的优化进行验证和总结。

### 目录 ###

*  快排的效率的情况
 *  基准值选择优化
 *  双向循环 vs 单向循环
 *   *  方式1: 折半方式
     *  方式2: 随机方式
     *  折半方式 vs 随机方式
 *  总结
 *  附录
 *   *  附录1:缺省单向循环方式
     *  附录2: 缺省的双向循环方式
     *  附录3: 基准值折半方式的双向循环方式
     *  附录4: 基准值随机方式的双向循环方式

--------------------

# 快排的效率的情况 #

> 快排本身不是一种稳定的算法，在前面的文章中也提到过，缺省的实现中一般直接选取最左或者最右进行，而这种方式之下，如果待排序的序列是已经有序的情况之下，快排的效率直接会恶化到N平方的时间复杂度，相当于排序核心的基准值分割算法几乎没有能起到作用，所以这种情况下出现超时也就可以理解了。这种情况之下，最简单的方式就是首先进行如下基准值选择的优化，这种情况就可以直接解决本身已经有序的大量带排序的算法的排序问题。

--------------------

# 基准值选择优化 #

基准值最为简单的优化方式是可以不改变之前的逻辑，在进行排序之前首先按照某种方式选取一个，放至基准值选取的位置，与之进行交换，相当于打个补丁，之前的代码几乎不必修改。

--------------------

# 双向循环 vs 单向循环 #

使用前文给出的实现示例的情况下，单向循环较为简略，在大量数据的情况下，前者的替换效率整体一般会高一些，但有时也不一定，对于不同的测试用例，单跑一次的效果可能也会不同，可以多试，测测人品。

*  缺省的单向循环  
    参看附录1的示例代码，执行时对于有序数列的效率如下所示，可以看到对于10万个有序数列，时间消耗已经达到10s级别的程度了

100
    Time Used: 0.000014s
    10000
    Time Used: 0.105468s
    100000
    Time Used: 10.499863s

*  缺省的双向循环  
    参看附录2的示例代码，对于10万有序数列，不做任何操作也已经到10s级别了

100
    Time Used: 0.000019s
    10000
    Time Used: 0.130322s
    100000
    Time Used: 12.846300s

--------------------

## 方式1: 折半方式 ##

选取待排序列的左右的中间值作为基准点，比如示例代码可能如下

int key = (left+right)/2;
        int tmp=arr[left]; arr[left]=arr[key]; arr[key]=tmp;

使用附录3示例代码，运行结果如下所示，可以看到提升2个数量级到千万级别的有序序列，运行时间也仍然在毫秒级别0.665毫秒：

100
    Time Used: 0.000005s
    10000
    Time Used: 0.000442s
    100000
    Time Used: 0.005531s
    1000000
    Time Used: 0.059314s
    10000000
    Time Used: 0.665215s

## 方式2: 随机方式 ##

选取待排序列的左右的中间值作为基准点，比如示例代码可能如下

int key = rand()%(right - left) + left;
        int tmp=arr[left]; arr[left]=arr[key]; arr[key]=tmp;

使用附录4的示例代码，执行结果如下所示

100
    Time Used: 0.000015s
    10000
    Time Used: 0.000635s
    100000
    Time Used: 0.007567s
    1000000
    Time Used: 0.082657s
    10000000
    Time Used: 1.008981s

--------------------

## 折半方式 vs 随机方式 ##

一般来说，平均而言随机方式比折半方式效果要好一点。当然针对本文示例中已经完全有序的情况，显然折半方式更加接近于标准答案，但是不同的测试用例，平均效果而言，应该来说随机方式还是有其优势的，不过对于应试这种无聊的思路而言，果断换效果比较好的方式就可以了。

--------------------

# 总结 #

使用双向循环+基准值的优化+平台整体优化选项的使用，一般来说可以解决TLE的问题

--------------------

# 附录 #

## 附录1:缺省单向循环方式 ##

#include <stdio.h>
    #include <string.h>
    #include <stdlib.h>
    #include <time.h>
    
    int partition(int* arr, int start, int end) { 
        if (start >= end ) return end;
    
        int pivot = arr[start];
        int index = start;
        for (int i=start+1; i<=end; i++) { 
            if (arr[i] <= pivot) { 
                index++;
                int tmp=arr[i]; arr[i]=arr[index]; arr[index]=tmp;
            }
        }
        arr[start]=arr[index];
        arr[index]=pivot;
    
        return index;
    }
    
    void quick_sort(int* arr, int start, int end){ 
        if (start >= end) return;
        int pivot_index = partition(arr,start,end);
        quick_sort(arr,start,pivot_index-1);
        quick_sort(arr,pivot_index+1,end);
    }
    
    int main() { 
        int n = 0;
        while (scanf("%d",&n) != EOF) { 
            int* array = (int *)malloc(sizeof(int)*n);
            memset(array,0,sizeof(int)*n);
            for (int i=0; i<n; i++) array[i]=i+1;
            time_t start_time, end_time;
            start_time=clock();
            quick_sort(array,0,n-1);
            end_time=clock();
            printf("Time Used: %fs\n",(double)(end_time-start_time)/CLOCKS_PER_SEC);
            free(array); array= NULL;
        }
    }

## 附录2: 缺省的双向循环方式 ##

#include <stdio.h>
    #include <string.h>
    #include <stdlib.h>
    #include <time.h>
    
    int partition(int* arr, int start, int end) { 
        int left=start, right=end;
        if (left >= right ) return right;
    
        int pivot = arr[left];
        while (left != right) { 
            while (left < right && arr[right] > pivot) right--;
            while (left < right && arr[left] <= pivot) left++;
            if (left < right) { 
                int tmp = arr[left]; arr[left]=arr[right]; arr[right]=tmp;
            }
        }
        arr[start]=arr[left];
        arr[left]=pivot;
    
        return right;
    }
    
    void quick_sort(int* arr, int start, int end){ 
        if (start >= end) return;
        int pivot_index = partition(arr,start,end);
        quick_sort(arr,start,pivot_index-1);
        quick_sort(arr,pivot_index+1,end);
    }
    
    int main() { 
        int n = 0;
        while (scanf("%d",&n) != EOF) { 
            int* array = (int *)malloc(sizeof(int)*n);
            memset(array,0,sizeof(int)*n);
            for (int i=0; i<n; i++) array[i]=i+1;
            time_t start_time, end_time;
            start_time=clock();
            quick_sort(array,0,n-1);
            end_time=clock();
            printf("Time Used: %fs\n",(double)(end_time-start_time)/CLOCKS_PER_SEC);
            free(array); array= NULL;
        }
    }

## 附录3: 基准值折半方式的双向循环方式 ##

#include <stdio.h>
    #include <string.h>
    #include <stdlib.h>
    #include <time.h>
    
    int partition(int* arr, int start, int end) { 
        int left=start, right=end;
        if (left >= right ) return right;
    
        int key = (left+right)/2;
        int tmp=arr[left]; arr[left]=arr[key]; arr[key]=tmp;
        
        int pivot = arr[left];
        while (left != right) { 
            while (left < right && arr[right] > pivot) right--;
            while (left < right && arr[left] <= pivot) left++;
            if (left < right) { 
                int tmp = arr[left]; arr[left]=arr[right]; arr[right]=tmp;
            }
        }
        arr[start]=arr[left];
        arr[left]=pivot;
    
        return right;
    }
    
    void quick_sort(int* arr, int start, int end){ 
        if (start >= end) return;
        int pivot_index = partition(arr,start,end);
        quick_sort(arr,start,pivot_index-1);
        quick_sort(arr,pivot_index+1,end);
    }
    
    int main() { 
        int n = 0;
        while (scanf("%d",&n) != EOF) { 
            int* array = (int *)malloc(sizeof(int)*n);
            memset(array,0,sizeof(int)*n);
            for (int i=0; i<n; i++) array[i]=i+1;
            time_t start_time, end_time;
            start_time=clock();
            quick_sort(array,0,n-1);
            end_time=clock();
            printf("Time Used: %fs\n",(double)(end_time-start_time)/CLOCKS_PER_SEC);
            free(array); array= NULL;
        }
    }

## 附录4: 基准值随机方式的双向循环方式 ##

#include <stdio.h>
    #include <string.h>
    #include <stdlib.h>
    #include <time.h>
    
    int partition(int* arr, int start, int end) { 
        int left=start, right=end;
        if (left >= right ) return right;
    
        int key = rand()%(right - left) + left;
        int tmp=arr[left]; arr[left]=arr[key]; arr[key]=tmp;
    
        int pivot = arr[left];
        while (left != right) { 
            while (left < right && arr[right] > pivot) right--;
            while (left < right && arr[left] <= pivot) left++;
            if (left < right) { 
                int tmp = arr[left]; arr[left]=arr[right]; arr[right]=tmp;
            }
        }
        arr[start]=arr[left];
        arr[left]=pivot;
    
        return right;
    }
    
    void quick_sort(int* arr, int start, int end){ 
        if (start >= end) return;
        int pivot_index = partition(arr,start,end);
        quick_sort(arr,start,pivot_index-1);
        quick_sort(arr,pivot_index+1,end);
    }
    
    int main() { 
        int n = 0;
        while (scanf("%d",&n) != EOF) { 
            int* array = (int *)malloc(sizeof(int)*n);
            memset(array,0,sizeof(int)*n);
            for (int i=0; i<n; i++) array[i]=i+1;
            time_t start_time, end_time;
            start_time=clock();
            quick_sort(array,0,n-1);
            end_time=clock();
            printf("Time Used: %fs\n",(double)(end_time-start_time)/CLOCKS_PER_SEC);
            free(array); array= NULL;
        }
    }