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

目录

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 
 
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 
#include 
 
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)。

具体算法步骤如下：

1. 选取一个基准元素（通常是第一个元素或者随机选取），将数组分成左右两个部分；

2. 将小于等于基准元素的数放到左边，大于基准元素的数放到右边，分别形成两个子数组；

3. 对左右两个子数组进行递归排序，直到每个子数组只有一个元素或为空为止；

4. 合并两个子数组，完成排序。

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

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

2.3 例题分析

以下是一个快速排序的例题：

假设我们要对以下数组进行快速排序：[7, 2, 8, 1, 4, 3, 6, 5]

• 首先选择一个基准值，可以选择数组中的任意一个数，这里我们选择第一个数7作为基准值。

• 接着从数组的左边开始，找到第一个大于等于基准值的数，这里是8；然后从数组的右边开始，找到第一个小于等于基准值的数，这里是5，将它们交换位置。

现在数组变成了：[5, 2, 8, 1, 4, 3, 6, 7]

• 继续从左到右找到一个大于等于基准值的数，这里是8，然后从右到左找到一个小于等于基准值的数，这里是3，将它们交换位置。

现在数组变成了：[5, 2, 3, 1, 4, 8, 6, 7]

• 继续从左到右找到一个大于等于基准值的数，这里是4，然后从右到左找到一个小于等于基准值的数，这里是1，将它们交换位置。

现在数组变成了：[5, 2, 3, 1, 4, 8, 6, 7]

• 继续从左到右找到一个大于等于基准值的数，这里是6，然后从右到左找到一个小于等于基准值的数，这里是1，将它们交换位置。

现在数组变成了：[5, 2, 3, 1, 4, 1, 6, 7, 8]

• 重复上述步骤，直到将整个数组排好序。

最后的排序结果是：[1, 2, 3, 4, 5, 6, 7, 8]