当前位置：首页 > news >正文

门户网站建设百度文库/百度大数据

news 2025/7/1 12:59:50

门户网站建设百度文库,百度大数据,优秀网络广告案例,视频网站如何做目录 1、冒泡排序 1.1 算法思想 1.2 代码实现方式一：顺序表方式二：链表 2、快速排序 2.1 算法思想 2.2 代码实现 2.3 例题分析 1、冒泡排序 1.1 算法思想冒泡排序是一种简单的排序算法，它的基本思想是从数组的第一个元素开始…

1、冒泡排序

1.1 算法思想

1.2 代码实现

方式一：顺序表

方式二：链表

2、快速排序

2.1 算法思想

2.2 代码实现

2.3 例题分析

1、冒泡排序

1.1 算法思想

冒泡排序是一种简单的排序算法，它的基本思想是从数组的第一个元素开始依次比较相邻的两个元素，根据大小交换它们的位置，直到所有元素都排好序为止。

具体步骤如下：

1. 从数组的第一个元素开始，依次比较相邻的两个元素。

2. 如果前面的元素大于后面的元素，则交换它们的位置。

3. 接着比较下一对相邻元素，重复上述步骤，直到遍历到数组的最后一个元素。

4. 一次遍历过后，最后一个元素一定是当前数组中的最大元素，因此下一次遍历可以排除它。

5. 重复上述步骤，直到所有元素都排好序为止。

冒泡排序的时间复杂度为O(n^2)，不适合处理大规模的数据。但是它实现简单，适用于对小规模数据排序，并且由于其稳定性和可读性，仍然被广泛应用。

1.2 代码实现

方式一：顺序表

以下是C语言实现冒泡排序的代码：

#include <stdio.h>void bubbleSort(int arr[], int n);
void printArray(int arr[], int n);int main()
{int arr[] = {64, 34, 25, 12, 22, 11, 90};int n = sizeof(arr) / sizeof(arr[0]);printf("原始数组：\n");printArray(arr, n);bubbleSort(arr, n);printf("排序后的数组：\n");printArray(arr, n);return 0;
}void bubbleSort(int arr[], int n)
{int i, j, temp;for (i = 0; i < n - 1; i++)    // 外层循环控制轮数{for (j = 0; j < n - i - 1; j++)    // 内层循环控制比较和交换{if (arr[j] > arr[j + 1]){temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}}
}void printArray(int arr[], int n)
{int i;for (i = 0; i < n; i++){printf("%d ", arr[i]);}printf("\n");
}

输出结果：

原始数组：
64 34 25 12 22 11 90 
排序后的数组：
11 12 22 25 34 64 90

方式二：链表

以下是基于链表的冒泡排序的C语言实现代码：

#include <stdio.h>
#include <stdlib.h>struct node {int data;struct node* next;
};void swap(struct node* a, struct node* b) {int temp = a->data;a->data = b->data;b->data = temp;
}void bubbleSort(struct node* head) {int swapped, i;struct node* ptr1;struct node* lptr = NULL;if (head == NULL) {return;}do {swapped = 0;ptr1 = head;while (ptr1->next != lptr) {if (ptr1->data > ptr1->next->data) {swap(ptr1, ptr1->next);swapped = 1;}ptr1 = ptr1->next;}lptr = ptr1;} while (swapped);
}void printList(struct node* head) {struct node* temp = head;while (temp != NULL) {printf("%d ", temp->data);temp = temp->next;}
}void push(struct node** head_ref, int new_data) {struct node* new_node = (struct node*)malloc(sizeof(struct node));new_node->data = new_data;new_node->next = (*head_ref);(*head_ref) = new_node;
}int main() {struct node* head = NULL;push(&head, 5);push(&head, 20);push(&head, 4);push(&head, 3);push(&head, 30);printf("Original Linked List:\n");printList(head);bubbleSort(head);printf("\nSorted Linked List:\n");printList(head);return 0;
}

该程序首先定义了一个结构体node，其中包含一个整型数据data和一个指向下一个结构体node的指针next。接着定义了三个函数：

swap函数用于交换两个结构体的数据成员data。
bubbleSort函数实现了基于链表的冒泡排序。
printList函数用于遍历链表并打印所有节点的数据成员data。

最后，main函数中创建了一个空的链表，并用push函数向其中添加了五个节点。然后，原始链表被打印出来，接着使用bubbleSort函数对链表进行排序。最后，排好序的链表也被打印出来。

2、快速排序

2.1 算法思想

快速排序（Quick Sort）是一种常用的排序算法，其基本思想是选取一个基准元素，将所有小于基准元素的数放到其左边，所有大于基准元素的数放到其右边，然后再对两边分别进行递归排序。快速排序是一种比较快的排序算法，平均时间复杂度为O(nlogn)。

具体算法步骤如下：

选取一个基准元素（通常是第一个元素或者随机选取），将数组分成左右两个部分；
将小于等于基准元素的数放到左边，大于基准元素的数放到右边，分别形成两个子数组；
对左右两个子数组进行递归排序，直到每个子数组只有一个元素或为空为止；
合并两个子数组，完成排序。

快速排序的关键在于如何进行划分，一般采用双指针法，即左指针从左往右扫描数组，右指针从右往左扫描数组，当左指针找到一个大于基准元素的数，右指针找到一个小于基准元素的数时，交换两个数的位置，直到左指针和右指针相遇。最后将基准元素与左右子数组的中间位置交换，完成一次排序。

2.2 代码实现

时间复杂度为O(nlogn)

下面是C语言实现快速排序的代码：

void quick_sort(int arr[], int left, int right) {if (left >= right)return;int i = left, j = right, pivot = arr[left];while (i < j) {while (i < j && arr[j] >= pivot)j--;arr[i] = arr[j];while (i < j && arr[i] <= pivot)i++;arr[j] = arr[i];}arr[i] = pivot;quick_sort(arr, left, i - 1);quick_sort(arr, i + 1, right);
}

上述代码中，arr表示待排序数组，left表示待排序区间左边界，right表示待排序区间右边界。首先判断左右边界是否相等或左边界大于右边界，如果是，则直接返回。然后取arr[left]作为枢轴元素，从右向左找到第一个小于枢轴元素的元素，从左向右找到第一个大于枢轴元素的元素，并交换两个元素。重复上述操作直到i=j，将枢轴元素放到i位置上，此时数组被分成了两个部分，左边部分小于枢轴元素，右边部分大于枢轴元素。然后递归调用快速排序函数对左右两个部分进行排序。