那谁的技术博客

感兴趣领域:高性能服务器编程,存储,算法,Linux内核
随笔 - 210, 文章 - 0, 评论 - 1183, 引用 - 0
数据加载中……

常见排序算法的实现(五)-快速排序

快速排序的算法思想: 选定一个枢纽元素,对待排序序列进行分割,分割之后的序列一个部分小于枢纽元素,一个部分大于枢纽元素,再对这两个分割好的子序列进行上述的过程.

// 对一个给定范围的子序列选定一个枢纽元素,执行完函数之后返回分割元素所在的位置,
// 在分割元素之前的元素都小于枢纽元素,在它后面的元素都大于这个元素
int Partition(int array[], int low, int high)
{
    
// 采用子序列的第一个元素为枢纽元素
    int pivot = array[low];

    
while (low < high)
    
{
        
// 从后往前在后半部分中寻找第一个小于枢纽元素的元素
        while (low < high && array[high] >= pivot)
        
{
            
--high;
        }


        
// 将这个比枢纽元素小的元素交换到前半部分
        Swap(&array[low], &array[high]);

        
// 从前往后在前半部分中寻找第一个大于枢纽元素的元素
        while (low < high && array[low] <= pivot)
        
{
            
++low;
        }


        
// 将这个比枢纽元素大的元素交换到后半部分
        Swap(&array[low], &array[high]);
    }


    
// 返回枢纽元素所在的位置
    return low;
}


// 快速排序
void QuickSort(int array[], int low, int high)
{
    
if (low < high)
    
{
        
int n = Partition(array, low, high);
        QuickSort(array, low, n);
        QuickSort(array, n 
+ 1, high);
    }

}

posted on 2006-07-04 01:08 那谁 阅读(780) 评论(0)  编辑 收藏 引用 所属分类: 算法与数据结构


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理