95 lines
2.3 KiB
C++
95 lines
2.3 KiB
C++
//
|
|
// Created by grtsinry43 on 5/8/25.
|
|
//
|
|
|
|
#include "problem3.h"
|
|
|
|
#include <vector>
|
|
#include <iostream>
|
|
#include <random>
|
|
#include <ctime>
|
|
|
|
int partition(std::vector<int> &arr, int low, int high) {
|
|
int pivot = arr[high];
|
|
int i = low - 1;
|
|
for (int j = low; j < high; j++) {
|
|
if (arr[j] <= pivot) {
|
|
i++;
|
|
std::swap(arr[i], arr[j]);
|
|
}
|
|
}
|
|
std::swap(arr[i + 1], arr[high]);
|
|
return i + 1;
|
|
}
|
|
|
|
void quick_sort(std::vector<int> &arr, int low, int high) {
|
|
if (low < high) {
|
|
int pivot = partition(arr, low, high);
|
|
quick_sort(arr, low, pivot - 1);
|
|
quick_sort(arr, pivot + 1, high);
|
|
}
|
|
}
|
|
|
|
void select_sort(std::vector<int> &arr) {
|
|
for (size_t i = 0; i < arr.size() - 1; i++) {
|
|
size_t min_index = i;
|
|
for (size_t j = i + 1; j < arr.size(); j++) {
|
|
if (arr[j] < arr[min_index]) {
|
|
min_index = j;
|
|
}
|
|
}
|
|
std::swap(arr[i], arr[min_index]);
|
|
}
|
|
}
|
|
|
|
void insert_sort(std::vector<int> &arr) {
|
|
for (int i = 0; i < arr.size(); ++i) {
|
|
int key = arr[i];
|
|
int j = i - 1;
|
|
while (j >= 0 && arr[j] > key) {
|
|
arr[j + 1] = arr[j];
|
|
j--;
|
|
}
|
|
arr[j + 1] = key;
|
|
}
|
|
}
|
|
|
|
std::vector<int> generate_random_array(int size) {
|
|
std::vector<int> arr(size);
|
|
for (int i = 0; i < size; ++i) {
|
|
arr[i] = random() % 10000; // 范围给一个0-9999吧
|
|
}
|
|
return arr;
|
|
}
|
|
|
|
int problem_3() {
|
|
int size = 10000;
|
|
std::vector<int> arr = generate_random_array(size);
|
|
std::vector<int> arr_copy = arr;
|
|
std::vector<int> arr_copy2 = arr;
|
|
// 快速排序
|
|
clock_t start, end;
|
|
start = clock();
|
|
quick_sort(arr, 0, arr.size() - 1);
|
|
end = clock();
|
|
double quick_sort_time = double(end - start) / CLOCKS_PER_SEC;
|
|
std::cout << "Quick Sort Time: " << quick_sort_time << " seconds\n";
|
|
|
|
// 选择排序
|
|
start = clock();
|
|
select_sort(arr_copy);
|
|
end = clock();
|
|
double select_sort_time = double(end - start) / CLOCKS_PER_SEC;
|
|
std::cout << "Select Sort Time: " << select_sort_time << " seconds\n";
|
|
|
|
// 插入排序
|
|
start = clock();
|
|
insert_sort(arr_copy2);
|
|
end = clock();
|
|
double insert_sort_time = double(end - start) / CLOCKS_PER_SEC;
|
|
std::cout << "Insert Sort Time: " << insert_sort_time << " seconds\n";
|
|
|
|
|
|
return 0;
|
|
}
|