一般的なソートアルゴリズムの実装とパフォーマンスの比較
18947 ワード
今回はアルゴリズムの授業の実験で、私はここですべてのアルゴリズムを実現して、その中でバケツのソートアルゴリズムに対してまだ大きい改善の空間があって、チェーンテーブルの構造を変えるのはずっと速いです.
1.連結アルゴリズム:2つ以上の秩序テーブルを新しい秩序テーブルに結合し、順序テーブルにn個の要素が含まれていると仮定すると、n個の秩序サブテーブルと見なすことができ、各サブテーブルの長さは1であり、その後、2つを集計し、n/2個の長さが2または1の秩序テーブルを得る.長さnの秩序テーブルにマージされるまで、2つの集計を繰り返します.
連結アルゴリズムは分治法の応用であり、その操作は以下のように表すことができる.
分解:n個の要素をn/2個の要素を含むサブシーケンスに分割します.
解決:2つのサブシーケンスを集計ソートで再帰ソートします.
≪マージ|Merge|emdw≫:2つのソートされたサブシーケンスをマージすると、ソート結果が得られます.
性能分析:平均時間複雑度は、空間複雑度はO(n)
連結アルゴリズムの実装:
void mergeSort(int*arr,int first,int last,int*temp)/集計アルゴリズム
{
if(first {
int mid=(first+last)/2;
mergeSort(arr,first,mid,temp);
mergeSort(arr,mid+1,last,temp);
merge(arr,first,mid,last,temp);
}
}
void merge(int *arr,int first,int mid,int last,int *temp)
{
int i,j,k;
for( k=first;k<=last;k++)
temp[k]=arr[k];
for(i=first,j=mid+1,k=i;i<=mid&&j<=last;k+)/残りの部分をarrに受け取る
{
if(temp[i] arr[k]=temp[i++];
else
arr[k]=temp[j++];
}
while(i<=mid)
arr[k++]=temp[i++];
while(j<=last)
arr[k++]=temp[j++];
}
2.挿入アルゴリズム:ソートされるレコードを1つ話すたびに、前にスケジュールされたサブシーケンスの適切な位置にキーワードサイズで挿入し、記録が挿入位置を完了するまで挿入します.
性能分析:平均時間複雑度は、空間複雑度はO(1)
挿入アルゴリズムの実装:
void insertSort(int*arr,int length)/挿入ソート
{
for(int j=1;j!=length;j++)
{
int key = arr[j];
int i=j-1;
while((i>=0)&&arr[i]>key)
{
arr[i+1]=arr[i];
i=i-1;
}
arr[i+1]=key;
}
}
3.ヒルソート:ヒルソートは縮小増分ソートとも呼ばれ、まずソート対象シーケンスをいくつかのサブシーケンス(同じステップ長を持つ)に分割し、それぞれ挿入ソートを行い、ステップ長が1になるまで縮小ソートを行い、全体を挿入ソートします.
性能分析:平均時間複雑度は、空間複雑度は
ヒルソートの実装:
//ヒルソートアルゴリズムの実現
void shellSort(int *arr,int length)
{
int d = length/2;//ヒルソートの増分設定
int i ;
int j;
int temp;
while(d>=1)
{
for(i=d;i{
temp=arr[i];
j=i-d;
while(j>=0 && arr[j]>temp)
{
arr[j+d]=arr[j];
j=j-d;
}
arr[j+d] = temp;
}
d= d/2;//増分縮小
}
}
4.クイックソート:1つのシーケンスの中点を絶えず探して、それから中点の左右のシーケンスを再帰的にソートして、すべてのシーケンスのソートが完成するまで、分治の思想を使いました.
性能分析:平均時間複雑度は、空間複雑度は
クイックソートの実装:
void quickSort(int*arr,int p,int r)//クイックソート
{
if (p{
int q=partition(arr,p,r);
quickSort(arr,p,q-1);
quickSort(arr,q+1,r);
}
}
int partition(int *arr,int p,int r)
{
int x = arr[r];
int temp;
int i = p-1;
for(int j=p;j!=r;j++)
{
if (arr[j]{
i=i+1;
temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
}
temp=arr[r];
arr[r]=arr[i+1];
arr[i+1]=temp;
return i+1;
}
5.泡立ちソート:シーケンスを無秩序と秩序に分割し、大きな要素を無秩序の末尾に交換することによってソートを完了します.
性能分析:平均時間複雑度は、空間複雑度は
バブルソートの実装:
void bullSort(int*arr,int length)/泡立ちソート
{
int i,j;
int tmp;
for(i=0;i{
for(j=0;j{
if(arr[j]>arr[j+1])
{
tmp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=tmp;
}
}
}
}
6.バケツソート:長さNの並べ替え対象キーワードシーケンスK[1....n]のセットがあると仮定する.まずこのシーケンスをM個のサブ区間(バケツ)に分割する.次に、あるマッピング関数に基づいて、並べ替えられるシーケンスのキーワードkをi番目のバケツ(すなわちバケツ配列Bの下付きi)にマッピングすると、そのキーワードkはB[i]の要素(バケツB[i]ごとにN/Mのサイズのシーケンスのセット)として機能する.次に、各バケツB[i]のすべての要素を比較してソートする(ここでは挿入ソートを用いる).そして出力B[0]…を順に列挙する.B[M]のすべての内容は秩序あるシーケンスである.
次の2つの点を行う必要があります.
(1)マッピング関数f(k)は、N個のデータを平均的にM個のバケツに割り当てることができ、これにより、バケツ当たり[N/M]個のデータ量が得られる.
(2)バケツの数をできるだけ増やす.極限の場合、バケツごとに1つのデータしか得られないため、バケツ内のデータの「比較」ソート操作を完全に回避できます.
今回の実験では,各バケツの大きさを50とし,10000個のバケツを設計し,数回の実験を経て,各バケツのデータは50個を超えないようにした.
性能分析:合理的なバケツを設計する時、平均時間の複雑度は、空間の複雑度は
バケツソートの実装:
void bucketSort(int *arr,int length)
{
int **temp=new int *[10000*sizeof(int *)];
int count[10000]={0};
int i,j,flag,k=0;
for(i=0;i<10000;i++)
{
temp[i]=new int[50*sizeof(int)];
}
for(i=0;i<10000;i++)
for(j=0;j<50;j++)
temp[i][j]=0;
for(i=0;i {
flag=arr[i]/10;
temp[flag][count[flag]]=arr[i];
count[flag]++;
}
for(i=0;i<10000;i++)
{
for(j=1;j {
int key =temp[i][j];
int t = j-1;
while((t>=0)&&temp[i][t]>key)
{
temp[i][t+1]=temp[i][t];
t=t-1;
}
temp[i][t+1]=key;
}
}
for(i=0;i<10000;i++)
for(j=0;j {
arr[k]=temp[i][j];
k++;
}
}
ここで最後の合成版コードを貼ります
1.連結アルゴリズム:2つ以上の秩序テーブルを新しい秩序テーブルに結合し、順序テーブルにn個の要素が含まれていると仮定すると、n個の秩序サブテーブルと見なすことができ、各サブテーブルの長さは1であり、その後、2つを集計し、n/2個の長さが2または1の秩序テーブルを得る.長さnの秩序テーブルにマージされるまで、2つの集計を繰り返します.
連結アルゴリズムは分治法の応用であり、その操作は以下のように表すことができる.
分解:n個の要素をn/2個の要素を含むサブシーケンスに分割します.
解決:2つのサブシーケンスを集計ソートで再帰ソートします.
≪マージ|Merge|emdw≫:2つのソートされたサブシーケンスをマージすると、ソート結果が得られます.
性能分析:平均時間複雑度は、空間複雑度はO(n)
連結アルゴリズムの実装:
void mergeSort(int*arr,int first,int last,int*temp)/集計アルゴリズム
{
if(first
int mid=(first+last)/2;
mergeSort(arr,first,mid,temp);
mergeSort(arr,mid+1,last,temp);
merge(arr,first,mid,last,temp);
}
}
void merge(int *arr,int first,int mid,int last,int *temp)
{
int i,j,k;
for( k=first;k<=last;k++)
temp[k]=arr[k];
for(i=first,j=mid+1,k=i;i<=mid&&j<=last;k+)/残りの部分をarrに受け取る
{
if(temp[i]
else
arr[k]=temp[j++];
}
while(i<=mid)
arr[k++]=temp[i++];
while(j<=last)
arr[k++]=temp[j++];
}
2.挿入アルゴリズム:ソートされるレコードを1つ話すたびに、前にスケジュールされたサブシーケンスの適切な位置にキーワードサイズで挿入し、記録が挿入位置を完了するまで挿入します.
性能分析:平均時間複雑度は、空間複雑度はO(1)
挿入アルゴリズムの実装:
void insertSort(int*arr,int length)/挿入ソート
{
for(int j=1;j!=length;j++)
{
int key = arr[j];
int i=j-1;
while((i>=0)&&arr[i]>key)
{
arr[i+1]=arr[i];
i=i-1;
}
arr[i+1]=key;
}
}
3.ヒルソート:ヒルソートは縮小増分ソートとも呼ばれ、まずソート対象シーケンスをいくつかのサブシーケンス(同じステップ長を持つ)に分割し、それぞれ挿入ソートを行い、ステップ長が1になるまで縮小ソートを行い、全体を挿入ソートします.
性能分析:平均時間複雑度は、空間複雑度は
ヒルソートの実装:
//ヒルソートアルゴリズムの実現
void shellSort(int *arr,int length)
{
int d = length/2;//ヒルソートの増分設定
int i ;
int j;
int temp;
while(d>=1)
{
for(i=d;i
temp=arr[i];
j=i-d;
while(j>=0 && arr[j]>temp)
{
arr[j+d]=arr[j];
j=j-d;
}
arr[j+d] = temp;
}
d= d/2;//増分縮小
}
}
4.クイックソート:1つのシーケンスの中点を絶えず探して、それから中点の左右のシーケンスを再帰的にソートして、すべてのシーケンスのソートが完成するまで、分治の思想を使いました.
性能分析:平均時間複雑度は、空間複雑度は
クイックソートの実装:
void quickSort(int*arr,int p,int r)//クイックソート
{
if (p
int q=partition(arr,p,r);
quickSort(arr,p,q-1);
quickSort(arr,q+1,r);
}
}
int partition(int *arr,int p,int r)
{
int x = arr[r];
int temp;
int i = p-1;
for(int j=p;j!=r;j++)
{
if (arr[j]
i=i+1;
temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
}
temp=arr[r];
arr[r]=arr[i+1];
arr[i+1]=temp;
return i+1;
}
5.泡立ちソート:シーケンスを無秩序と秩序に分割し、大きな要素を無秩序の末尾に交換することによってソートを完了します.
性能分析:平均時間複雑度は、空間複雑度は
バブルソートの実装:
void bullSort(int*arr,int length)/泡立ちソート
{
int i,j;
int tmp;
for(i=0;i
for(j=0;j
if(arr[j]>arr[j+1])
{
tmp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=tmp;
}
}
}
}
6.バケツソート:長さNの並べ替え対象キーワードシーケンスK[1....n]のセットがあると仮定する.まずこのシーケンスをM個のサブ区間(バケツ)に分割する.次に、あるマッピング関数に基づいて、並べ替えられるシーケンスのキーワードkをi番目のバケツ(すなわちバケツ配列Bの下付きi)にマッピングすると、そのキーワードkはB[i]の要素(バケツB[i]ごとにN/Mのサイズのシーケンスのセット)として機能する.次に、各バケツB[i]のすべての要素を比較してソートする(ここでは挿入ソートを用いる).そして出力B[0]…を順に列挙する.B[M]のすべての内容は秩序あるシーケンスである.
次の2つの点を行う必要があります.
(1)マッピング関数f(k)は、N個のデータを平均的にM個のバケツに割り当てることができ、これにより、バケツ当たり[N/M]個のデータ量が得られる.
(2)バケツの数をできるだけ増やす.極限の場合、バケツごとに1つのデータしか得られないため、バケツ内のデータの「比較」ソート操作を完全に回避できます.
今回の実験では,各バケツの大きさを50とし,10000個のバケツを設計し,数回の実験を経て,各バケツのデータは50個を超えないようにした.
性能分析:合理的なバケツを設計する時、平均時間の複雑度は、空間の複雑度は
バケツソートの実装:
void bucketSort(int *arr,int length)
{
int **temp=new int *[10000*sizeof(int *)];
int count[10000]={0};
int i,j,flag,k=0;
for(i=0;i<10000;i++)
{
temp[i]=new int[50*sizeof(int)];
}
for(i=0;i<10000;i++)
for(j=0;j<50;j++)
temp[i][j]=0;
for(i=0;i
flag=arr[i]/10;
temp[flag][count[flag]]=arr[i];
count[flag]++;
}
for(i=0;i<10000;i++)
{
for(j=1;j
int key =temp[i][j];
int t = j-1;
while((t>=0)&&temp[i][t]>key)
{
temp[i][t+1]=temp[i][t];
t=t-1;
}
temp[i][t+1]=key;
}
}
for(i=0;i<10000;i++)
for(j=0;j
arr[k]=temp[i][j];
k++;
}
}
ここで最後の合成版コードを貼ります
#include<iostream>
#include<math.h>
#include<iomanip>
#include<time.h>
#include<stdlib.h>
using namespace std;
void initialArr(int *arr,int length);
void disPlay(int *arr,int length);
void copyArr(int *arr,int *temp,int length); // ，
void mergeSort(int *arr,int first,int last,int *temp); //
void merge(int *arr,int first,int mid,int last,int *temp);
void insertSort(int *arr,int length); //
void bullSort(int *arr,int length); //
void shellSort(int *arr,int length); //
void quickSort(int *arr,int p,int r); //
int partition(int *arr,int p,int r);
void bucketSort(int *arr,int length); //
int main()
{
clock_t start,finish;
double ptime;
int arr[10];
initialArr(arr,10);
cout<<" N=10 , :"<<endl;
disPlay(arr,10);
cout<<" ， :"<<endl;
int temp[10];
mergeSort(arr,0,9,temp);
disPlay(arr,10);
cout<<" ， :"<<endl;
insertSort(arr,10);
disPlay(arr,10);
cout<<" ， :"<<endl;
shellSort(arr,10);
disPlay(arr,10);
cout<<" ， :"<<endl;
quickSort(arr,0,9);
disPlay(arr,10);
cout<<" ， :"<<endl;
bullSort(arr,10);
disPlay(arr,10);
cout<<" ， :"<<endl;
bucketSort(arr,10);
disPlay(arr,10);
system("pause");
// N=1000
int *arr1000=new int[1000];
int *demo1000=new int[1000];
initialArr(arr1000,1000);
cout<<" N=1000 ， ："<<endl;
//
copyArr(arr1000,demo1000,1000);
int temp1000[1000];
start=clock();
mergeSort(demo1000,0,999,temp1000);
finish=clock();
ptime=(double)(finish-start)/CLOCKS_PER_SEC;
cout<<" ， :"<<ptime<<" "<<endl;
//
copyArr(arr1000,demo1000,1000);
start=clock();
insertSort(demo1000,1000);
finish=clock();
ptime=(double)(finish-start)/CLOCKS_PER_SEC;
cout<<" ， :"<<ptime<<" "<<endl;
//
copyArr(arr1000,demo1000,1000);
start=clock();
shellSort(demo1000,1000);
finish=clock();
ptime=(double)(finish-start)/CLOCKS_PER_SEC;
cout<<" ， :"<<ptime<<" "<<endl;
//
copyArr(arr1000,demo1000,1000);
start=clock();
quickSort(demo1000,0,999);
finish=clock();
ptime=(double)(finish-start)/CLOCKS_PER_SEC;
cout<<" ， :"<<ptime<<" "<<endl;
//
copyArr(arr1000,demo1000,1000);
start=clock();
bullSort(demo1000,1000);
finish=clock();
ptime=(double)(finish-start)/CLOCKS_PER_SEC;
cout<<" ， :"<<ptime<<" "<<endl;
//
copyArr(arr1000,demo1000,1000);
start=clock();
bucketSort(demo1000,1000);
finish=clock();
ptime=(double)(finish-start)/CLOCKS_PER_SEC;
cout<<" ， :"<<ptime<<" "<<endl;
// delete []arr1000;
// arr1000=NULL;
// delete []demo1000;
// demo1000=NULL;
system("pause");
// N=10000
int *arr10000=new int[10000];
int *demo10000=new int[10000];
initialArr(arr10000,10000);
cout<<" N=10000 ， ："<<endl;
//
copyArr(arr10000,demo10000,10000);
int temp10000[10000];
start=clock();
mergeSort(demo1000,0,9999,temp10000);
finish=clock();
ptime=(double)(finish-start)/CLOCKS_PER_SEC;
cout<<" ， :"<<ptime<<" "<<endl;
//
copyArr(arr10000,demo10000,10000);
start=clock();
insertSort(demo10000,10000);
finish=clock();
ptime=(double)(finish-start)/CLOCKS_PER_SEC;
cout<<" ， :"<<ptime<<" "<<endl;
//
copyArr(arr10000,demo10000,10000);
start=clock();
shellSort(demo10000,10000);
finish=clock();
ptime=(double)(finish-start)/CLOCKS_PER_SEC;
cout<<" ， :"<<ptime<<" "<<endl;
//
copyArr(arr10000,demo10000,10000);
start=clock();
quickSort(demo10000,0,9999);
finish=clock();
ptime=(double)(finish-start)/CLOCKS_PER_SEC;
cout<<" ， :"<<ptime<<" "<<endl;
//
copyArr(arr10000,demo10000,10000);
start=clock();
bullSort(demo10000,10000);
finish=clock();
ptime=(double)(finish-start)/CLOCKS_PER_SEC;
cout<<" ， :"<<ptime<<" "<<endl;
//
copyArr(arr10000,demo10000,10000);
start=clock();
bucketSort(demo10000,10000);
finish=clock();
ptime=(double)(finish-start)/CLOCKS_PER_SEC;
cout<<" ， :"<<ptime<<" "<<endl;
// delete []arr10000;
// arr10000=NULL;
// delete []demo10000;
// demo10000=NULL;
system("pause");
// N=100000
int *arr100000=new int[100000];
int *demo100000=new int[100000];
initialArr(arr100000,100000);
cout<<" N=100000 ， ："<<endl;
//
copyArr(arr100000,demo100000,100000);
int temp100000[100000];
start=clock();
mergeSort(demo10000,0,99999,temp100000);
finish=clock();
ptime=(double)(finish-start)/CLOCKS_PER_SEC;
cout<<" ， :"<<ptime<<" "<<endl;
//
copyArr(arr100000,demo100000,100000);
start=clock();
insertSort(demo100000,100000);
finish=clock();
ptime=(double)(finish-start)/CLOCKS_PER_SEC;
cout<<" ， :"<<ptime<<" "<<endl;
//
copyArr(arr100000,demo100000,10000);
start=clock();
shellSort(demo100000,100000);
finish=clock();
ptime=(double)(finish-start)/CLOCKS_PER_SEC;
cout<<" ， :"<<ptime<<" "<<endl;
//
copyArr(arr100000,demo100000,100000);
start=clock();
quickSort(demo100000,0,99999);
finish=clock();
ptime=(double)(finish-start)/CLOCKS_PER_SEC;
cout<<" ， :"<<ptime<<" "<<endl;
//
copyArr(arr100000,demo100000,100000);
start=clock();
bullSort(demo100000,100000);
finish=clock();
ptime=(double)(finish-start)/CLOCKS_PER_SEC;
cout<<" ， :"<<ptime<<" "<<endl;
//
copyArr(arr100000,demo100000,100000);
start=clock();
bucketSort(demo100000,100000);
finish=clock();
ptime=(double)(finish-start)/CLOCKS_PER_SEC;
cout<<" ， :"<<ptime<<" "<<endl;
// delete []arr100000;
// arr100000=NULL;
// delete []demo100000;
// demo100000=NULL;
system("pause");
// N=100000 5
int *arr1=new int[100000];
int *arr2=new int[100000];
int *arr3=new int[100000];
int *arr4=new int[100000];
int *arr5=new int[100000];
int *temp1=new int[100000];
int *temp2=new int[100000];
int *temp3=new int[100000];
int *temp4=new int[100000];
int *temp5=new int[100000];
initialArr(arr1,100000);
initialArr(arr2,100000);
initialArr(arr3,100000);
initialArr(arr4,100000);
initialArr(arr5,100000);
cout<<" N=100000 ， N=100000 5 ："<<endl;
//
copyArr(arr1,temp1,100000);
copyArr(arr2,temp2,100000);
copyArr(arr3,temp3,100000);
copyArr(arr4,temp4,100000);
copyArr(arr5,temp5,100000);
//int temp100000[100000];
start=clock();
mergeSort(temp1,0,99999,temp100000);
mergeSort(temp2,0,99999,temp100000);
mergeSort(temp3,0,99999,temp100000);
mergeSort(temp4,0,99999,temp100000);
mergeSort(temp5,0,99999,temp100000);
finish=clock();
ptime=(double)(finish-start)/CLOCKS_PER_SEC/5;
cout<<" 5 ， :"<<ptime<<" "<<endl;
//
copyArr(arr1,temp1,100000);
copyArr(arr2,temp2,100000);
copyArr(arr3,temp3,100000);
copyArr(arr4,temp4,100000);
copyArr(arr5,temp5,100000);
start=clock();
insertSort(temp1,100000);
insertSort(temp2,100000);
insertSort(temp3,100000);
insertSort(temp4,100000);
insertSort(temp5,100000);
finish=clock();
ptime=(double)(finish-start)/CLOCKS_PER_SEC/5;
cout<<" 5 ， :"<<ptime<<" "<<endl;
//
copyArr(arr1,temp1,100000);
copyArr(arr2,temp2,100000);
copyArr(arr3,temp3,100000);
copyArr(arr4,temp4,100000);
copyArr(arr5,temp5,100000);
start=clock();
shellSort(temp1,100000);
shellSort(temp2,100000);
shellSort(temp3,100000);
shellSort(temp4,100000);
shellSort(temp5,100000);
finish=clock();
ptime=(double)(finish-start)/CLOCKS_PER_SEC/5;
cout<<" 5 ， :"<<ptime<<" "<<endl;
//
copyArr(arr1,temp1,100000);
copyArr(arr2,temp2,100000);
copyArr(arr3,temp3,100000);
copyArr(arr4,temp4,100000);
copyArr(arr5,temp5,100000);
start=clock();
quickSort(temp1,0,99999);
quickSort(temp2,0,99999);
quickSort(temp3,0,99999);
quickSort(temp4,0,99999);
quickSort(temp5,0,99999);
finish=clock();
ptime=(double)(finish-start)/CLOCKS_PER_SEC/5;
cout<<" 5 ， :"<<ptime<<" "<<endl;
//
copyArr(arr1,temp1,100000);
copyArr(arr2,temp2,100000);
copyArr(arr3,temp3,100000);
copyArr(arr4,temp4,100000);
copyArr(arr5,temp5,100000);
start=clock();
bullSort(temp1,100000);
bullSort(temp2,100000);
bullSort(temp3,100000);
bullSort(temp4,100000);
bullSort(temp5,100000);
finish=clock();
ptime=(double)(finish-start)/CLOCKS_PER_SEC/5;
cout<<" 5 ， :"<<ptime<<" "<<endl;
//
copyArr(arr1,temp1,100000);
copyArr(arr2,temp2,100000);
copyArr(arr3,temp3,100000);
copyArr(arr4,temp4,100000);
copyArr(arr5,temp5,100000);
start=clock();
bucketSort(temp1,100000);
bucketSort(temp2,100000);
bucketSort(temp3,100000);
bucketSort(temp4,100000);
bucketSort(temp5,100000);
finish=clock();
ptime=(double)(finish-start)/CLOCKS_PER_SEC/5;
cout<<" 5 ， :"<<ptime<<" "<<endl;
return 0;
}
void initialArr(int *arr,int length)
{
srand((unsigned)time(NULL));
for(int i=0;i<length;i++)
arr[i]=1+100000.0*(rand()/(RAND_MAX+1.0));
}
void disPlay(int *arr,int length)
{
for(int i=0;i<length;i++)
{
cout<<setw(10)<<arr[i];
if((i+1)%10==0||i==length-1)
cout<<endl;
}
}
void copyArr(int *arr,int *temp,int length) // ，
{
for (int i=0;i!=length;i++)
{
temp[i]=arr[i];
}
}
void mergeSort(int *arr,int first,int last,int *temp) //
{
if(first<last)
{
int mid=(first+last)/2;
mergeSort(arr,first,mid,temp);
mergeSort(arr,mid+1,last,temp);
merge(arr,first,mid,last,temp);
}
}
void merge(int *arr,int first,int mid,int last,int *temp)
{
int i,j,k;
for( k=first;k<=last;k++)
temp[k]=arr[k];
for(i=first,j=mid+1,k=i;i<=mid&&j<=last;k++) // arr
{
if(temp[i]<temp[j])
arr[k]=temp[i++];
else
arr[k]=temp[j++];
}
while(i<=mid)
arr[k++]=temp[i++];
while(j<=last)
arr[k++]=temp[j++];
}
void insertSort(int *arr,int length) //
{
for(int j=1;j!=length;j++)
{
int key = arr[j];
int i=j-1;
while((i>=0)&&arr[i]>key)
{
arr[i+1]=arr[i];
i=i-1;
}
arr[i+1]=key;
}
}
void bullSort(int *arr,int length) //
{
int i,j;
int tmp;
for(i=0;i<length;i++)
{
for(j=0;j<length-i-1;j++)
{
if(arr[j]>arr[j+1])
{
tmp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=tmp;
}
}
}
}
void quickSort(int *arr,int p,int r) //
{
if (p<r)
{
int q=partition(arr,p,r);
quickSort(arr,p,q-1);
quickSort(arr,q+1,r);
}
}
int partition(int *arr,int p,int r)
{
int x = arr[r];
int temp;
int i = p-1;
for(int j=p;j!=r;j++)
{
if (arr[j]<x)
{
i=i+1;
temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
}
temp=arr[r];
arr[r]=arr[i+1];
arr[i+1]=temp;
return i+1;
}
//
void shellSort(int *arr,int length)
{
int d = length/2; //
int i ;
int j;
int temp;
while(d>=1)
{
for(i=d;i<length;i++)
{
temp=arr[i];
j=i-d;
while(j>=0 && arr[j]>temp)
{
arr[j+d]=arr[j];
j=j-d;
}
arr[j+d] = temp;
}
d= d/2; //
}
}
void bucketSort(int *arr,int length)
{
int **temp=new int *[10000*sizeof(int *)];
int count[10000]={0};
int i,j,flag,k=0;
for(i=0;i<10000;i++)
{
temp[i]=new int[50*sizeof(int)];
}
for(i=0;i<10000;i++)
for(j=0;j<50;j++)
temp[i][j]=0;
for(i=0;i<length;i++)
{
flag=arr[i]/10;
temp[flag][count[flag]]=arr[i];
count[flag]++;
}
for(i=0;i<10000;i++)
{
for(j=1;j<count[i];j++)
{
int key =temp[i][j];
int t = j-1;
while((t>=0)&&temp[i][t]>key)
{
temp[i][t+1]=temp[i][t];
t=t-1;
}
temp[i][t+1]=key;
}
}
for(i=0;i<10000;i++)
for(j=0;j<count[i];j++)
{
arr[k]=temp[i][j];
k++;
}
}