有极速快乐十分吗|极速快乐十分走势图|

各排序算法的C++實現與性能測試

了解下各種排序的效率問題
服務器君一共花費了275.118 ms進行了7次數據庫查詢,努力地為您提供了這個頁面。
試試閱讀模式?希望聽取您的建議

排序是計算機算法中非常重要的一項,而排序算法又有不少實現方法,那么哪些排序算法比較有效率,哪些算法在特定場合比較有效,下面將用C++實現各種算法,并且比較他們的效率,讓我們對各種排序有個更深入的了解。

minheap.h 用于堆排序:

//使用時注意將關鍵碼加入
#ifndef MINHEAP_H
#define MINHEAP_H
#include <assert.h>
#include <iostream>
using std::cout;
using std::cin;
using std::endl;
using std::cerr;
#include <stdlib.h>
//const int maxPQSize = 50;  
template <class Type> class MinHeap {
public: 
	MinHeap ( int maxSize );//根據最大長度建堆
	MinHeap ( Type arr[], int n );//根據數組arr[]建堆
	~MinHeap ( ) { delete [] heap; }
	const MinHeap<Type> & operator = ( const MinHeap &R );//重載賦值運算符
    int Insert ( const Type &x );//插入元素
	int RemoveMin ( Type &x );//移除關鍵碼最小的元素,并賦給x
	int IsEmpty ( ) const { return CurrentSize == 0; }//檢查堆是否為空     
	int IsFull ( ) const { return CurrentSize == MaxHeapSize; }//檢查對是否滿
    void MakeEmpty ( ) { CurrentSize = 0; }//使堆空
private: 
    enum { DefaultSize = 50 };//默認堆的大小
    Type *heap;                 
    int CurrentSize;
    int MaxHeapSize;
    void FilterDown ( int i, int m );//自上向下調整堆
    void FilterUp ( int i );//自下向上調整堆
};
template <class Type> MinHeap <Type>::MinHeap ( int maxSize )
{
	//根據給定大小maxSize,建立堆對象
    MaxHeapSize = (DefaultSize < maxSize ) ? maxSize : DefaultSize;	        //確定堆大小
    heap = new Type [MaxHeapSize];  //創建堆空間
    CurrentSize = 0;                               //初始化
}
template <class Type> MinHeap <Type>::MinHeap ( Type arr[], int n )
{
	//根據給定數組中的數據和大小,建立堆對象    
	MaxHeapSize = DefaultSize < n ? n : DefaultSize;
    heap = new Type [MaxHeapSize]; 
    if(heap==NULL){cerr <<"fail" <<endl;exit(1);}
	for(int i =0; i< n; i++)
		heap[i] = arr[i];               //數組傳送
    CurrentSize = n;       //當前堆大小
    int currentPos = (CurrentSize-2)/2;   //最后非葉
    while ( currentPos >= 0 ) {       
		//從下到上逐步擴大,形成堆
        FilterDown ( currentPos, CurrentSize-1 );
		currentPos-- ;
        //從currentPos開始,到0為止, 調整currentPos--; }
	}
}
template <class Type> void MinHeap<Type>::FilterDown ( const int start, const int EndOfHeap )
{
	// 結點i的左、右子樹均為堆,調整結點i
	int i = start,   j = 2*i+1;           // j 是 i 的左子女
	Type temp = heap[i];
	while ( j <= EndOfHeap ) {
		if ( j < EndOfHeap && heap[j] > heap[j+1] )
			j++;//兩子女中選小者
		if ( temp<= heap[j] ) break;
		else { heap[i] = heap[j];  i = j;   j = 2*j+1; }
	}
	heap[i] = temp;
}
template <class Type> int MinHeap<Type>::Insert ( const Type &x ) 
{
	//在堆中插入新元素 x
	if ( CurrentSize == MaxHeapSize )       //堆滿
	{ 
		cout << "堆已滿" << endl;  return 0; 
	}
	heap[CurrentSize] = x;           //插在表尾  
	FilterUp (CurrentSize);          //向上調整為堆
	CurrentSize++;                       //堆元素增一
	return 1;
}
template <class Type> void MinHeap<Type>::FilterUp ( int start ) 
{
	//從 start 開始,向上直到0,調整堆
	int j = start,  i = (j-1)/2;    // i 是 j 的雙親
	Type temp = heap[j];
	while ( j > 0 ) {      
		if ( (heap[i].root->data.key )<= (temp.root->data.key) ) break;
		else {  heap[j] = heap[i];  j = i;  i = (i -1)/2; }
	}
	heap[j] = temp;
}
template <class Type> int MinHeap <Type>::RemoveMin ( Type &x ) 
{
	if ( !CurrentSize )
	{ 
		cout << "堆已空 " << endl; 
		return 0; 
	}
	x = heap[0];             //最小元素出隊列
	heap[0] = heap[CurrentSize-1];    
	CurrentSize--;        //用最小元素填補
	FilterDown ( 0, CurrentSize-1 );
	//從0號位置開始自頂向下調整為堆
	return 1;
}	
#endif

sort.cpp 主要的排序函數集包括冒泡排序、快速排序、插入排序、希爾排序、計數排序:

//n^2
//冒泡排序V[n]不參與排序
void BubbleSort (int V[], int n ) 
{
    bool exchange;	     //設置交換標志置
    for ( int i = 0;  i < n;  i++ ){
        exchange=false;
		for (int j=n-1; j>i; j--) { //反向檢測,檢查是否逆序
			if  (V[j-1] > V[j]) //發生逆序,交換相鄰元素
			{ 
				int temp=V[j-1]; 
				V[j-1]=V[j];
				V[j]=temp; 
				exchange=true;//交換標志置位
			}
		}
		
		if  (exchange == false)
			return; //本趟無逆序,停止處理
	}
}
//插入排序,L[begin],L[end]都參與排序
void InsertionSort ( int L[], const int begin, const int end)
{
	//按關鍵碼 Key 非遞減順序對表進行排序
	int temp;
	int i, j;
    for ( i = begin; i < end; i++ ) 
	{
		if  (L[i]>L[i+1]) 
		{
			temp = L[i+1]; 
			j=i;
			do 
			{
				L[j+1]=L[j];
				if(j == 0)
				{
					j--;
					break;
				}
				j--;
				
			} while(temp<L[j]);
			L[j+1]=temp;
		}
	}
}
//n*logn
//快速排序A[startingsub],A[endingsub]都參與排序
void QuickSort( int A[], int startingsub, int endingsub)
{
	if ( startingsub >= endingsub  )
		;
	else{
		int partition;
		int q = startingsub;
		int p = endingsub;
		int hold;
		
		do{
			for(partition = q ; p > q ; p--){
				if( A[q] > A[p]){
					hold = A[q];
					A[q] = A[p];
					A[p] = hold;
					break;
				}
			}
			for(partition = p; p > q; q++){
				if(A[p] < A[q]){
					hold = A[q];
					A[q] = A[p];
					A[p] = hold;
					break;
				}
			}
			
		}while( q < p );
		QuickSort( A, startingsub, partition - 1 );
		QuickSort( A, partition + 1, endingsub );
	}
}
//希爾排序,L[left],L[right]都參與排序
void Shellsort( int L[], const int left, const int right)
{
	int i, j, gap=right-left+1;   //增量的初始值
	int temp;
	do{
		gap=gap/3+1;               //求下一增量值
		for(i=left+gap; i<=right; i++)
			//各子序列交替處理
			if( L[i]<L[i-gap]){        //逆序
				temp=L[i]; j=i-gap;     
				do{
					L[j+gap]=L[j];    //后移元素
					j=j-gap;      //再比較前一元素
				}while(j>left&&temp<L[j]);
				L[j+gap]=temp;   //將vector[i]回送
			}
	}while(gap>1);
} 
//n
//計數排序,L[n]不參與排序
void CountingSort( int L[], const int n )
{
	int i,j;
	const int k =1001;
	int tmp[k];
	int *R;
	R = new int[n];
	for(i=0;i<k;i++) tmp[i]= 0; 
	for(j=0;j<n;j++) tmp[L[j]]++; 
    //執行完上面的循環后,tmp[i]的值是L中等于i的元素的個數
	for(i=1;i<k;i++)
		tmp[i]=tmp[i]+tmp[i-1]; //執行完上面的循環后,
	//tmp[i]的值是L中小于等于i的元素的個數
	for(j=n-1;j>=0;j--) //這里是逆向遍歷,保證了排序的穩定性
	{
		
		R[tmp[L[j]]-1] = L[j];  
		//L[j]存放在輸出數組R的第tmp[L[j]]個位置上
		tmp[L[j]]--; 
		//tmp[L[j]]表示L中剩余的元素中小于等于L[j]的元素的個數 
		
	}
	for(j=0;j<n;j++) L[j] = R[j];
}
//基數排序
void printArray( const int Array[], const int arraySize );
int getDigit(int num, int dig);
const int radix=10;   //基數
void RadixSort(int L[], int left, int right, int d){
//MSD排序算法的實現。從高位到低位對序列劃分,實現排序。d是第幾位數,d=1是最低位。left和right是待排序元素子序列的始端與尾端。
   int i, j, count[radix], p1, p2;
   int *auxArray;
   int M = 5;
   auxArray = new int[right-left+1];
   if (d<=0) return; //位數處理完遞歸結束
   if (right-left+1<M){//對于小序列可調用直接插入排序
       InsertionSort(L,left,right); return;
   }
for (j=0; j<radix; j++) count[j]=0;
   for (i=left; i<=right; i++) //統計各桶元素的存放位置
       count[getDigit(L[i],d)]++;
   for (j=1; j<radix; j++) //安排各桶元素的存放位置
       count[j]=count[j]+count[j-1];
   for (i=right; i>=left; i--){ //將待排序序列中的元素按位置分配到各個桶中,存于助數組auxArray中
       j=getDigit(L[i],d);  //取元素L[i]第d位的值
       auxArray[count[j]-1]=L[i]; //按預先計算位置存放
       count[j]--;  //計數器減1
   }
   for (i=left, j=0; i<=right; i++, j++)	
       L[i]=auxArray[j];  //從輔助數組順序寫入原數組
   delete []auxArray;
	for (j=0; j<radix; j++){ //按桶遞歸對d-1位處理
       p1=count[j]+left;  //取桶始端,相對位置,需要加上初值$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$
       (j+1 <radix )?(p2=count[j+1]-1+left):(p2=right) ; //取桶尾端
	//	delete []count;
	   if(p1<p2){
       RadixSort(L, p1, p2, d-1);  //對桶內元素進行基數排序 
	 //  printArray(L,10);
	   }
   }
 
} 
int getDigit(int num, int dig)
{
	int myradix = 1;
/*	for(int i = 1;i<dig;i++)
	{
	myradix *= radix;
	}*/
	switch(dig)
	{
	case 1:
		myradix = 1;
		break;
case 2:
		myradix = 10;
		break;
case 3:
		myradix = 1000;
		break;
case 4:
		myradix = 10000;
		break;
default:
		myradix = 1;
		break;
	}
	return (num/myradix)%radix;
}

maintest.cpp 測試例子:

#include<iostream>
using std::cout;
using std::cin;
using std::endl;
#include <cstdlib>
#include <ctime>
#include<iostream>
using std::cout;
using std::cin;
using std::ios;
using std::cerr;
using std::endl;
#include<iomanip>
using std::setw;
using std::fixed;
#include<fstream>
using std::ifstream;
using std::ofstream;
using std::flush;
#include<string>
using std::string;
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include"minheap.h"
void BubbleSort(int arr[], int size);//冒泡排序
void QuickSort( int A[], int startingsub, int endingsub);//快速排序
void InsertionSort ( int L[], const int begin,const int n);//插入排序
void Shellsort( int L[], const int left, const int right);//希爾排序
void CountingSort( int L[], const int n );//計數排序
int getDigit(int num, int dig);//基數排序中獲取第dig位的數字
void RadixSort(int L[], int left, int right, int d);//基數排序
void printArray( const int Array[], const int arraySize );//輸出數組
int main()
{
	clock_t start, finish;
	double  duration;
	/* 測量一個事件持續的時間*/
	ofstream *ofs;
	string fileName = "sortResult.txt";
	ofs = new ofstream(fileName.c_str(),ios::out|ios::app);
	const int size = 100000;
	int a[size];
	int b[size];
	srand(time(0));
	ofs->close();
	for(int i = 0; i < 20;i++)
	{
		ofs->open(fileName.c_str(),ios::out|ios::app);
		if( ofs->fail()){
                cout<<"!!";
				ofs->close();
		}
		for(int k =0; k <size;k++)
		{
			a[k] = rand()%1000;
			b[k] = a[k];
			
		} 		
		/*	for( k =0; k <size;k++)
		{
		a[k] = k;
		b[k] = a[k];
		
	} */
		//printArray(a,size);	
		//計數排序
		for( k =0; k <size;k++)
		{
			a[k] = 	b[k];
		}
		start = clock();
		CountingSort(a,size);
		
		finish = clock();
		//	printArray(a,size);
		
		duration = (double)(finish - start) / CLOCKS_PER_SEC;
		printf( "%s%f seconds\n", "計數排序:",duration );
		*ofs<<"第"<<i<<"次:\n " <<"排序內容:0~999共" << size <<  " 個整數\n" ;
		*ofs<<"第"<<i<<"次計數排序:\n " <<"		Time:	" <<fixed<< duration <<  " seconds\n";
		//基數排序
		for( k =0; k <size;k++)
		{
			a[k] = 	b[k];
		}
		start = clock();
		RadixSort(a, 0,size-1, 3);
		finish = clock();
		//	printArray(a,size);
		
		duration = (double)(finish - start) / CLOCKS_PER_SEC;
		printf( "%s%f seconds\n", "基數排序:",duration );
		*ofs<<"第"<<i<<"次基數排序:\n " <<"		Time:	" << duration <<  " seconds\n";
		//堆排序
		MinHeap<int> mhp(a,size); 
		start = clock();
		for( k =0; k <size;k++)
		{
			mhp.RemoveMin(a[k]);
		}
		finish = clock();
		//	printArray(a,size);
		duration = (double)(finish - start) / CLOCKS_PER_SEC;
		printf( "%s%f seconds\n", "堆排序:",duration );
		*ofs<<"第"<<i<<"次堆排序:\n " <<"		Time:	" << duration <<  " seconds\n";
		//快速排序
		for( k =0; k <size;k++)
		{
			a[k] = 	b[k];
			
		}
		//printArray(a,size);
		start = clock();
		QuickSort(a,0,size-1);
		finish = clock();
		//	printArray(a,size);
		duration = (double)(finish - start) / CLOCKS_PER_SEC;
		printf( "%s%f seconds\n", "快速排序:",duration );
		*ofs<<"第"<<i<<"次快速排序:\n " <<"		Time:	" << duration <<  " seconds\n";
		//希爾排序
		for( k =0; k <size;k++)
		{
			a[k] = 	b[k];
		}
		start = clock();
		Shellsort(a,0,size-1);
		
		finish = clock();
		//	printArray(a,size);
		
		duration = (double)(finish - start) / CLOCKS_PER_SEC;
		printf( "%s%f seconds\n", "希爾排序:",duration );
		*ofs<<"第"<<i<<"次希爾排序:\n " <<"		Time:	" << duration <<  " seconds\n";
		
		//插入排序
		for( k =0; k <size;k++)
		{
			a[k] = 	b[k];
		}
		start = clock();
		InsertionSort (a,0,size-1);
		finish = clock();
		//	printArray(a,size);
		
		duration = (double)(finish - start) / CLOCKS_PER_SEC;
		printf( "%s%f seconds\n", "插入排序:",duration );
		*ofs<<"第"<<i<<"次插入排序:\n " <<"		Time:	" << duration <<  " seconds\n";
		//冒泡排序
		for( k =0; k <size;k++)
		{
			a[k] = 	b[k];
		}
		start = clock();
		BubbleSort(a,size);
		finish = clock();
		//	printArray(a,size);
		
		duration = (double)(finish - start) / CLOCKS_PER_SEC;
		printf( "%s%f seconds\n", "冒泡排序:",duration );
		*ofs<<"第"<<i<<"次冒泡排序:\n " <<"		Time:	" << duration <<  " seconds\n";
		ofs->close();
		}
		return 0;
}
void printArray( const int Array[], const int arraySize )
{
	for( int i = 0; i < arraySize; i++ ) {
		cout << Array[ i ] << "   ";
		if ( i % 20 == 19 )
			cout << endl;
	}
	cout << endl;
}

排序算法性能仿真:

排序內容:從0~999中隨機產生,共100000 個整數,該表中單位為秒。

次數 計數排序 基數排序 堆排序 快速排序 希爾排序 直接插入排序 冒泡排序
1 0.0000 0.0310 0.0470 0.0470 0.0310 14.7970 58.0930
2 0.0000 0.0470 0.0310 0.0470 0.0470 16.2500 53.3280
3 0.0000 0.0310 0.0310 0.0310 0.0310 14.4850 62.4380
4 0.0000 0.0320 0.0320 0.0470 0.0310 17.1090 61.8440
5 0.0000 0.0310 0.0470 0.0470 0.0310 16.9380 62.3280
6 0.0000 0.0310 0.0310 0.0470 0.0310 16.9380 57.7030
7 0.0000 0.0310 0.0470 0.0310 0.0310 16.8750 61.9380
8 0.0150 0.0470 0.0310 0.0470 0.0320 17.3910 62.8600
9 0.0000 0.0320 0.0470 0.0460 0.0310 16.9530 62.2660
10 0.0000 0.0470 0.0310 0.0470 0.0310 17.0160 60.1410
11 0.0000 0.0930 0.0780 0.0320 0.0310 14.6090 54.6570
12 0.0000 0.0310 0.0320 0.0310 0.0310 15.0940 62.3430
13 0.0000 0.0310 0.0310 0.0470 0.0310 17.2340 61.9530
14 0.0000 0.0320 0.0470 0.0470 0.0310 16.9060 61.0620
15 0.0000 0.0320 0.0320 0.0460 0.0320 16.7810 62.5310
16 0.0000 0.0470 0.0470 0.0620 0.0310 17.2350 57.1720
17 0.0150 0.0160 0.0320 0.0470 0.0310 14.1400 52.0320
18 0.0150 0.0160 0.0310 0.0310 0.0310 14.1100 52.3590
19 0.0000 0.0310 0.0320 0.0460 0.0320 14.1090 51.8750
20 0.0000 0.0310 0.0320 0.0460 0.0320 14.0780 52.4840
21 0.0150 0.0780 0.0470 0.0470 0.0310 16.3750 59.5150
22 0.0000 0.0310 0.0310 0.0470 0.0320 16.8900 60.3440
23 0.0000 0.0310 0.0310 0.0310 0.0310 16.3440 60.0930
24 0.0000 0.0310 0.0310 0.0470 0.0310 16.3440 60.5780
25 0.0000 0.0320 0.0470 0.0470 0.0470 16.3590 59.7810
26 0.0160 0.0470 0.0310 0.0470 0.0310 16.1250 61.0620
27 0.0000 0.0310 0.0470 0.0470 0.0310 16.7810 59.6100
28 0.0150 0.0320 0.0320 0.0470 0.0310 16.9220 56.8130
29 0.0000 0.0310 0.0310 0.0310 0.0310 15.0790 57.8120
30 0.0000 0.0310 0.0320 0.0460 0.0320 14.7810 58.8280
31 0.0000 0.0310 0.0310 0.0470 0.0310 15.8590 59.1400
32 0.0000 0.0470 0.0320 0.0310 0.0310 16.0940 59.1560
33 0.0000 0.0470 0.0310 0.0310 0.0310 15.9850 59.1400
34 0.0000 0.0310 0.0310 0.0470 0.0320 16.0150 59.2500
35 0.0000 0.0310 0.0470 0.0470 0.0310 16.7660 57.9840
36 0.0000 0.0310 0.0320 0.0470 0.0310 15.3750 59.0470
37 0.0000 0.0320 0.0460 0.0470 0.0320 16.0310 58.9060
38 0.0000 0.0310 0.0310 0.0470 0.0310 15.9530 57.2650
39 0.0160 0.0310 0.0470 0.0470 0.0310 15.9530 57.5160
40 0.0150 0.0310 0.0320 0.0470 0.0310 14.7030 56.6710
平均值 0.0031 0.0360 0.0372 0.0437 0.0320 15.9946 58.7480
最小值 0.0000 0.0160 0.0310 0.0310 0.0310 14.0780 51.8750
最大值 0.0160 0.0930 0.0780 0.0620 0.0470 17.3910 62.8600

本文地址:http://www.bavugt.tw/librarys/veda/detail/294,歡迎訪問原出處。

不打個分嗎?

轉載隨意,但請帶上本文地址:

http://www.bavugt.tw/librarys/veda/detail/294

如果你認為這篇文章值得更多人閱讀,歡迎使用下面的分享功能。
小提示:您可以按快捷鍵 Ctrl + D,或點此 加入收藏

大家都在看

閱讀一百本計算機著作吧,少年

很多人覺得自己技術進步很慢,學習效率低,我覺得一個重要原因是看的書少了。多少是多呢?起碼得看3、4、5、6米吧。給個具體的數量,那就100本書吧。很多人知識結構不好而且不系統,因為在特定領域有一個足夠量的知識量+足夠良好的知識結構,系統化以后就足以應對大量未曾遇到過的問題。

奉勸自學者:構建特定領域的知識結構體系的路徑中再也沒有比學習該專業的專業課程更好的了。如果我的知識結構體系足以囊括面試官的大部分甚至吞并他的知識結構體系的話,讀到他言語中的一個詞我們就已經知道他要表達什么,我們可以讓他坐“上位”畢竟他是面試官,但是在知識結構體系以及心理上我們就居高臨下。

所以,閱讀一百本計算機著作吧,少年!

《php和mysql web開發(原書第4版)》 Luke Welling (作者), Laura Thomson (作者), 武欣 (譯者)

《php和mysql web開發(原書第4版)》將PHP開發與MySQL應用相結合,分別對PHP和MySQL做了深入淺出的分析,不僅介紹PHP和MySQL的一般概念,而且對PHP和MySQL的Web應用做了較全面的闡述,并包括幾個經典且實用的例子。《php和mysql web開發(原書第4版)》是第4版,經過了全面的更新、重寫和擴展,包括PHP 5.3最新改進的特性(例如,更好的錯誤和異常處理),MySQL的存儲過程和存儲引擎,Ajax技術與Web 2.0以及Web應用需要注意的安全問題。

更多計算機寶庫...

有极速快乐十分吗
广东11选5任5遗 新疆11选5开奖直 江苏快3推荐和值 江苏十一选五遗漏号 英超足球赛程 期货配资平台靠谱天牛宝在行 江苏11选5任五遗 伊利股票涨跌 平安银行股票分析论文 中国股市