C语言实现快速排序(3)

for ( i = 0, j = n -1;; i++, j--) {
        while (a[i] < p)
            i++;
        while (p < a[j])
            j--;
        if ( i >= j)
            break;
        tmp = a[i]; a[i] = a[j]; a[j] = tmp;    //swap both ..
    }
}

int main(void)
{
    int a[] = { 2, 5, 7, 3, -1, 1, 4};
    int n = sizeof a /sizeof a[0];
    int i;
    for (i = 0; i < n; i++)
        printf("%d%s", a[i], i == n -1 ? "\n" : " ");
    quick_sort(a, n);
    for (i = 0; i < n; i++)
        printf("%d%s", a[i], i == n -1 ? "\n" : " ");

return 0;
}

我们会得到如下结果：

显然，我们已经得到啦p左边都是小于p的；

右边则是大于p的；

符合我们的设想；

为了把整个数组正确排序，我们需要分别又对两部分重复一遍刚才的操作；

好，我们递归的调用函数，并且把数组的两部分元素传递到函数中;

void quick_sort( int *a, int n)
{
    int i, j, p, tmp;
    if (n < 2)  return;

p = a[n / 2];  // Get the middle element as pivot ..

for ( i = 0, j = n -1;; i++, j--) {
        while (a[i] < p)
            i++;
        while (p < a[j])
            j--;
        if ( i >= j)
            break;
        tmp = a[i]; a[i] = a[j]; a[j] = tmp;    //swap both ..
    } 

quick_sort( a, i);
    quick_sort( a + i, n - i);
}

注意：

第一个递归调用处理数组的前部分，a对应的是数组的首地址，i是指对应的元素个数；

第二个递归调用处理数组后部分，a + i指的当然是首地址加偏移地址，如果你对偏移地址有问题的话，应该看看计算机寻址方式的资料啦；

接下来看运行结果：

最后，我们把所有代码附上:

#include <stdio.h>

void quick_sort( int *a, int n)
{
    int i, j, p, tmp;
    if (n < 2)  return;

p = a[n / 2];  // Get the middle element as pivot ..

for ( i = 0, j = n -1;; i++, j--) {
        while (a[i] < p)
            i++;
        while (p < a[j])
            j--;
        if ( i >= j)
            break;
        tmp = a[i]; a[i] = a[j]; a[j] = tmp;    //swap both ..
    } 

quick_sort( a, i);
    quick_sort( a + i, n - i);
}

int main(void)
{
    int a[] = { 2, 5, 7, 3, -1, 1, 4};
    int n = sizeof a /sizeof a[0];
    int i;
    for (i = 0; i < n; i++)
        printf("%d%s", a[i], i == n -1 ? "\n" : " ");
    quick_sort(a, n);
    for (i = 0; i < n; i++)
        printf("%d%s", a[i], i == n -1 ? "\n" : " ");
   
    return 0;
}