珠海网站建,小清新wordpress模板,企业网站制作设计,空包网站做红章底单目录
1、冒泡排序
1.1 算法思想
1.2 代码实现
方式一#xff1a;顺序表
方式二#xff1a;链表
2、快速排序
2.1 算法思想
2.2 代码实现
2.3 例题分析 1、冒泡排序
1.1 算法思想 冒泡排序是一种简单的排序算法#xff0c;它的基本思想是从数组的第一个元素开始…目录
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.hvoid 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.hstruct 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]作为枢轴元素从右向左找到第一个小于枢轴元素的元素从左向右找到第一个大于枢轴元素的元素并交换两个元素。重复上述操作直到ij将枢轴元素放到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]
