C语言快速排序代码

定义

快速排序由C.A.R.Hoare在1962年提出。快速排序是对冒泡排序的一种改进，采用了一种分治的策略。

基本思想

通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

步骤

先选择一个数作为基准值(这里用的是第一个数)，进行一次排序
将所有比“基准值小的数”放在基准值的“左边”，
将所有比“基准值大的数”放在基准值的“右边”，
再对左右区间重复以上步骤（进行递推），直到各区间只有一个数

函数代码如下

void quick_sort(int num[], int low, int high )
{
    int i,j,temp;
    int tmp;

    i = low;
    j = high;
    tmp = num[low];   //任命为中间分界线，左边比他小，右边比他大,通常第一个元素是基准数

    if(i > j)  //如果下标i大于下标j，函数结束运行
    {
        return;
    }

    while(i != j)
    {
        while(num[j] >= tmp && j > i)   
        {
            j--;
        }

        while(num[i] <= tmp && j > i)
        {
            i++;
        }

        if(j > i)
        {
            temp = num[j];
            num[j] = num[i];
            num[i] = temp;
        }
    }

    num[low] = num[i];
    num[i] = tmp;

    quick_sort(num,low,i-1);
    quick_sort(num,i+1,high);
}

一个参考实例

#include <stdio.h>
#include<stdlib.h>

#define SIZE 6

//快速排序
void quick_sort(int num[], int low, int high )
{
    int i,j,temp;
    int tmp;

    i = low;
    j = high;
    tmp = num[low];   //任命为中间分界线，左边比他小，右边比他大,通常第一个元素是基准数

    if(i > j)  //如果下标i大于下标j，函数结束运行
    {
        return;
    }

    while(i != j)
    {
        while(num[j] >= tmp && j > i)   
        {
            j--;
        }

        while(num[i] <= tmp && j > i)
        {
            i++;
        }

        if(j > i)
        {
            temp = num[j];
            num[j] = num[i];
            num[i] = temp;
        }
    }

    num[low] = num[i];
    num[i] = tmp;

    quick_sort(num,low,i-1);
    quick_sort(num,i+1,high);
}

int main(int argc , char **argv)
{
    //创建一个数组
    int num[SIZE] ={0};
    int i;

    //输入数字
    for(i =0; i < SIZE; i++)
    {
        scanf("%d",&num[i]);
    }

    quick_sort(num, 0, SIZE-1);

    for(i = 0; i < SIZE; i++)
    {
        printf(" %d ", num[i]);
    }
    system("pause");
    return 0;
}

扩展

前面给出的代码是将数组从小到大排序
若想改为从大到小排序
只需要将

while(i != j)
{
    while(num[j] >= tmp && j > i)   
    {
        j--;
    }

    while(num[i] <= tmp && j > i)
    {
        i++;
    }

改为

while(i != j)
{
    while(num[j] <= tmp && j > i)   
    {
        j--;
    }

    while(num[i] >= tmp && j > i)
    {
        i++;
    }