2023-03-29 17:18:54
浏览数 (1)
一、代码
代码语言：c
复制#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/timeb.h>
#include <time.h>
using namespace std;
#define MAXLENGTH 100000
long getSystemTime()
{
struct timeb tb;
ftime(&tb);
return tb.time * 1000 tb.millitm;
}
//交换函数
void swapData(int* a, int* b)
{
int temp = *a;
*a = *b;
*b = temp;
}
//打印函数
void PrintArray(int arr[], int length)
{
for (int i = 0; i < length; i )
{
cout << arr[i] << " ";
}
cout << endl;
}
//冒泡排序改进版本
int flag = 0; //表示没有排序好
void BubbleSortFaster(int arr[], int length)
{
for (int i = 0; i < length - 1 && flag == 0; i )
{
flag = 1; //认为已经排序好
for (int j = 0; j < length - 1 - i; j )
{
if (arr[j] > arr[j 1])
{
flag = 0;
swapData(&arr[j], &arr[j 1]);
}
}
}
}
//选择排序
void SelectSort(int arr[], int length)
{
for (int i = 0; i < length; i )
{
int min = i;
for (int j = i 1; j < length; j )
{
if (arr[j] < arr[min])
{
min = j;
}
}
if (min != i)
{
swapData(&arr[min], &arr[i]);
}
}
}
//插入排序
void InsertSort(int arr[], int length)
{
int j;
for (int i = 1; i < length; i )
{
if (arr[i] < arr[i - 1])
{
int temp = arr[i];
for (j = i - 1; j >= 0 && temp < arr[j]; j--)
{
arr[j 1] = arr[j];
}
arr[j 1] = temp;
}
}
}
//希尔排序
//从小到大
void ShellSort(int arr[], int length)
{
int increasement = length;
int i, j, k;
do
{
//确定分组的增量
increasement = increasement / 3 1;
for (i = 0; i < increasement; i )
{
for (j = i increasement; j < length; j =increasement)
{
if (arr[j]<arr[j-increasement])
{
int temp = arr[j];
for ( k = j-increasement; k >=0 && temp<arr[k]; k-=increasement)
{
arr[k increasement] = arr[k];
}
arr[k increasement] = temp;
}
}
}
} while (increasement>1);
}
//从小到大排序
int main()
{
int arr[MAXLENGTH];
int arr2[MAXLENGTH];
srand((unsigned int)time(NULL));
for (int i = 0; i < MAXLENGTH; i )
{
int numtemp = rand() % MAXLENGTH;
arr[i] = numtemp;
arr2[i] = numtemp;
}
//PrintArray(arr, MAXLENGTH);
//InsertSort(arr, MAXLENGTH);
long tshell_start = getSystemTime();
ShellSort(arr, MAXLENGTH);
long tshell_end = getSystemTime();
cout << "希尔排序" << MAXLENGTH << "个元素所需时间：" << (tshell_end - tshell_start)<<"n";
//PrintArray(arr, MAXLENGTH);
long tinsert_start = getSystemTime();
InsertSort(arr2, MAXLENGTH);
long tinsert_end = getSystemTime();
cout << "插入排序" << MAXLENGTH << "个元素所需时间：" << (tinsert_end - tinsert_start)<<"n";
return 0;
}
二、运行结果
三、算法就是生产力！
