用c++语言写一个排序程序,采用随机数发生器产生待排序整型数据,值的范围在0到n*10之间,排序表函包括直接插入排序函数,冒泡排序函数,快速排序函数,直接选择排序函数,筛选函数,对排序函数,归并排序函数。并显示出排序时间
时间: 2023-08-14 17:05:39 浏览: 108
以下是一个使用C++编写的排序程序,包括所需的六个排序算法和计时功能:
```c++
#include <iostream>
#include <cstdlib>
#include <ctime>
#include <chrono>
using namespace std;
void insertionSort(int arr[], int n)
{
int i, key, j;
for (i = 1; i < n; i++)
{
key = arr[i];
j = i - 1;
while (j >= 0 && arr[j] > key)
{
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}
void bubbleSort(int arr[], int n)
{
int i, j;
for (i = 0; i < n-1; i++)
{
for (j = 0; j < n-i-1; j++)
{
if (arr[j] > arr[j+1])
{
swap(arr[j], arr[j+1]);
}
}
}
}
int partition(int arr[], int low, int high)
{
int pivot = arr[high];
int i = (low - 1);
for (int j = low; j <= high- 1; j++)
{
if (arr[j] <= pivot)
{
i++;
swap(arr[i], arr[j]);
}
}
swap(arr[i + 1], arr[high]);
return (i + 1);
}
void quickSort(int arr[], int low, int high)
{
if (low < high)
{
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
void selectionSort(int arr[], int n)
{
int i, j, min_idx;
for (i = 0; i < n-1; i++)
{
min_idx = i;
for (j = i+1; j < n; j++)
{
if (arr[j] < arr[min_idx])
{
min_idx = j;
}
}
swap(arr[min_idx], arr[i]);
}
}
void heapify(int arr[], int n, int i)
{
int largest = i;
int l = 2*i + 1;
int r = 2*i + 2;
if (l < n && arr[l] > arr[largest])
{
largest = l;
}
if (r < n && arr[r] > arr[largest])
{
largest = r;
}
if (largest != i)
{
swap(arr[i], arr[largest]);
heapify(arr, n, largest);
}
}
void heapSort(int arr[], int n)
{
for (int i = n / 2 - 1; i >= 0; i--)
{
heapify(arr, n, i);
}
for (int i = n - 1; i >= 0; i--)
{
swap(arr[0], arr[i]);
heapify(arr, i, 0);
}
}
void merge(int arr[], int l, int m, int r)
{
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;
int L[n1], R[n2];
for (i = 0; i < n1; i++)
{
L[i] = arr[l + i];
}
for (j = 0; j < n2; j++)
{
R[j] = arr[m + 1+ j];
}
i = 0;
j = 0;
k = l;
while (i < n1 && j < n2)
{
if (L[i] <= R[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
j++;
}
k++;
}
while (i < n1)
{
arr[k] = L[i];
i++;
k++;
}
while (j < n2)
{
arr[k] = R[j];
j++;
k++;
}
}
void mergeSort(int arr[], int l, int r)
{
if (l < r)
{
int m = l+(r-l)/2;
mergeSort(arr, l, m);
mergeSort(arr, m+1, r);
merge(arr, l, m, r);
}
}
void printArray(int arr[], int n)
{
for (int i=0; i < n; i++)
{
cout << arr[i] << " ";
}
cout << endl;
}
int main()
{
int n = 10000;
int arr[n];
srand(time(NULL));
for (int i=0; i<n; i++)
{
arr[i] = rand() % (n*10);
}
auto start = chrono::high_resolution_clock::now();
insertionSort(arr, n);
auto end = chrono::high_resolution_clock::now();
cout << "Insertion sort: " << chrono::duration_cast<chrono::microseconds>(end - start).count() << " microseconds" << endl;
start = chrono::high_resolution_clock::now();
bubbleSort(arr, n);
end = chrono::high_resolution_clock::now();
cout << "Bubble sort: " << chrono::duration_cast<chrono::microseconds>(end - start).count() << " microseconds" << endl;
start = chrono::high_resolution_clock::now();
quickSort(arr, 0, n-1);
end = chrono::high_resolution_clock::now();
cout << "Quick sort: " << chrono::duration_cast<chrono::microseconds>(end - start).count() << " microseconds" << endl;
start = chrono::high_resolution_clock::now();
selectionSort(arr, n);
end = chrono::high_resolution_clock::now();
cout << "Selection sort: " << chrono::duration_cast<chrono::microseconds>(end - start).count() << " microseconds" << endl;
start = chrono::high_resolution_clock::now();
heapSort(arr, n);
end = chrono::high_resolution_clock::now();
cout << "Heap sort: " << chrono::duration_cast<chrono::microseconds>(end - start).count() << " microseconds" << endl;
start = chrono::high_resolution_clock::now();
mergeSort(arr, 0, n-1);
end = chrono::high_resolution_clock::now();
cout << "Merge sort: " << chrono::duration_cast<chrono::microseconds>(end - start).count() << " microseconds" << endl;
return 0;
}
```
这里使用了C++11中的`chrono`库来计时。程序中首先生成了一个长度为10000的整型数组,然后分别调用六个排序算法对其进行排序,并输出排序所需的时间。
阅读全文