计算机科学论坛--显示贴子

以文本方式查看主题

-  计算机科学论坛  (http://bbs.xml.org.cn/index.asp)
--  『编程心得』   (http://bbs.xml.org.cn/list.asp?boardid=42)
----  刚写的一段快速排序算法，尽可能的面向对象，请大家在质量属性各个方面给出批评意见。  (http://bbs.xml.org.cn/dispbbs.asp?boardid=42&rootid=&id=26470)

--  作者：pennyliang
--  发布时间：1/16/2006 12:58:00 AM

--  刚写的一段快速排序算法，尽可能的面向对象，请大家在质量属性各个方面给出批评意见。
//主要考虑的因素，可读性，分解均衡性。如果大家对快速排序遗忘，在看了这段代码很
//容易回忆出来，目的就达到了

#include <cstdlib>
#include <iostream>

using namespace std;
class QuickSort
{
private:
  int* m_array;
  int   m_first;
  int   m_last;
public :
  QuickSort(int* unSortedArray,int low,int high);
  virtual ~QuickSort();
  bool Process();
private:
  int Partition(int key,int low,int high);
  int ExtendLargeRegion(int key,int lowVac,int high);
  int ExtendSmallRegion(int key,int low,int HighVac);
};

QuickSort::QuickSort(int* unSortedArray,int low,int high)
{
m_array = unSortedArray;
m_first = low;
m_last = high;
};
QuickSort::~QuickSort()
{
};

bool QuickSort::Process()
{
if(m_array == NULL)
{
  return false;
}
if(m_first<m_last)
{
  int pivot = m_array[m_first];
  int splitPoint = Partition(pivot,m_first,m_last);
  m_array[splitPoint] = pivot;

  QuickSort *quickSortLeft = new QuickSort(m_array,m_first,splitPoint-1);
  quickSortLeft->Process();
  delete quickSortLeft;

  QuickSort *quickSortRight = new QuickSort(m_array,splitPoint+1,m_last);
  quickSortRight->Process();
  delete quickSortRight;
}

return true;
};

int QuickSort::Partition(int key,int low,int high)
{
int lowVac = low;
int highVac = -1;

while(low<high)
{
  highVac = ExtendLargeRegion(key,lowVac,high);
  lowVac = ExtendSmallRegion(key,low+1,highVac);
  low = lowVac;
  high = highVac - 1;
}

return low;
};

int QuickSort::ExtendLargeRegion(int key,int lowVac,int high)
{
int highVac,curr;
highVac = lowVac;

for(curr = high;curr>lowVac;curr--)
{
  if(m_array[curr]<key)
  {
   m_array[lowVac]= m_array[curr];
   highVac = curr;
   break;
  }
}

return highVac;
};

int QuickSort::ExtendSmallRegion(int key,int low,int highVac)
{
int lowVac,curr;
lowVac = highVac;
for(curr = low;curr<highVac;curr++)
{
  if(m_array[curr]>=key)
  {
   m_array[highVac]= m_array[curr];
   lowVac = curr;
   break;
  }
}

return lowVac;
};

int main(int argc, char *argv[])
{
int unSortedArray[] = {31,45,36,27,88,3,4,56,78,44,65,102,-5,0};

    QuickSort *Sorter = new QuickSort(&unSortedArray[0],0,13);
    Sorter->Process();
    delete Sorter;

    cout<<endl;
    for(int i=0;i<14;i++)
    {
     cout<<unSortedArray[i]<<endl;
    }

    system("PAUSE");
    return EXIT_SUCCESS;
}

[此贴子已经被作者于2006-1-16 10:44:26编辑过]

--  作者：pennyliang
--  发布时间：1/16/2006 1:00:00 AM

--
这居然是本学期写的第二次代码。

--  作者：pennyliang
--  发布时间：1/16/2006 12:45:00 PM

--
//根据好友Loki的意见修改的代码

#include <cstdlib>
#include <iostream>

QuickSort::QuickSort(int* unSortedArray,int low,int high)
{
m_array = unSortedArray;
m_first = low;
m_last  = high;
};
QuickSort::~QuickSort()
{
};
bool QuickSort::Process()
{
if(m_array == NULL)
{
  return false;
}
if(m_first<m_last)
{
  int pivot = m_array[m_first];
  int splitPoint = Partition(pivot,m_first,m_last);
  m_array[splitPoint] = pivot;
  QuickSortLeftRegion(m_first,splitPoint-1);
  QuickSortRightRegion(splitPoint+1,m_last);
}
return true;
};

int QuickSort::Partition(int key,int low,int high)
{
int lowVac = low;
int highVac = -1;

while(low<high)
{
  highVac = ExtendLargeRegion(key,lowVac,high);
  lowVac = ExtendSmallRegion(key,low+1,highVac);
  low = lowVac;
  high = highVac - 1;
}

return low;
};

return highVac;
};

return lowVac;
};

bool QuickSort::QuickSortRegion(int low,int high)
{
     QuickSort* sorter = new QuickSort(m_array,low,high);
     sorter->Process();
     delete sorter;
     return true;
};

bool QuickSort::QuickSortLeftRegion(int low,int high)
{
return QuickSortRegion(low,high);
};

bool QuickSort::QuickSortRightRegion(int low,int high)
{
return QuickSortRegion(low,high);
};

int main(int argc, char *argv[])
{
int unSortedArray[] = {31,45,36,27,88,3,4,56,78,44,65,102,-5,0};

[此贴子已经被作者于2006-1-16 13:16:42编辑过]

--  作者：pennyliang
--  发布时间：1/16/2006 6:19:00 PM

--
//根据chen3feng的意见修改第三个版本
#include <cstdlib>
#include <iostream>

using namespace std;

class QuickSort
{

private:
    int* m_array;
    int m_first;
    int m_last;

public :
    QuickSort(int* unSortedArray, int low, int high);
    virtual ~QuickSort();
    bool Process();

private:
    int Partition(int key, int low, int high);
    int ExtendLargeRegion(int key, int lowVac, int high);
    int ExtendSmallRegion(int key, int low, int HighVac);
    bool QuickSortLeftRegion(int low, int high);
    bool QuickSortRightRegion(int low, int high);
    bool QuickSortRegion(int low, int high);
};

QuickSort::QuickSort(int* unSortedArray, int low, int high)
{
    m_array = unSortedArray;
    m_first = low;
    m_last = high;
}

QuickSort::~QuickSort()
{
}

bool QuickSort::Process()
{
    if (m_array == NULL)
    {
        return false;
    }

    if (m_first < m_last)
    {
        int pivot = m_array[m_first];
        int splitPoint = Partition(pivot, m_first, m_last);
        m_array[splitPoint] = pivot;
        QuickSortLeftRegion(m_first, splitPoint - 1);
        QuickSortRightRegion(splitPoint + 1, m_last);
    }

return true;
}

int QuickSort::Partition(int key, int low, int high)
{
int lowVac = low;
int highVac = -1;

    while (low < high)
    {
        highVac = ExtendLargeRegion(key, lowVac, high);
        lowVac = ExtendSmallRegion(key, low + 1, highVac);
        low = lowVac;
        high = highVac - 1;
    }

return low;
}

int QuickSort::ExtendLargeRegion(int key, int lowVac, int high)
{
int highVac, curr;
highVac = lowVac;

    for (curr = high;curr > lowVac;curr--)
    {
        if (m_array[curr] < key)
        {
            m_array[lowVac] = m_array[curr];
            highVac = curr;
            break;
        }
    }

return highVac;
}

int QuickSort::ExtendSmallRegion(int key, int low, int highVac)
{
int lowVac, curr;
lowVac = highVac;

    for (curr = low;curr < highVac;curr++)
    {
        if (m_array[curr] >= key)
        {
            m_array[highVac] = m_array[curr];
            lowVac = curr;
            break;
        }
    }

return lowVac;
}

bool QuickSort::QuickSortRegion(int low, int high)
{
    QuickSort sorter(m_array, low, high);
    sorter.Process();

    return true;
}

bool QuickSort::QuickSortLeftRegion(int low, int high)
{
return QuickSortRegion(low, high);
}

bool QuickSort::QuickSortRightRegion(int low, int high)
{
return QuickSortRegion(low, high);
}

int main(int argc, char *argv[])
{
    int unSortedArray[] = {31, 45, 36, 27, 88, 3, 4, 56, 78, 44, 65, 102, -5, 0};
    QuickSort Sorter(&unSortedArray[0], 0, 13);

    Sorter.Process();
    for (int i = 0;i < 14;i++)
    {
        cout << unSortedArray[i] << endl;
    }
    system("PAUSE");

    return EXIT_SUCCESS;
}

--  作者：pennyliang
--  发布时间：1/16/2006 6:25:00 PM

--
//这个是我两年前写得代码

#include "stdafx.h"

int list[] =
{
12, 4, 6, 65, 7, 18, 23, 2, 45, 66, 8, 10, 16, 44, 22, 24,
17, 23, 34, 45, 67, 23, 12, 54, 22, 16, 47, 89, 36, 66
};

void exchange(int&a, int&b)
{
    int temp;
    temp = a;
    a = b;
    b = temp;
};

int partition(int list[], int l, int h, int pivotal)
{
int temp, pivotval;

exchange(list[pivotal], list[l]);

int pivotpos = l;

pivotval = list[pivotpos];

for (int i = l + 1;i <= h;i++)
{

        if (list[i] < pivotval && ++pivotpos != i)
        {
            exchange(list[i], list[pivotpos]);
        }
    }

exchange(list[l], list[pivotpos]);
return pivotpos;

};

int quicksort(int list[], int l, int h)
{
int pivotal;

if (h > l)
{

pivotal = (l + h) / 2;

int pivotpos = partition(list, l, h, pivotal);

        quicksort(list, l, pivotpos - 1);
        quicksort(list, pivotpos + 1, h);
    }
    else
    {}

return 0;
};

int main(int argc, char* argv[])
{
quicksort(list, 0, sizeof(list) / sizeof(int) - 1);
return 0;
}

--  作者：reallyh
--  发布时间：2/12/2006 6:45:00 PM

--
还真给忘了呵呵
3ks

--  作者：pennyliang
--  发布时间：3/13/2006 3:46:00 PM

--
using System;
using System.Collections;
using NUnit.Framework;

namespace Algorithm.Sort
{
class QuickSort:ISort
{
#region Member List
ArrayList m_array;
int m_first;
int m_last;
#endregion

#region Ctor
public QuickSort(ArrayList unSortedArray, int low, int high)
{
  #region precondition
  if(null == unSortedArray)
  {
   throw new Exception(string.Format("ArrayList cannot be sorted,{0},{1}",low,high));
  }
  #endregion

  m_array = unSortedArray;
  m_first = low;
  m_last = high;
}
#endregion

#region ISort 成员

public bool Sort()
{
  if (m_first < m_last)
  {
   IComparable pivot = (IComparable)m_array[m_first];
   int splitPoint = Partition(pivot, m_first, m_last);
   m_array[splitPoint] = pivot;
   QuickSortLeftRegion(m_first, splitPoint - 1);
   QuickSortRightRegion(splitPoint + 1, m_last);
  }
  return true;
}

#endregion

#region Private Fun
private int Partition(IComparable key, int low, int high)
{
int lowVac = low;
int highVac = -1;

  while (low < high)
  {
   highVac = ExtendLargeRegion(key, lowVac, high);
   lowVac = ExtendSmallRegion(key, low + 1, highVac);
   low = lowVac;
   high = highVac - 1;
  }

  return low;
}
private int ExtendLargeRegion(IComparable key, int lowVac, int high)
{
  int highVac, curr;
  highVac = lowVac;

  for (curr = high;curr > lowVac;curr--)
  {
   if (key.CompareTo(m_array[curr])>0)
   {
    m_array[lowVac] = m_array[curr];
    highVac = curr;
    break;
   }
  }

  return highVac;
}
private int ExtendSmallRegion(IComparable key, int low, int highVac)
{
  int lowVac, curr;
  lowVac = highVac;

  for (curr = low;curr < highVac;curr++)
  {
   int comparedValue = key.CompareTo(m_array[curr]);
   if (comparedValue<0||comparedValue==0)
   {
    m_array[highVac] = m_array[curr];
    lowVac = curr;
    break;
   }
  }
  return lowVac;
}
private bool QuickSortLeftRegion(int low, int high)
{
   return QuickSortRegion(low, high);
}
private bool QuickSortRightRegion(int low, int high)
{
   return QuickSortRegion(low, high);
}
private bool QuickSortRegion(int low, int high)
{
  QuickSort m_instance = new QuickSort(m_array,low,high);
  return m_instance.Sort();
}
  #endregion
}
public class TestObjcet:IComparable
{
  int m_value;
  public int Value
  {
   get{return m_value;}
  }
  public TestObjcet(int value)
  {
   m_value = value;
  }
  public static implicit operator int(TestObjcet m)
  {
   return m.Value;
  }

#region IComparable 成员

  public int CompareTo(object obj)
  {

   TestObjcet testObj = obj as TestObjcet;
   if(null!=testObj)
   {
    if(testObj.Value>this.Value)
    {
     return -1;
    }
    else if(testObj.Value == this.Value)
    {
     return 0;
    }
    else
    {
     return 1;
    }
   }
   else
   {
    throw new Exception(string.Format("object type is not testCase"));
   }
  }

  #endregion
}
[TestFixture]
public class TestQuickSort
{

  [Test]
  public void test()
  {
   ArrayList people1 = new ArrayList();
   people1.Add(new TestObjcet(1));
   people1.Add(new TestObjcet(2));
   people1.Add(new TestObjcet(4));
   people1.Add(new TestObjcet(3));

   ArrayList people2 = new ArrayList();
   people2.Add('a');
   people2.Add('d');
   people2.Add('c');
   people2.Add('b');

   QuickSort sorter1 = new QuickSort(people1,0,people1.Count-1);
   QuickSort sorter2 = new QuickSort(people2,0,people2.Count-1);
   Queue queue = new Queue(20);
   queue.Enqueue(sorter1);
   queue.Enqueue(sorter2);
   testSorter(queue);

   foreach (TestObjcet p in people1)
    Console.WriteLine(p);
   foreach (char p in people2)
    Console.WriteLine(p);

   Console.ReadLine();
  }
  private void testSorter(Queue queue)
  {
   ISort sorter = (queue.Dequeue())as ISort;
   if(null!=sorter)
   {
    sorter.Sort();
   }
  }
  public static void Main()
  {
   (new TestQuickSort()).test();
  }
}
}

W 3 C h i n a ( since 2003 ) 旗下站点
苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》

125.000ms