用C语言编写快速排序和随机化快排,.随机产生数据存入数组,任意选择一种排序算法对待排序列进行排序,生成有序序列;
时间: 2023-07-05 20:29:06 浏览: 98
好的,我可以帮你解答这个问题。首先,我来介绍一下快速排序算法。
快速排序是一种基于分治思想的排序算法,它的基本思路是:选择一个基准元素,将待排序序列分成两个子序列,小于基准元素的放在左边,大于基准元素的放在右边,然后对两个子序列递归进行快速排序,直到子序列的长度为1或0时停止递归。
下面是C语言实现快速排序的代码:
```c
/* 快速排序 */
void quick_sort(int arr[], int left, int right) {
int i, j, pivot;
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); // 对右子序列递归排序
}
}
```
接下来,我来介绍一下随机化快排算法。
随机化快排是在快速排序算法的基础上加入了随机选择基准元素的步骤,其目的是为了避免快速排序在某些特殊情况下时间复杂度退化为O(n^2),例如待排序序列已经有序或者基本有序。
下面是C语言实现随机化快排的代码:
```c
/* 随机化快速排序 */
void random_quick_sort(int arr[], int left, int right) {
int i, j, pivot, rand_index;
if (left < right) {
i = left;
j = right;
rand_index = rand() % (right - left + 1) + left; // 随机选择基准元素
pivot = arr[rand_index];
arr[rand_index] = arr[left];
arr[left] = pivot;
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;
random_quick_sort(arr, left, i - 1); // 对左子序列递归排序
random_quick_sort(arr, i + 1, right); // 对右子序列递归排序
}
}
```
在上面的代码中,我们使用了rand()函数来随机选择基准元素的下标。另外,为了方便起见,我们将随机选择的基准元素放到了序列的最左边。
最后,我们可以用以下代码来测试快速排序和随机化快排:
```c
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
/* 快速排序 */
void quick_sort(int arr[], int left, int right) {
// ...
}
/* 随机化快速排序 */
void random_quick_sort(int arr[], int left, int right) {
// ...
}
/* 打印数组 */
void print_array(int arr[], int len) {
int i;
for (i = 0; i < len; i++)
printf("%d ", arr[i]);
printf("\n");
}
int main() {
int arr[10], i;
srand((unsigned)time(NULL)); // 初始化随机数种子
for (i = 0; i < 10; i++)
arr[i] = rand() % 100; // 随机产生0~99之间的数
printf("原始序列:");
print_array(arr, 10);
random_quick_sort(arr, 0, 9); // 任意选择一种排序算法进行排序
printf("排序后序列:");
print_array(arr, 10);
return 0;
}
```
在上面的代码中,我们使用srand()函数初始化了随机数种子,然后用rand()函数产生了10个0~99之间的随机数存入了数组arr中,并打印了原始序列。接着,我们任意选择了随机化快排算法对序列进行排序,并打印了排序后的序列。
阅读全文