C实现快速排序

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