C语言，快速排序算法

你好！

首先 0 ，n-1 。应该是 数组的坐标（因为n个数字。所以数组的坐标是0 到n-1）

而a是你传入的数组。所以他会根据数组的坐标到数组中找到元素。比较并进行排序。

递归这段理解如下：

首先要了解快速排序的思想：

1）随意找一个基准数 。将比基准小的都放到它左边。比它大的都放到它右边。所以当返回基准的坐标的时候。其实这个坐标左边都是小于它的，右边都是大于等于它的。（这里主要是看代码的实现。图中代码是大于等于在右边。也可以自己写小于等于在左边。这个不影响最后结果）

2）那么第二次对于返回基准坐标的左右两边。我们同样利用返回的基准坐标找到两个“基准”（如下图）。就会使得返回的这两个基准左右两边有序

第三次  用返回的两个基准找到四个基准（如图）

然后不断递归不断的在整体有序的情况下使局部变的有序。

假设 为  532348789

第一次以a0 5为基准 。

则：

图中红色标识为基准元素 最后会使得数组全局有序。

希望能对你有所帮助。

/

冒泡排序和快速排序比较的C语言程序实现

要求：

1．被排序对象由计算机随机生成，长度分别取20、500、5000；

2．设计测试方法，统计分析正序、逆序、随机序情况下各种算法关键码比较次数和记录移动次数；

3．对结果进行统计分析；

/

#include<stdioh>

#include <timeh>

#define ARR_LENGTH 5000

int arr[ARR_LENGTH];

int maopao(int array[],int n)

{

int i,j,flag,temp,index=0;

for(i=0;i<n-1;i++)

{

flag=1;

for(j=0;j<n-i-1;j++)

{

if(array[j]>array[j+1])

{

temp=array[j];

array[j]=array[j+1];

array[j+1]=temp;

flag = 0;

index++;

}

}

if(1 == flag)

break;

}

return index;

}

static result=0;

int partitions(int a[],int low,int high)

{

int pivotkey=a[low];

//a[0]=a[low];

while(low<high)

{

while(low<high && a[high]>=pivotkey)

--high;

a[low]=a[high];

while(low<high && a[low]<=pivotkey)

++low;

a[high]=a[low];

result++;

}

//a[low]=a[0];

a[low]=pivotkey;

return low;

}

void qsort(int a[],int low,int high)

{

int pivottag;

if(low<high)

{

//递归调用

pivottag=partitions(a,low,high);

qsort(a,low,pivottag-1);

qsort(a,pivottag+1,high);

}

}

void kuaisu(int a[],int n)

{

qsort(a,0,n);

}

int main()

{

int length,range,index,k,j;

printf("请输入随机生成数的长度length和随机数的最大值range:\n");

scanf("%d%d",&length,&range);

for(index=0;index<length;index++)

{

arr[index]=rand()%range;

}

k=maopao(arr,length);

printf("冒泡排序执行次数:k=%d\n",k);

kuaisu(arr,length);

printf("快速排序执行次数:result=%d\n",result);

return 0;

}

/

功能：快速排序

输入：数组名称（也就是数组首地址）、数组中起止元素的下标

================================================

/

/

====================================================

算法思想简单描述：

快速排序是对冒泡排序的一种本质改进。它的基本思想是通过一趟

扫描后，使得排序序列的长度能大幅度地减少。在冒泡排序中，一次

扫描只能确保最大数值的数移到正确位置，而待排序序列的长度可能只

减少1。快速排序通过一趟扫描，就能确保某个数（以它为基准点吧）

的左边各数都比它小，右边各数都比它大。然后又用同样的方法处理

它左右两边的数，直到基准点的左右只有一个元素为止。它是由

CARHoare于1962年提出的。

显然快速排序可以用递归实现，当然也可以用栈化解递归实现。下面的

函数是用递归实现的，有兴趣的朋友可以改成非递归的。

快速排序是不稳定的。最理想情况算法时间复杂度O(nlog2n)，最坏O(n2)

=====================================================

/

void quick_sort(int x, int low, int high)

{

int i, j, t;

if (low < high) /要排序的元素起止下标，保证小的放在左边，大的放在右边。这里以下标为low的元素为基准点/

{

i = low;

j = high;

t = (x+low); /暂存基准点的数/

while (i<j) /循环扫描/

{

while (i<j && (x+j)>t) /在右边的只要比基准点大仍放在右边/

{

j--; /前移一个位置/

}

if (i<j)

{

(x+i) = (x+j); /上面的循环退出：即出现比基准点小的数，替换基准点的数/

i++; /后移一个位置，并以此为基准点/

}

while (i<j && (x+i)<=t) /在左边的只要小于等于基准点仍放在左边/

{

i++; /后移一个位置/

}

if (i<j)

{

(x+j) = (x+i); /上面的循环退出：即出现比基准点大的数，放到右边/

j--; /前移一个位置/

}

}

(x+i) = t; /一遍扫描完后，放到适当位置/

quick_sort(x,low,i-1); /对基准点左边的数再执行快速排序/

quick_sort(x,i+1,high); /对基准点右边的数再执行快速排序/

}

}

我的文件路径"c:\\listtxt"，里面测试数据就是你举例的：第一行：7，第二行：-2 8 42 9 76 1 30。

#include<stdlibh>

#include<conioh>

int num[100];

int cmp ( const void a , const void b );//qsort的子函数

int compare(const void p, const void q);//bsearch的子函数

int duwenjian(char paixu, int A[], int lang);

int main()

{

    char paixu[]="c:\\listtxt";

    int lang,a=NULL,i,n,isFouund=NULL;

    a=(int )malloc(sizeof(int)10000);

    if(duwenjian(paixu,a,&lang)==-1)

        exit(1);

    qsort(a,lang,sizeof(a[0]),cmp);

    printf("从文件中读取数组并升序排列打印为：");

    for(i=0;i<lang;i++)

        printf("%d ",a[i]);

    while(1)

    {

        printf("\n输入要查找的数字：");

        scanf("%d",&n);

        isFouund = (int )bsearch(&n, a, lang, sizeof(int), compare);//bsearch有匹配返回地址，无返回NULL。多个匹配不指定哪一个

        if(isFouund==NULL)

            printf("不在已升序排列的整数序列中\n");

        else

            printf("在已升序排列的整数序列中,地址为%p。\n",isFouund);

    }

    return 0;

}

int compare(const void p, const void q)

{

    return ((int )p - (int )q);

}

int cmp ( const void a , const void b )

{

  return (int )a - (int )b;//升序

}

int duwenjian(char paixu, int A[], int lang)

{

    FILE file;

    int i;

    file=fopen(paixu, "r");

    if (file==NULL) {

        fprintf(stderr, "文档 %s 打开失败\n", paixu);

        return -1;

    }

    fscanf(file, "%d", lang);

    if (lang>10000) {

        fprintf(stderr, "文档%s中的数字过多，至多只允许10000位\n",

        paixu);

        return -1;

    }

    for (i=0; i<lang; i++) {

        fscanf(file, "%d", &(A[i]));

    }

    return 0;

}

以上就是关于C语言，快速排序算法全部的内容，包括:C语言，快速排序算法、冒泡排序和快速排序的C语言实现比较、c语言快速排序等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！