算法导论读书笔记之快速排序

    快速排序是一种在实际运用中很有效率、很常用的算法，其平均复杂度为O(n*lgn)。虽然最坏复杂度为

O(n*n)(每次划分都将待排序数组划分成n-0组合，这就成了一颗左偏树或右偏树)，但是极少情况下会引起这种

情况发生。

    快速排序采用的是分治策略(divisor-and-conquor)，先将待排序数组分割成两个数组，其中左边的数组

中的元素都小于A[len(A)]，右边的数组都大于A[len(A)]，然后分别对两个数组进行快速排序，知道求解完成

quickSort.c

#include "quickSort.h"

int partition(int *A, int l, int r)
{
        int i, j, x, temp;

        for(x = A[r], i = l - 1, j = l;j <= r - 1;j++)
        {
                if(A[j] <= x)
                {
                        i++;
                        temp = A[i];
                        A[i] = A[j];
                        A[j] = temp;
                }
        }
        temp = A[i + 1];
        A[i + 1] = A[r];
        A[r] = temp;
        return (i + 1);
}

void quickSort(int *A, int l, int r)
{
        int q;
        if(l < r)
        {
                q = partition(A, l, r);
                quickSort(A, l, q - 1);
                quickSort(A, q + 1, r);
        }
}

quickSort.h

#ifndef QUICKSORT_H
#define QUICKSORT_H

int partition(int *A, int l, int r);
void quickSort(int *A, int l, int r);

#endif

main.c

#include "quickSort.h"
#include
#include
#include
#include

void print_array(int *a, int len)
{
        int i = 0;
        for(i = 0;i < len;i++)
        {
                printf("%d ", a[i]);
        }
        printf("\n");
}
int main()
{
        int i, len;
        int *A;

        printf("len = ");
        scanf("%d", &len);

        if( (A = (int *)malloc(sizeof(int) * len)) == NULL)
        {
                perror(strerror(errno));
                return 1;
        }
        for(i = 0;i < len;i++)
        {
                A[i] = rand() % 100;
        }

        printf("Before quick sorting : ");
        print_array(A, len);

        quickSort(A, 0, len - 1);

        printf("After quick sorting : ");
        print_array(A, len);

        return 0;
}