C语言实现快速排序

我觉得冒泡排序是比较简单的;所以今天我们实现一个叫做快速排序的;

Problem

你想要将(4,3,5,1,2)排序成(1,2,3,4,5)

你决定使用最简单的快速排序;

Solution

首先,打开你的terminal,我写得C代码通常都是用vi编辑,gcc编译;

vim quickSortSample.c

因为,快速排序需要对数据进行分割然后处理,再分割再处理;

显然需要一个递归的过程;

所以,我们先把递归结束条件写好;

#include <stdio.h>

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

也就是说,当输入只有一个数字就没有必要排序啦!直接返回;

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--) {                                                 

//TODO ...

}     
}

注意: p = a[n / 2];的目地是获取数组中得中间位置的数据;

我们都知道,数组下标是整数,因此,如果n=3那么n/2应该是1,此时正好平分数组;

若是,n=4那么n/2应该是2,而此时它们就不完全是平分数组啦;

for循环的作用是为了从前后两个方向分别遍历;

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--;
    }         
}

注意:我们在for循环中又进行啦while循环;

它的作用是对元素进行遍历,假设左边的数据没有p中保存的元素大,那么继续寻找,并且把i自增;

当找到比p大的或者相等得则停止第一个while循环;

例如:如果数组(2,5,3,1,4)那么p显然是3,当while循环发现5大于3时停止循环,此时i=1;

同理,第二个while循环中,p依然是3,当while循环第一次发现4大于3则继续循环此时j=4;

当while循环到j=3时,得到的元素是1,1不大于3所以停止循环,此时得到的j=3;

好啦!那么我们知道在for循环中没有明确指定循环停止条件;

它该什么时候停止呢?

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;
    } 
}

注意:当i>=j意味着此时数据已经全部遍历完了;

因为i与j分布在数组左右两部分,当它们重合,当然也就表明它们遍历完啦;

刚才,我们的两个while循环分别找到啦一个左边比p大得元素,和一个右边比p小的数字;

显然这两个元素应该交换位置的;

那么怎么实现呢;

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:http://www.heiqu.com/f58145674c053f98a8573c4cb8383f21.html