算法-快速排序

ゝ一世哀愁。 2022-07-24 06:07 17阅读 0赞

> 快速排序的过程：
> 
> 1.选基准数。
> 
> 2. j 从右端遍历，寻找比基准数小的数。
> 
> 3. i 从左端遍历，寻找比基准数大的数。
> 
> 4. 交换两数的位置，j 沿原位置继续向左寻找，i 继续向右寻找，然后交换位置。
> 
> 5. 当i = j 时，将 i 位置的数与基准数交换位置，第一次交换结束。
> 
> 6. 以上次结束的位置为界，将原数列分为左右两个数列分别从1开始递归执行。
> 
> 7. 递归结束的条件是 i > j。

> 以下以“ 6 1 2 7 9 3 4 5 10 8”十个数为例说明快速排序的过程。
> 
> 首先选取6为基准数，i，j 从两端开始遍历，如下图。

![20160515134232577][]

> 当 j 找到5的位置，i 找到7的位置时，两数交换位置。

![20160515134434971][]

> 在5与7交换后，j、i 分别继续寻找，当 j 找到4的位置，i 找到9的位置时两数交换。

![20160515134506768][]

> 当4与9交换后，j、i 继续寻找时出现了j = i，此时将基准数6与3交换。

![20160515134602825][]

> 在6与3交换结束后，6已经归位，接下来的排序中6不需再参与，此时将数列以6为中介分为左右两部分，分别重复以上步骤。

![20160515134712349][]

> 以左端部分为例继续排序，右端也是如此。

![20160515134828226][]

> 当 j = i 时，2与3交换。

![20160515134851013][]

> 交换后3已归位，以3为中介继续切分数列。

![20160515134913576][]

> 排序过程均为以上过程的重复操作，在此不再赘述，源程序如下：
> 
>     #include <stdio.h>
>     int a[20]={6,1,2,7,9,3,4,5,10,8,0}, n;
>     void quicksort(int left,int right){
>         int i,j,t,temp;
>         if(left>right)
>            return;
>                                         
>         temp=a[left]; //temp来存储基准数
>         i=left;
>         j=right;
>         while(i != j){
>             //先从右边向左找
>             while(a[j]>=temp && i<j)
>                 j--;
>             //再从左边向右找 
>             while(a[i]<=temp && i<j)
>                 i++;
>             //交换两个数在数组中的位置
>             if(i<j){
>                 t=a[i];
>                 a[i]=a[j];
>                 a[j]=t;
>             }
>         }
>         //将基准数归位
>         a[left]=a[i];
>         a[i]=temp;                               
>         quicksort(left,i-1);//继续处理左边的数列 
>         quicksort(i+1,right);//继续处理右边的数列 
>     }
>     int main(){
>         int i,j,t;
>         n = 10;
>         quicksort(0,n); 
>                                      
>         //输出排序结果
>         for(i=0;i<=n;i++)
>             printf("%d ",a[i]);
>         return 0;
>     }
> 
>   
>   
>

> 参考博文：http://ahalei.blog.51cto.com/4767671/1365285

[20160515134232577]: /images/20220722/ae5bc8eef31a425f9e09b5bfadf5e2bb.png
[20160515134434971]: /images/20220722/3f468587fd5847b39f98be5dd00d37b9.png
[20160515134506768]: /images/20220722/68c3200e460244138d76d2cb7dbafa3d.png
[20160515134602825]: /images/20220722/c7ecd92475124e76a5224c434f545953.png
[20160515134712349]: /images/20220722/5e91902be54c49f88e55288333981ebf.png
[20160515134828226]: /images/20220722/34e73f0193274e899863f99688ec8358.png
[20160515134851013]: /images/20220722/2570a13a777f48acacf27e93989c23b2.png
[20160515134913576]: /images/20220722/1e37319f7bbf44b88f6f8a9471d83831.png