用C++写一个算法,求数组中的第i小元素,数组随机生成,用两种方法实现
时间: 2023-05-29 20:04:59 浏览: 87
09_调用函数实现冒泡排序.rar
5星 · 资源好评率100%
方法一:冒泡排序+直接读取
1. 冒泡排序,将数组从小到大排序
2. 直接读取第i个元素即为第i小元素
代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define SIZE 10
void generateArray(int arr[], int size);
void bubbleSort(int arr[], int size);
void printArray(int arr[], int size);
int findIthSmallest(int arr[], int size, int i);
int main() {
int arr[SIZE];
generateArray(arr, SIZE);
printf("Original array:\n");
printArray(arr, SIZE);
bubbleSort(arr, SIZE);
printf("After sorting:\n");
printArray(arr, SIZE);
int i = 3; // 第3小元素
int ithSmallest = findIthSmallest(arr, SIZE, i);
printf("The %dth smallest element is: %d\n", i, ithSmallest);
return 0;
}
void generateArray(int arr[], int size) {
srand(time(NULL));
for (int i = 0; i < size; i++) {
arr[i] = rand() % 100 + 1;
}
}
void bubbleSort(int arr[], int size) {
for (int i = 0; i < size - 1; i++) {
for (int j = 0; j < size - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
int findIthSmallest(int arr[], int size, int i) {
if (i <= 0 || i > size) {
printf("Invalid input!\n");
return -1;
}
return arr[i - 1];
}
```
方法二:快速排序
1. 快速排序,将数组从小到大排序
2. 直接读取第i个元素即为第i小元素
代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define SIZE 10
void generateArray(int arr[], int size);
void quickSort(int arr[], int left, int right);
int partition(int arr[], int left, int right);
void printArray(int arr[], int size);
int findIthSmallest(int arr[], int size, int i);
int main() {
int arr[SIZE];
generateArray(arr, SIZE);
printf("Original array:\n");
printArray(arr, SIZE);
quickSort(arr, 0, SIZE - 1);
printf("After sorting:\n");
printArray(arr, SIZE);
int i = 3; // 第3小元素
int ithSmallest = findIthSmallest(arr, SIZE, i);
printf("The %dth smallest element is: %d\n", i, ithSmallest);
return 0;
}
void generateArray(int arr[], int size) {
srand(time(NULL));
for (int i = 0; i < size; i++) {
arr[i] = rand() % 100 + 1;
}
}
void quickSort(int arr[], int left, int right) {
if (left < right) {
int pivotIndex = partition(arr, left, right);
quickSort(arr, left, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, right);
}
}
int partition(int arr[], int left, int right) {
int pivot = arr[left];
int i = left + 1;
int j = right;
while (i <= j) {
while (i <= j && arr[i] <= pivot) {
i++;
}
while (i <= j && arr[j] > pivot) {
j--;
}
if (i < j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
int temp = arr[left];
arr[left] = arr[j];
arr[j] = temp;
return j;
}
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
int findIthSmallest(int arr[], int size, int i) {
if (i <= 0 || i > size) {
printf("Invalid input!\n");
return -1;
}
return arr[i - 1];
}
```
阅读全文