c++实现 数组合并与排序
时间: 2023-10-20 09:18:11 浏览: 48
下面是C++实现的数组合并与排序的示例代码:
```cpp
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
int arr1[5] = {1, 3, 5, 7, 9};
int arr2[5] = {2, 4, 6, 8, 10};
int arr3[10];
// 合并数组
merge(arr1, arr1 + 5, arr2, arr2 + 5, arr3);
// 排序数组
sort(arr3, arr3 + 10);
// 输出结果
for(int i = 0; i < 10; i++)
cout << arr3[i] << " ";
return 0;
}
```
首先定义两个数组arr1和arr2,分别存储5个有序的整数。然后定义一个大小为10的新数组arr3,用于存储合并后的数组。使用`merge`函数将arr1和arr2合并到arr3中,并使用`sort`函数对arr3进行排序。最后输出数组arr3的元素。
相关问题
pthread线程池实现快速排序并计时 c++
好的,这是一个比较复杂的问题,需要分步骤来回答。
首先,我们需要实现一个基本的快速排序算法,可以用以下的代码实现:
```c
void quick_sort(int *arr, int left, int right){
int i, j, pivot, temp;
if(left < right){
i = left;
j = right;
pivot = arr[left];
while(i < j){
while(i < j && arr[j] >= pivot)
j--;
if(i < j)
arr[i++] = arr[j];
while(i < j && arr[i] < pivot)
i++;
if(i < j)
arr[j--] = arr[i];
}
arr[i] = pivot;
quick_sort(arr, left, i - 1);
quick_sort(arr, i + 1, right);
}
}
```
接下来,我们需要实现一个线程池。这里我们使用pthread库实现。以下是线程池的代码:
```c
typedef struct{
int *arr;
int left;
int right;
} Task;
typedef struct{
Task *task_queue;
int queue_head;
int queue_tail;
int queue_size;
pthread_mutex_t queue_lock;
pthread_cond_t queue_not_empty;
pthread_cond_t queue_not_full;
pthread_t *threads;
int thread_count;
int is_shutdown;
} ThreadPool;
void thread_pool_init(ThreadPool *pool, int thread_count, int queue_size){
pool->thread_count = thread_count;
pool->queue_size = queue_size;
pool->queue_head = pool->queue_tail = 0;
pool->is_shutdown = 0;
pool->threads = (pthread_t *)malloc(sizeof(pthread_t) * thread_count);
pool->task_queue = (Task *)malloc(sizeof(Task) * queue_size);
pthread_mutex_init(&(pool->queue_lock), NULL);
pthread_cond_init(&(pool->queue_not_empty), NULL);
pthread_cond_init(&(pool->queue_not_full), NULL);
for(int i = 0; i < thread_count; i++)
pthread_create(&(pool->threads[i]), NULL, thread_func, (void *)pool);
}
void thread_pool_add_task(ThreadPool *pool, Task task){
pthread_mutex_lock(&(pool->queue_lock));
while((pool->queue_tail + 1) % pool->queue_size == pool->queue_head){
pthread_cond_wait(&(pool->queue_not_full), &(pool->queue_lock));
}
pool->task_queue[pool->queue_tail] = task;
pool->queue_tail = (pool->queue_tail + 1) % pool->queue_size;
pthread_cond_signal(&(pool->queue_not_empty));
pthread_mutex_unlock(&(pool->queue_lock));
}
void thread_pool_shutdown(ThreadPool *pool){
pthread_mutex_lock(&(pool->queue_lock));
pool->is_shutdown = 1;
pthread_cond_broadcast(&(pool->queue_not_empty));
pthread_mutex_unlock(&(pool->queue_lock));
for(int i = 0; i < pool->thread_count; i++)
pthread_join(pool->threads[i], NULL);
free(pool->threads);
free(pool->task_queue);
pthread_mutex_destroy(&(pool->queue_lock));
pthread_cond_destroy(&(pool->queue_not_empty));
pthread_cond_destroy(&(pool->queue_not_full));
}
void *thread_func(void *arg){
ThreadPool *pool = (ThreadPool *)arg;
Task task;
while(1){
pthread_mutex_lock(&(pool->queue_lock));
while(pool->queue_head == pool->queue_tail && !pool->is_shutdown){
pthread_cond_wait(&(pool->queue_not_empty), &(pool->queue_lock));
}
if(pool->is_shutdown){
pthread_mutex_unlock(&(pool->queue_lock));
pthread_exit(NULL);
}
task = pool->task_queue[pool->queue_head];
pool->queue_head = (pool->queue_head + 1) % pool->queue_size;
pthread_cond_signal(&(pool->queue_not_full));
pthread_mutex_unlock(&(pool->queue_lock));
quick_sort(task.arr, task.left, task.right);
}
}
```
最后,我们需要实现计时功能。可以用以下代码实现:
```c
#include <sys/time.h>
double get_time(){
struct timeval tv;
gettimeofday(&tv, NULL);
return tv.tv_sec + tv.tv_usec / 1000000.0;
}
```
现在我们需要将这些代码组合起来,实现一个快速排序的线程池,并计时。以下是完整的代码:
```c
#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <sys/time.h>
typedef struct{
int *arr;
int left;
int right;
} Task;
typedef struct{
Task *task_queue;
int queue_head;
int queue_tail;
int queue_size;
pthread_mutex_t queue_lock;
pthread_cond_t queue_not_empty;
pthread_cond_t queue_not_full;
pthread_t *threads;
int thread_count;
int is_shutdown;
} ThreadPool;
void quick_sort(int *arr, int left, int right){
int i, j, pivot, temp;
if(left < right){
i = left;
j = right;
pivot = arr[left];
while(i < j){
while(i < j && arr[j] >= pivot)
j--;
if(i < j)
arr[i++] = arr[j];
while(i < j && arr[i] < pivot)
i++;
if(i < j)
arr[j--] = arr[i];
}
arr[i] = pivot;
quick_sort(arr, left, i - 1);
quick_sort(arr, i + 1, right);
}
}
void thread_pool_init(ThreadPool *pool, int thread_count, int queue_size){
pool->thread_count = thread_count;
pool->queue_size = queue_size;
pool->queue_head = pool->queue_tail = 0;
pool->is_shutdown = 0;
pool->threads = (pthread_t *)malloc(sizeof(pthread_t) * thread_count);
pool->task_queue = (Task *)malloc(sizeof(Task) * queue_size);
pthread_mutex_init(&(pool->queue_lock), NULL);
pthread_cond_init(&(pool->queue_not_empty), NULL);
pthread_cond_init(&(pool->queue_not_full), NULL);
for(int i = 0; i < thread_count; i++)
pthread_create(&(pool->threads[i]), NULL, thread_func, (void *)pool);
}
void thread_pool_add_task(ThreadPool *pool, Task task){
pthread_mutex_lock(&(pool->queue_lock));
while((pool->queue_tail + 1) % pool->queue_size == pool->queue_head){
pthread_cond_wait(&(pool->queue_not_full), &(pool->queue_lock));
}
pool->task_queue[pool->queue_tail] = task;
pool->queue_tail = (pool->queue_tail + 1) % pool->queue_size;
pthread_cond_signal(&(pool->queue_not_empty));
pthread_mutex_unlock(&(pool->queue_lock));
}
void thread_pool_shutdown(ThreadPool *pool){
pthread_mutex_lock(&(pool->queue_lock));
pool->is_shutdown = 1;
pthread_cond_broadcast(&(pool->queue_not_empty));
pthread_mutex_unlock(&(pool->queue_lock));
for(int i = 0; i < pool->thread_count; i++)
pthread_join(pool->threads[i], NULL);
free(pool->threads);
free(pool->task_queue);
pthread_mutex_destroy(&(pool->queue_lock));
pthread_cond_destroy(&(pool->queue_not_empty));
pthread_cond_destroy(&(pool->queue_not_full));
}
void *thread_func(void *arg){
ThreadPool *pool = (ThreadPool *)arg;
Task task;
while(1){
pthread_mutex_lock(&(pool->queue_lock));
while(pool->queue_head == pool->queue_tail && !pool->is_shutdown){
pthread_cond_wait(&(pool->queue_not_empty), &(pool->queue_lock));
}
if(pool->is_shutdown){
pthread_mutex_unlock(&(pool->queue_lock));
pthread_exit(NULL);
}
task = pool->task_queue[pool->queue_head];
pool->queue_head = (pool->queue_head + 1) % pool->queue_size;
pthread_cond_signal(&(pool->queue_not_full));
pthread_mutex_unlock(&(pool->queue_lock));
quick_sort(task.arr, task.left, task.right);
}
}
double get_time(){
struct timeval tv;
gettimeofday(&tv, NULL);
return tv.tv_sec + tv.tv_usec / 1000000.0;
}
int main(){
int arr[1000000];
for(int i = 0; i < 1000000; i++)
arr[i] = rand() % 1000000;
ThreadPool pool;
thread_pool_init(&pool, 4, 10000);
double start_time = get_time();
Task task;
task.arr = arr;
task.left = 0;
task.right = 999999;
thread_pool_add_task(&pool, task);
thread_pool_shutdown(&pool);
double end_time = get_time();
printf("Time: %lf\n", end_time - start_time);
return 0;
}
```
运行程序,可以看到输出的时间,就是快速排序的时间。注意,线程池的线程数和任务队列大小可以根据自己的需求进行调整。
c++实现归并排序
归并排序是一种基于分治思想的经典排序算法,其时间复杂度为O(nlogn)。下面是C++实现归并排序的代码:
```c++
#include <iostream>
using namespace std;
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);
}
}
int main() {
int arr[] = { 12, 11, 13, 5, 6, 7 };
int arr_size = sizeof(arr) / sizeof(arr[0]);
mergeSort(arr, 0, arr_size - 1);
for (int i = 0; i < arr_size; i++)
cout << arr[i] << " ";
cout << endl;
return 0;
}
```
在这个代码中,`merge()`函数将两个已排序的子数组合并成一个子数组。`mergeSort()`函数使用递归的方式将数组分成两半,直到每个子数组的长度为1,然后调用`merge()`函数将它们合并成一个已排序的数组。最后,`main()`函数初始化一个数组并调用`mergeSort()`函数对其进行排序。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)