1

已修复 - 我也包含了 .cpp 文件，导致模板类出现链接器问题 - 我在 mergesort.cpp 中存在内存泄漏，这导致快速排序（包含在之后）也无法正常工作。Introsort 之前已包含在内，因此运行良好。

我的 qsort 算法：

#include "quicksort.h"

template <class typ> 
void quicksort(typ* tab, long int begin, long int end) {
  long int i = begin; 
  long int j = end;
  typ tmp;
  typ pivot = tab[(begin + end) / 2];

  /* podziel */
  while (i <= j) {
        while (tab[i] < pivot)
              i++;
        while (tab[j] > pivot)
              j--;
        if (i <= j) {
              tmp = tab[i];
              tab[i] = tab[j];
              tab[j] = tmp;
              i++;
              j--;
        }
  };

  /* rekurencja */
  if (begin < j)
        quicksort(tab, begin, j);
  if (i < end)
        quicksort(tab, i, end); 
}

我已经使用 Visual Studio 11（win 64）和 dev c++ 在 2 台不同的计算机上构建了它。我的归并排序也是如此。32002 个元素，仅此而已。

合并排序：

#include "mergesort.h"

using namespace std;


template <class typ>
void merge(typ *tab, long int begin, long int mid, long int end){
 typ *tab_pom = new typ[end+1];
 long int  i,j,k;

 i=begin; //pierwsza czesc
 j=mid+1; //druga czesc
 k=0;

 while ( (i<=mid) && (j<=end) ){ //pierwsze mniej niz srodek drugie mniej niz koniec
           if(tab[i] < tab[j]){
                tab_pom[k]=tab[i];
                i++;
                k++;
           }else{
                tab_pom[k]=tab[j];                
                j++;
                k++;
           }   
 }

 if (!(i<=mid)){
      while(j<=end){  
           tab_pom[k]=tab[j];
           k++;
           j++;
      } 
 }else{

      if (!(j<=end)){
           while(i<=mid){
                tab_pom[k]=tab[i];
                k++;
                i++;
           } 
      }
 }
 k=0;
 for (i=begin;i<=end;i++){
      tab[i]=tab_pom[k];
      k++;
 }         
}


// dzieli dane az do otzrymania posortowanych tablic jedno elementowych

template <class typ>
void merge_sort(typ *tab, long int begin, long int end){
 long int mid;

 if (begin < end){
      mid=(begin+end)/2;
      merge_sort(tab,begin,mid);
      merge_sort(tab,mid+1,end);
      merge(tab,begin,mid,end);
 }    
}

我还写过 introsort，它适用于任何数量的元素。我尝试在 Visual Studio 11 -> 项目 -> 属性 -> 链接器 -> 堆栈保留大小 -> 80000000 中增加堆栈大小。没有任何变化。任何帮助表示赞赏。

资源：

#include <iostream>
#include <time.h>
#include "introspectiv.h"
#include "introspectiv.cpp"
#include "mergesort.h"
#include "mergesort.cpp"
#include "quicksort.h"
#include "quicksort.cpp"

using namespace std;

//funkcja do kopiowania tablicy 
template<class typ>
void kopiuj(typ* tabl_1, typ* tabl_2, int indeks){
for (int i = 0 ; i < indeks ; i++) tabl_2[i] = tabl_1[i];
}

int main() {
//tworzy tablice
cout << "podaj rozmiary tablicy wypelnionej losowymi liczbami: ";
int wybor;
clock_t czas[7];
clock_t start, stop;
long int n, i, end, begin;
cin >> n;
int *tablica = new int[n];
int *tab_pom = new int[n];
for (i=0; i<n; i++){
    tablica[i] = rand() % 100;
}

end = n-1;
begin = 0;

float procent[] = {0, 0.25, 0.5, 0.75, 0.95, 0.99, 0.997};

cout << endl << "wybierz algorytm sortowania: " << endl;
cout << "quicksort - 1 " << endl;
cout << "mergesort - 2 " << endl;
cout << "introspektywne - 3 " << endl;
cin >> wybor;
switch (wybor)
{
case 1: {
    for (i=0; i<7; i++){
        kopiuj(tablica, tab_pom, end);
        end = end*procent[i]; 
        quicksort(tab_pom, begin , end);

        end = n-1;
        start=clock();
        quicksort(tab_pom, begin , end);
        stop=clock();  
        czas[i] = stop-start;

            }
        }

case 2: {
    start=clock();  
    merge_sort(tablica, begin , end);
    stop=clock();
        }
case 3: {
    start=clock();
    introspective(tablica, n);
    stop=clock();
        }
default: break;
    }


//for (i=0; i<n; i++){
//  cout<<tablica[i]<< " ";
//}

cout << endl << "Czas wybranego sortowania: " << endl; 

for (i=0; i<7; i++){
cout << "Dla " << procent[i]*100 << "% posortowanych danych: " << czas[i] << " ms"    << endl << endl;
}
system("pause");
}

在介绍和合并排序中计算时间还没有完成。

4

1 回答 1

3

快速排序：对于 32000 个元素，快速排序只进行大约 15 次递归，您不必担心堆栈大小。问题可能是您尝试传递的对象是函数中的局部变量，因此大小有限。尝试将其分配为全局或静态变量，例如：

void myfunction(){
    static int myelements[40000];
    //...
    merge_sort(myelements, 0, sizeof(myelements)/sizeof(int));
    //....
}

合并排序：我看到您多次调用 new ，但没有删除。我不明白为什么你需要分配内存，你可以只使用指针。尝试添加

delete[] tab_pom;

在合并结束时；

下次尝试提供更多诊断帮助，而不是不起作用。也许是错误信息。干杯，希望它有帮助。

于 2012-04-20T12:53:37.050 回答