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

news/2024/5/19 23:23:48 标签: 数据结构, 算法, 冒泡排序, 快速排序

目录

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

具体算法步骤如下：

  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]


http://www.niftyadmin.cn/n/5055130.html

相关文章

8、SpringBoot_多环境开发

8、SpringBoot_多环境开发

二、多环境开发 1.概述 概述&#xff1a;开发环境、测试环境、生产环境 分类 开发环境 spring:datasource:druid:url: jdbc:mysql://localhost:3306/springboot_ssmusername: rootpassword: 123456driver-class-name: com.mysql.cj.jdbc.Driver测试环境 spring:datasource:dr…
阅读更多...
WebGL 切换着色器

WebGL 切换着色器

目录 前言 如何实现切换着色器 1. 准备用来绘制单色立方体的着色器 2. 准备用来绘制纹理立方体的着色器 3. 调用createProgram&#xff08;&#xff09;函数&#xff0c;利用第1步创建出的着色器&#xff0c;创建着色器程序对象 4. 调用createProgram&#xff08;&…
阅读更多...
英语——谐音篇——单词——单词密码

英语——谐音篇——单词——单词密码

记忆即联结&#xff0c;只要能建立有效的联结&#xff0c;就能很好地记住。在现实生活中&#xff0c;声音的联结模式能很好地帮助我们记忆。几乎每个学生都曾用谐音的方法记忆一些事物&#xff0c;但很多人都没有意识到&#xff0c;我们每个人都可以通过一定的练习&#xff0c;…
阅读更多...
MybatisPlus自定义SQL用法

MybatisPlus自定义SQL用法

1、功能概述&#xff1f; MybatisPlus框架提供了BaseMapper接口供我们使用&#xff0c;大大的方便了我们的基础开发&#xff0c;但是BaseMapper中提供的方法很多情况下不够用&#xff0c;这个时候我们依旧需要自定义SQL,也就是跟mybatis的用法相同&#xff0c;自定义xml映射文…
阅读更多...
el-menu 导航栏学习-for循环封装（2）

el-menu 导航栏学习-for循环封装（2）

基于el-menu 导航栏学习&#xff08;1&#xff09; 对于导航栏主菜单NavMenuDemo.vue进行for循环改进&#xff0c;代码如下所示&#xff1a; <template> <el-container> <el-aside width"200px"> <el-menu :default-active"this.$route.…
阅读更多...
阿里巴巴K8S集成seata

阿里巴巴K8S集成seata

正文 在K8S集成seata&#xff0c;官方配置 代码 apiVersion: v1 kind: Service metadata:name: seata-servernamespace: wmz-devlabels:k8s-app: seata-server spec:type: NodePortports:- port: 8091nodePort: 30091protocol: TCPname: httpselector:k8s-app: seata-server-…
阅读更多...
FPGA设计时序约束二、输入延时与输出延时

FPGA设计时序约束二、输入延时与输出延时

目录 一、背景 二、set_input_delay 2.1 set_input_delay含义 2.2 set_input_delay参数说明 2.3 使用样例 三、set_output_delay 3.1 set_output_delay含义 3.2 set_output_delay参数说明 3.3 使用样例 四、样例工程 4.1 工程代码 4.2 时序报告 五、参考资料 一、…
阅读更多...
LeetCode算法二叉树—226. 翻转二叉树

LeetCode算法二叉树—226. 翻转二叉树

目录 226. 翻转二叉树 代码&#xff1a; 运行结果&#xff1a; 给你一棵二叉树的根节点 root &#xff0c;翻转这棵二叉树&#xff0c;并返回其根节点。 示例 1&#xff1a; 输入&#xff1a;root [4,2,7,1,3,6,9] 输出&#xff1a;[4,7,2,9,6,3,1]示例 2&#xff1a; 输入…
阅读更多...
最新文章

Copyright @ 2022~2023