【数据结构】冒泡排序，快速排序的学习知识总结

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位置上，此时数组被分成了两个部分，左边部分小于枢轴元素，右边部分大于枢轴元素。然后递归调用快速排序函数对左右两个部分进行排序。