快排C语言实现

• 快排的主要思想就是把一组数分成两组，左边那一组的最大数都比右边的最小数小，然后再对左边那一组数进行相同操作，再对右边的数进行相同操作。直到这一组数变成一个数单独成组，排序完成。
• 比如 3 5 9 -8 5 4
  在第一次分组时变成 第一组{-8} 标准值3 第二组{5 9 5 4} 这里标准值就使该组的第一个数，此时第一组的所有数小于标准值小于第二组的所有数。那么再对第一组和第二组的所有数进行相同操作则排序成功。代码如下：
• 第一种

void sort(int * a, int len) {
if(len <= 1) return; //数组长度等于一或者等于零的时候，不必排序
//a为每一组的第一个元素的地址，len为每一组的长度
    int i=0. j=len-1, temp=a[0];//初始化i指向数组开头，初始化j指向数组结尾，temp为标准值
    while(i<j) {//只要i，j不相遇，就一直扫描
        while(a[j] > temp) j--; a[i] = a[j];
        //后面的数只要大于前面的数就不管，往前扫描，直到小于或等于标准值的时候，把a[j]赋值给前面的a[i]
        //注意，此时a[j]有两份而a[i]原来的值被覆盖，且a[j]是没有用的，因为它小于标准值，它应该在前面a[i]的位置
        while(a[i] <= temp) i++; a[j] = a[i];
        //前面的数小于等于标准值就继续扫描
        //注意此时在上面的那一份多余a[j]被替换掉了，但是多了一份a[i]，它大于标准值，它应该此刻j对应的位置.
        //这个循环又会走到上面消去这个无用的a[i]。
    }
    //执行完上面这个循环，在i的位置上会多一个无用的a[i]，因为最后一次多余的a[i]不会被替换掉
    //而且可以发现在进入循环时，无端消去了一个并不是多余的a[i]，因为是第一次的时候，所以是a[0]。
    //而temp=a[0]，并且可以发现a[i]前面的数必定小于temp，a[i]后面的数必定大于temp,所以可以令a[i] = temp，这样数组的元素就没有变化，并且完成了把数分成两组;
    a[i] = temp;
    //对前一组，后一组 数分别继续进行这种操作
    sort(a, i);//0~i-1长度为i
    sort(a+i+1, len-i-1);
    
    return;
}

• 第二种：

void sort(int * a, int len) {
    if( len <= 1 ) return;

    int i=0, j=len-1, temp = a[0], t;
    while( i<j ) {
        while( a[j]>temp && j>i ) j--;
        while( a[i]<=temp && i<j ) i++;
        if(i != j) { //i等于j时交换没有意义,否则使小数到前面，大数到后面 
            t = a[i];
            a[i]=a[j];
            a[j]=a[i];
        } 
    }
    //由于是先从后面往前扫描，所以无论何时，从后往前扫描停止时，当时的a[j]必定不大于temp,则退出时a[i]必定不大于temp
    //使标准值到中间形成 小数数组 标准值 大数数组 
    a[0]=a[i];
    a[i]=temp;
    sort(a, i);
    sort(a+i+1, len-i-1);

    return;
}

• 测试程序：

#include<stdio.h>

void sort(int * a, int len) {
    if( len <= 1 ) return;

    int i=0, j=len-1, t, temp = a[0];
    while( i<j ) {
        while( a[j]>temp && j>i ) j--; a[i] = a[j];
        while( a[i]<=temp && i<j ) i++; a[j] = a[i];
    }
    a[i] = temp;
    sort(a, i);
    sort(a+i+1, len-i-1);

    return;
}

int main(void) {
    int i, a[13] = {-100, 4, 6, -10, 9, 46, -4, 3, 6, 5, 8, 44, 20};
    sort(a, 13);
    for(i=0; i<13; i++) {
        printf("%d ", a[i]);
    }

    return 0;
}

• 如果有错误或者可以改进的地方，欢迎指出