「4个排序对比之结果及评价」

4个排序对比之结果及评价

板块灌水区
楼主lizesheng520
当前回复5
已保存回复5
发布时间2024/10/13 10:19
上次更新2024/10/13 12:11:05

被骇客银狼阻止的越权访问保存失败

4个排序对比之结果及评价

lizesheng520楼主2024/10/13 10:19

勇敢勇敢我的冒泡~

	std::sort()	bubble	insert	shell
time1	16.5822ms	51228.3ms	6731.83ms	20.7231ms
time2	16.4295ms	70814.4ms	10497.3ms	19.5011ms
time3	16.4111ms	50867.1ms	7738.26ms	21.5137ms
time4	16.3882ms	50432.3ms	6713.18ms	19.7919ms
time5	17.5525ms	73575.7ms	7763.7ms	19.7787ms
平均	16.6727ms	59383.56ms	7888.854ms	20.2617ms
附代码：

#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <time.h>
#include <windows.h>
#include <assert.h>
using namespace std;

int main(){
	time_t t;
	srand(unsigned(t));
	int a[100000],b[100000];
	for(int i=0;i<100000;i++){
		b[i] = rand() % 2147483647;
	}
	for(int i=0;i<100000;i++){
		a[i]=b[i];
	}
	{
		double time;
		LARGE_INTEGER nFreq;
		LARGE_INTEGER nBeginTime;
		LARGE_INTEGER nEndTime;
		QueryPerformanceFrequency(&nFreq);
		QueryPerformanceCounter(&nBeginTime);
		sort(a,a+100000);
		QueryPerformanceCounter(&nEndTime);
		time = (double)(nEndTime.QuadPart-nBeginTime.QuadPart)/(double)nFreq.QuadPart;
		cout << "std::sort() Time: " << time*1000 << "ms" << endl;
	}
	for(int i=0;i<100000;i++){
		a[i]=b[i];
	}
	{
		double time;
		LARGE_INTEGER nFreq;
		LARGE_INTEGER nBeginTime;
		LARGE_INTEGER nEndTime;
		QueryPerformanceFrequency(&nFreq);
		QueryPerformanceCounter(&nBeginTime);
		for(int i=1;i<100000;i++)
		{
			int x=a[i],j=i-1;
			while(j>=0&&x<a[j]){
				a[j+1]=a[j];
				j--;
			}
			a[j+1]=x;
		}
		QueryPerformanceCounter(&nEndTime);
		time = (double)(nEndTime.QuadPart-nBeginTime.QuadPart)/(double)nFreq.QuadPart;
		cout << "\nInsert Time: " << time*1000 << "ms" << endl;
	}
	for(int i=0;i<100000;i++){
		a[i]=b[i];
	}
	{
		double time;
		LARGE_INTEGER nFreq;
		LARGE_INTEGER nBeginTime;
		LARGE_INTEGER nEndTime;
		QueryPerformanceFrequency(&nFreq);
		QueryPerformanceCounter(&nBeginTime);
		for(int i=0;i<100000-1;i++){
			for(int j=0;j<100000-1-i;j++){
				if(a[j]<a[j+1]){
					swap(a[j],a[j+1]);
				}
			}
		}
		QueryPerformanceCounter(&nEndTime);
		time = (double)(nEndTime.QuadPart-nBeginTime.QuadPart)/(double)nFreq.QuadPart;
		cout << "\nBubble Time: " << time*1000 << "ms" << endl;
	}
	for(int i=0;i<100000;i++){
		a[i]=b[i];
	}
	{
		double time;
		LARGE_INTEGER nFreq;
		LARGE_INTEGER nBeginTime;
		LARGE_INTEGER nEndTime;
		QueryPerformanceFrequency(&nFreq);
		QueryPerformanceCounter(&nBeginTime);
		assert(a);
		int gap = 100000;
		while (gap > 1){
			gap = gap / 3 + 1;
			for (int i = 0; i < 100000 - gap; i++){
				int end = i;
				int x = a[end + gap];
				while (end >= 0){
					if (a[end] > x){
						a[end + gap] = a[end];
						end -= gap;
					} else {
						break;
					}
				}
				a[end + gap] = x;
			}
		}
		QueryPerformanceCounter(&nEndTime);
		time = (double)(nEndTime.QuadPart-nBeginTime.QuadPart)/(double)nFreq.QuadPart;
		cout << "\nShell Time: " << time*1000 << "ms" << endl;
	}
	system("pause");
	return 0;
}

总结：std::sort()<shell<insert<bubble （时间）综上，std::sort() ------ NB!!

2024/10/13 10:19