MyMSDN

MyMSDN记录开发新知道

QuickSort快速排序法(2009-03-06)

本文代码已经更新,修正严重BUG,最新版本详见《QuickSort快速排序法(2009-10-28)》!

本文中所涉及的代码未做更新,请移步最新版查阅正确代码!

链接:http://www.cppblog.com/mymsdn/archive/2009/10/28/quicksort20091028.html


快速排序法:(好土,感觉满世界都会,不过还是写一下,当然了,标准库里多的是排序算法),这里还是实现经典版的快速排序了,时间复杂度O(nlogn)

Algorithms.h

#pragma once

#include <iostream>

class Algorithms
{
public:
    Algorithms(void);
    ~Algorithms(void);

public:
    template <typename T>
    static void QuickSort(T* arr, size_t min, size_t max);
private:
    template <typename T>
    static size_t qsort_helper_partition(T* arr, size_t min, size_t max);
    template <typename T>
    static inline void swap(T* arr, size_t x, size_t y);
};

template <typename T>
void Algorithms::QuickSort(T* arr, size_t min, size_t max)
{
    if(min >= max || max == 0 - 1) return;
    size_t p = qsort_helper_partition(arr, min, max);

    QuickSort(arr, min, p - 1);
    QuickSort(arr, p + 1, max);
}

template <typename T>
size_t Algorithms::qsort_helper_partition(T* arr, size_t min, size_t max)
{
    T cmp = arr[min];
    int i = min + 1, j = max;
    while(true)
    {
        while(cmp < arr[i])
            ++i;
        while(arr[j] < cmp)
            --j;
        if(i >= j) break;

        swap(arr, i, j);
    }
    swap(arr, min, j);
    return j;
}

template <typename T>
void Algorithms::swap(T* arr, size_t x, size_t y)
{
    T tmp = arr[x];
    arr[x] = arr[y];
    arr[y] = tmp;
}

用法:(顺便有标准库的排序法,当然只是调一下,没有什么可说的了)

#include "Algorithms.h"
#include <iostream>
#include <vector>
#include <algorithm>

int _tmain(int argc, _TCHAR* argv[])
{
    int arr[] = {4, 8, 3, 7, 1, 5, 6, 2};

    for(size_t i = 0; i != 8; ++i)
    {
        std::cout<<arr[i]<<" ";
    }
    std::cout<<std::endl;

    Algorithms::QuickSort(arr,0, 7);

    for(size_t i = 0; i != 8; ++i)
    {
        std::cout<<arr[i]<<" ";
    }
    std::cout<<std::endl;

    std::vector<int> vec;
    vec.push_back(3);
    vec.push_back(1);
    vec.push_back(4);
    vec.push_back(1);
    vec.push_back(7);
    vec.push_back(6);

    for(std::vector<int>::iterator iter = vec.begin();
        iter != vec.end(); ++ iter)
    {
        std::cout<<*iter<<" ";
    }
    std::cout<<std::endl;

    std::sort(vec.begin(), vec.end());

    for(std::vector<int>::iterator iter = vec.begin();
        iter != vec.end(); ++ iter)
    {
        std::cout<<*iter<<" ";
    }
    std::cout<<std::endl;

    return 0;
}

posted on 2009-03-06 03:03 volnet 阅读(1163) 评论(5)  编辑 收藏 引用 所属分类: C/C++algorithm

评论

# re: QuickSort快速排序法 2009-03-06 03:08 volnet

如果大家是要写C语言版本呢,我看看:
1、把class包裹的一大堆都去掉(里面的声明可以拷贝出来)
2、把template <typename T>都去掉,Algorithms::也去掉
然后就是调用的地方了,大家自己写一下调用就可以了  回复  更多评论   

# re: QuickSort快速排序法 2009-06-18 17:39 bug

while(true)
{
while(cmp < arr[i]) // 这里有bug!!!!!!!!!!
++i;
while(arr[j] < cmp)
--j;
if(i >= j) break;

swap(arr, i, j);
}
  回复  更多评论   

# re: QuickSort快速排序法 2009-06-19 00:10 volnet

@bug
非常感谢发现了问题。
能否详细说一下哪里的问题
你的测试数据是多少?我也测测  回复  更多评论   

# re: QuickSort快速排序法 2009-10-27 19:35 bug

当测试数据中有三个一样的值的时候,你的quicksort会陷入无限循环
int i = min + 1, j = max;
while(true)
{
while(cmp < arr[i])
++i;
while(arr[j] < cmp)
--j;
if(i >= j) break;

swap(arr, i, j);
}

应当改为:
int i = min , j = max+1;
while(true)
{
while(cmp < arr[++i])
;
while(arr[j] < cmp)
--j;
if(i >= j) break;

swap(arr, i, j);
}  回复  更多评论   

# re: QuickSort快速排序法 2009-10-28 00:55 volnet

@bug
@bug
两位bug同学不知道是不是同一个人,在此特别感谢两位提出的意见和建议。
代码已经做了修改,详见http://www.cppblog.com/mymsdn/archive/2009/10/28/quicksort20091028.html  回复  更多评论   


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


特殊功能