C实现快速排序

快速排序之所以比较快，是因为相比冒泡排序，每次交换是跳跃式的。每次排序的时候设置一个基准点，将小于等于基准点的数全部放到基准点的左边，将大于等于基准点的数全部放到基准点的右边。这样在每次交换的时候就不会像冒泡排序一样只能在相邻的数之间进行交换，交换的距离就大得多了。因此总的比较和交换次数就少了，速度自然就提高了。
当然在最坏的情况下，仍可能是相邻的两个数进行了交换。因此快速排序的最差时间复杂度和冒泡排序是一样的，都是 O(N2)，它的平均时间复杂度为 O (NlogN)。

假设我们对6 1 2 7 9 3 4 5 10 8 这10个数进行排序。首先在这个序列中随便找一个数作为基准数。为了方便，就让第一个数6作为基准数。接下来，需要将这个序列中所有比基准数大的数放在6的右边，比基准数小的数放在6的左边。

方法是：分别从初始序列6 1 2 7 9 3 4 5 10 8两端开始检测。先从右往左找一个小于6的数，再从左往右找一个大于6的数，然后交换它们（必须先从右边开始找）。
初始序列： 6 1 2 7 9 3 4 5 10 8
第一次交换后的序列：6 1 2 5 9 3 4 7 10 8
第二次交换后的序列：6 1 2 5 4 3 9 7 10 8
将3与基准数6交换: 3 1 2 5 4 6 9 7 10 8(第一趟)
现在基准数6已经归位，此时我们已经将原来的序列，以6为分界点拆分成了两个序列，左边的序列是3 1 2 5 4，右边的序列是9 7 10 8。接下来按刚才的步骤分别处理这两个序列，依此递归。

C实现的代码如下：

#include <stdio.h>
#include <string.h>
//快速排序基于二分思想,平均时间复杂度O(NlogN)

//数值排序
void quick_sort_int(int *array,int start,int end){
    int i,j,t,temp;
    if(start>end)
        return;
    temp=array[start];
    i=start;
    j=end;
    while(i!=j){
        while(array[j]>=temp && i<j){//先从右往左找
            j--;
        }
        while(array[i]<=temp && i<j){//再从左往右找
            i++;
        }
        if(i<j){
            t=array[i];
            array[i]=array[j];
            array[j]=t;
        }
    }
    array[start]=array[i];
    array[i]=temp;
    quick_sort_int(array,start,i-1);//继续处理左边的
    quick_sort_int(array,i+1,end);//继续处理右边的
}

//字符串内排序
void quick_sort_char(char *array,int start,int end){
    int i,j;
    char t,temp;
    if(start>end)
        return;
    temp=array[start];
    i=start;
    j=end;
    while(i!=j){
        while(array[j]>=temp && i<j){//先从右往左找
            j--;
        }
        while(array[i]<=temp && i<j){//再从左往右找
            i++;
        }
        if(i<j){
            t=array[i];
            array[i]=array[j];
            array[j]=t;
        }
    }
    array[start]=array[i];
    array[i]=temp;
    quick_sort_char(array,start,i-1);//继续处理左边的
    quick_sort_char(array,i+1,end);//继续处理右边的
}

//字符串间排序,首字母,默认长度为10
#define STRING_LEN 10
void quick_sort_string(char (*array)[STRING_LEN],int start,int end){
    int i,j;
    char t[STRING_LEN],temp[STRING_LEN];
    if(start>end)
        return;
    strncpy(temp,array[start],STRING_LEN);
    i=start;
    j=end;
    while(i!=j){
        while(array[j][0]>=temp[0] && i<j){//先从右往左找
            j--;
        }
        while(array[i][0]<=temp[0] && i<j){//再从左往右找
            i++;
        }
        if(i<j){
            strncpy(t,array[i],STRING_LEN);
            strncpy(array[i],array[j],STRING_LEN);
            strncpy(array[j],t,STRING_LEN);
        }
    }
    strncpy(array[start],array[i],STRING_LEN);
    strncpy(array[i],temp,STRING_LEN);
    quick_sort_string(array,start,i-1);//继续处理左边的
    quick_sort_string(array,i+1,end);//继续处理右边的
}

测试用例：

int main(void){
    int j=0;
    int i[5]={1,3,4,2,5};
    char array1[20] = "mrbluyee";
    char array2[20][STRING_LEN] = {"7","13","4","246","35"};
    
    quick_sort_int(i,0,4);
    for(j=0;j<5;j++){
        printf("%d ",i[j]);
    }
    printf("\n");
    
    quick_sort_char(array1,0,strlen(array1)-1);
    printf("%s",array1);
    printf("\n");
    
    quick_sort_string(array2,0,4);
    for(j=0;j<5;j++){
        printf("%s",array2[j]);
        printf("\n");
    }
    printf("\n");
    return 0;
}

运行结果显示如下：

1 2 3 4 5 
beelmruy
13
246
35
4
7