Chinaunix首页 | 论坛 | 博客
  • 博客访问: 481467
  • 博文数量: 61
  • 博客积分: 2438
  • 博客等级: 大尉
  • 技术积分: 871
  • 用 户 组: 普通用户
  • 注册时间: 2010-07-28 08:04
文章分类
文章存档

2013年(1)

2012年(8)

2011年(15)

2010年(37)

分类: C/C++

2010-11-14 10:23:09

在学习中经常会遇到排序的问题,而在众多的排序算法中,快速排序可谓是首选,下面是我对它的理解,希望对初学者有所启发,下面是源码(补充一点,我当中是用的递归实现的):

/*
 *filename: quicksort.c
 *discription: the array data structure, to take any value as a benchhark for comparison
 * (first element), larger than it is to one side, one side smaller than it.
 * then, here two arrays and then repeat the process in.
 */

#include <stdio.h>
#define N 9

void QuickSort( int a[], int low, int high );

int main(void)
{
    int array[N] = {2, 8, 9, 0, 3, 7 , 2, 4, 6};/*test array*/
    int i = 0;

    QuickSort(array, 0, N - 1);

    printf("Sort completed\n");
    /*output*/
    while(i < N){
        printf("%d ", array[i]);
        i++;
    }
    printf("\n");

    return 0;
}

void QuickSort(int *array, int low, int high)
{
    int i = low, j = high; //low represent array bottom, high represent array end

    int temp = array[low]; //temp for the base


    while(i < j){ // exports conditions: i >= j

        while(i < j && temp <= array[j])
            j--; //in the right scan

        if(i < j){
            array[i] = array[j];
            i++;
        }

        while(i < j && temp > array[i])
            i++; //in the left scan

        if(i < j){
            array[j] = array[i];
            j--;
        }
    }
    array[i] = temp; //the base value in the middle

    //recursively divided into two arrays in the continued sweep

    if(low < i) QuickSort(array, low, i - 1);
    if(i < high) QuickSort(array, j + 1, high);
}


这只是我对他的一个简单实现,如果谁有更好的想法,希望一起讨论
我的邮箱:qiaozqjhsy@gmail.com
阅读(458) | 评论(0) | 转发(0) |
0

上一篇:ubuntu面板恢复

下一篇:sprintf函数

给主人留下些什么吧!~~