Quick sort 算法小结

Quick sort 主要利用分治的思想来进行排序。首先从这个序列中选取一个元素作为分界点（pivot），然后将序列分成两个子序列，左边序列元素值都小于分界点的值，右边序列的元素值都大于分界点的值。然后利用递归的思想，分别对两个子序列再进行排序。

具体的步骤：
step 1：从序列中选取一个元素作为分界点（pivot）
step 2：将原始序列序列分成两部分，并且满足 a.左边序列元素值都小于分界点的值 b.右边序列的元素值都大于分界点的值。这一步叫做分区（partition）操作。
step 3 ：对得到的子序列，递归调用上面的步骤进行划分，直到子序列的长度为1，则结束。

具体的步骤就是这样，但是由于第一步中选取分界点的方法的不同，也有几个不同的版本的版本。
先详解一下最简单的版本：就是直接选取中间的的
例子：
A = ( 38  81  22  48  13  69  93  14  45  58  79  72)
取[(left+ringht)/2]处的元素作为分界点（pivot）的值。具体分区的过程如下图：

得到两个子序列，然后对两个子序列进行同样的操作。

代码实现：
#include
#include


static void swap(void *x, void *y, size_t l) {
   char *a = (char *)x, *b = (char*)y, c;
   while(l--) {
      c = *a;
      *a++ = *b;
      *b++ = c;
   }
}

//考虑边界问题，当r==l时，也需要判别一下这个值是否小于分界值

void quicksort(int *num_list,int begin,int end)
{
    if(begin         int pivot=*(num_list+(begin+end)/2);
        int l=begin,r=end;
       // printf("%d\n",pivot);
        while(l<=r){
            if(*(num_list+l)<=pivot){
                l++;
            }else{      
                swap(num_list+l,num_list+r,sizeof(int));
                r--;
            }
        }
//考虑边界问题，当r==l时，也需要判别一下这个值是否小于分界值
/*
        if(*(num_list+l)<=pivot){
            swap(num_list+l,num_list+(begin+end)/2,sizeof(int));
        }else{
            l--;
            swap(num_list+l,num_list+(begin+end)/2,sizeof(int));
        }
*/
        l--;
        r++;
        swap(num_list+l,num_list+(begin+end)/2,sizeof(int));
        l--;
        quicksort(num_list,begin, l);
        quicksort(num_list,r, end);
    }
}

 
int main(void){
    int num_list[]={5,4,3,2,1};
    int len=sizeof(num_list)/sizeof(int);
    char *sep="";
    int i;
    quicksort(num_list,0,4);
    printf("sorted_num_list={");
    for(i=0; i     printf("%s%d",sep,num_list[i]);
    sep=", ";
    }
    printf("};\n");
    system("pause");
    return 0;
}

上面的代码是我参照
Algorithm Implementation/Sorting/Quicksort：
写出来的，可能存在问题，或不够美观，望大家批评指正。
有关快速排序的相关优化的算法，如In-place等，会在以后的学习总进行总结。其基本的思想没有变化，主要就是针对分界点（pivot）的选择，进行讨论与优化。
下面的两篇参考文献相当具有参考价值，有什么问题可以查阅下面的参考文献。
参考文献：
【1】Algorithm Implementation/Sorting/Quicksort：
【2】Quicksort ：