快排 C语言 原理

Python019

快排 C语言 原理,第1张

快排即qsort,包含在stdlib.h头文件里,函数一共四个参数,没返回值.一个典型的qsort的写法如下：qsort(s,n,sizeof(s[0]),cmp)

其中第一个参数是参与排序的数组名

第二个参数是参与排序的元素个数第三个三数是

单个元素的大小,推荐使用sizeof(数组名)这样的表达式,下面也有说明 :)

第四个参数就是

比较函数。

典型的cmp的定义是

int

cmp(const void *a,const void *b)

返回值必须是int,两个参数的类型必须都是const void

*.

假设是对int排序的话,如果是升序,那么就是如果a比b大返回一个正值,小则负值,相等返回

0,其他的依次类推,下面给出简单例子：

#include <stdio.h>

#include <string.h>

#include <stdlib.h>

int s[10000],n,i

int cmp(const void *a, const void *b)

{ 

 return(*(int *)a-*(int *)b)

}

int main()

{

 scanf("%d",&n)

 for(i=0i<ni++)

 scanf("%d",&s[i])

 qsort(s,n,sizeof(s[0]),cmp)

 for(i=0i<ni++) printf("%d ",s[i])

return(0)

}

你好！

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

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

递归这段理解如下：

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

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

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

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

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

假设 为  532348789

第一次以a【0】 5为基准 。

则：

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

希望能对你有所帮助。

首先 你在if(i<j)

{r[j]=r[i]j--}}这里多了一个}符号

第二

while(ii&&r[j]>=r[0])

if(ii&&r[i]<=r[0])

这两个语句出现了ii 应该是i

其他的我还在帮你看

好吧，上面两个语句还有两个问题，应该把i换成j，否则一开始就判断为假

我完全看不懂你混乱的思维，直接给你贴一个快排的代码

void quiksort(int a[],int low,int high){

int i = low

int j = high int temp = a[i] if( low <high){ while(i <j) {while((a[j] >= temp) &&(i <j)){ j--}a[i] = a[j] while((a[i] <= temp) &&(i <j)){i++} a[j]= a[i] }a[i] = temp quiksort(a,low,i-1) quiksort(a,j+1,high) }else{return }}

void main()

{

int arry[5] = {23,1,21,4,19}

quiksort(arry,0,4)

for(i=0i<5i++)

{

printf("%d ",arr[i])

}

printf("\n")

}