用C++实现数组{6,2,3,1,7,4,8,9}的快速排序,归并排序和堆排序
时间: 2023-10-09 17:09:47 浏览: 90
用c++实现的快速排序
好的,我可以回答你的问题。以下是用 C 语言实现给定数组的快速排序、归并排序和堆排序的代码:
1. 快速排序
// 数组快速排序函数
void quicksort(int arr[], int left, int right){
int i = left, j = right;
int pivot = arr[(left + right) / 2]; // 以中间数作为基准
int temp;
while (i <= j) {
while (arr[i] < pivot) i++;
while (arr[j] > pivot) j--;
if (i <= j) {
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
j--;
}
}
if (left < j) quicksort(arr, left, j); // 递归排序左半部分
if (i < right) quicksort(arr, i, right); // 递归排序右半部分
}
// 测试代码
int arr[] = {6,2,3,1,7,4,8,9};
int len = sizeof(arr) / sizeof(int); // 数组长度
quicksort(arr, 0, len - 1);
for (int i = 0; i < len; i++){
printf("%d ", arr[i]);
}
2. 归并排序
// 合并数组的函数
void merge(int arr[], int left, int middle, int right){
int len = right - left + 1; // 要合并的数组长度
int temp[len]; // 分配临时数组
int i = left, j = middle + 1, k = 0;
while (i <= middle && j <= right){ // 合并两个已排好序的子数组
if (arr[i] <= arr[j]){
temp[k] = arr[i];
i++;
} else {
temp[k] = arr[j];
j++;
}
k++;
}
while (i <= middle){ // 处理剩余元素
temp[k] = arr[i];
i++;
k++;
}
while (j <= right){ // 处理剩余元素
temp[k] = arr[j];
j++;
k++;
}
for (k = 0; k < len; k++){ // 将临时数组复制回原数组
arr[left + k] = temp[k];
}
}
// 归并排序函数
void mergesort(int arr[], int left, int right){
if (left < right){
int middle = (left + right) / 2; // 分割数组
mergesort(arr, left, middle); // 递归排序左半部分
mergesort(arr, middle + 1, right); // 递归排序右半部分
merge(arr, left, middle, right); // 合并已排序的两个子数组
}
}
// 测试代码
int arr[] = {6,2,3,1,7,4,8,9};
int len = sizeof(arr) / sizeof(int); // 数组长度
mergesort(arr, 0, len - 1);
for (int i = 0; i < len; i++){
printf("%d ", arr[i]);
}
3. 堆排序
// 建立大根堆
void build_max_heap(int arr[], int len){
for (int i = len / 2 - 1; i >= 0; i--){ // 从最后一个非叶子节点开始向上构造堆
int parent = i;
int child = 2 * parent + 1;
while (child < len){ // 子节点下标不超出堆的范围
if (child + 1 < len && arr[child] < arr[child+1]){ // 如果有两个子节点且右子节点比左子节点大
child++;
}
if (arr[parent] >= arr[child]){ // 父节点已经比子节点大
break;
} else { // 父节点比子节点小,交换父子节点
int temp = arr[parent];
arr[parent] = arr[child];
arr[child] = temp;
parent = child;
child = 2 * parent + 1;
}
}
}
}
// 堆排序函数
void heapsort(int arr[], int len){
build_max_heap(arr, len); // 建立大根堆
for (int i = len - 1; i > 0; i--){ // 从最后一个元素开始向前调整堆
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
build_max_heap(arr, i); // 再次建堆
}
}
// 测试代码
int arr[] = {6,2,3,1,7,4,8,9};
int len = sizeof(arr) / sizeof(int); // 数组长度
heapsort(arr, len);
for (int i = 0; i < len; i++){
printf("%d ", arr[i]);
}
阅读全文