网站开发在线学习,免费的平面设计网站,网站建设宣传页,微信网站建设塞尼铁克目录 1.冒泡排序1.1 基本原理1.2 例子1.3 示例代码 2.魔炮排序2.1 基本原理2.1 例子2.2 示例代码 1.冒泡排序
1.1 基本原理
冒泡排序#xff08;Bubble Sort#xff09;是一种简单的排序算法。它重复地遍历待排序的数列#xff0c;一次比较两个元素#xff0c;如果他们的… 目录 1.冒泡排序1.1 基本原理1.2 例子1.3 示例代码 2.魔炮排序2.1 基本原理2.1 例子2.2 示例代码 1.冒泡排序
1.1 基本原理
冒泡排序Bubble Sort是一种简单的排序算法。它重复地遍历待排序的数列一次比较两个元素如果他们的顺序错误就把他们交换过来。遍历数列的工作是重复地进行直到没有再需要交换也就是说该数列已经排序完成。
冒泡排序的基本思想是
比较相邻的元素。如果第一个比第二个大就交换他们两个。对每一对相邻元素做同样的工作从开始第一对到结尾的最后一对。这步做完后最后的元素会是最大的数。针对所有的元素重复以上的步骤除了最后一个。持续每次对越来越少的元素重复上面的步骤直到没有任何一对数字需要比较。 这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端故名。
冒泡排序的时间复杂度在最坏和平均情况下都是 O(n^2)其中 n 是列表的长度。 解释如下
最坏情况下即输入数组完全逆序需要进行 n(n-1)/2 次比较和交换所以最坏情况下的时间复杂度是 O(n^2)。平均情况下需要进行近似 n(n-1)/4 次比较和交换所以平均情况下的时间复杂度也是 O(n^2)。 在最好情况下即输入数组已经完全有序冒泡排序只需要进行 n-1 次比较不需要进行交换所以最好情况下的时间复杂度是 O(n)。
1.2 例子
冒泡排序的基本思想是每次比较两个相邻的元素如果他们的顺序如从大到小、首字母从A到Z错误就将他们交换过来。 举例说明假设我们有一个待排序的数列[5, 3, 8, 6, 1]
第一轮排序从第一个元素开始比较相邻的两个元素如果第一个元素大于第二个元素就交换他们。这一轮结束后最大的元素会被放到数列的最后。数列变为[3, 5, 6, 1, 8]第二轮排序同样从第一个元素开始重复上述过程但是最后一个元素这里是8可以忽略因为它已经是最大的元素。数列变为[3, 5, 1, 6, 8]第三轮排序重复上述过程忽略最后两个元素这里是6和8。数列变为[3, 1, 5, 6, 8]第四轮排序重复上述过程忽略最后三个元素这里是5、6和8。数列变为[1, 3, 5, 6, 8] 此时所有元素已经排序完成。
1.3 示例代码
#include stdio.hvoid 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[j1]) { // 交换 arr[j] 和 arr[j1]temp arr[j];arr[j] arr[j1];arr[j1] temp;}}}
}void printArray(int arr[], int size) {int i;for (i0; i size; i)printf(%d , arr[i]);printf(\n);
}int main() {int arr[] {64, 34, 25, 12, 22, 11, 90};int n sizeof(arr)/sizeof(arr[0]);bubbleSort(arr, n);printf(Sorted array: \n);printArray(arr, n);return 0;
}这段代码首先定义了一个 bubbleSort 函数用于执行冒泡排序。然后定义了一个 printArray 函数用于打印数组。在 main 函数中我们创建了一个数组并调用 bubbleSort 函数对其进行排序然后打印排序后的数组。
2.魔炮排序
2.1 基本原理
魔炮排序Cocktail Sort也被称为双向冒泡排序是冒泡排序的一种变形。它在对待排序的数列进行遍历时是双向进行的也就是说每一轮遍历都分为两个方向一个是从前往后一个是从后往前。 魔炮排序的基本思想是
首先从左到右比较相邻的元素如果左边的元素大于右边的元素就交换他们。这一步完成后最大的元素会被放到数列的最右边。然后从右到左比较相邻的元素如果右边的元素小于左边的元素就交换他们。这一步完成后最小的元素会被放到数列的最左边。重复以上步骤直到没有元素需要交换。
魔炮排序Cocktail Sort的时间复杂度和冒泡排序一样都是 O(n^2)。 在最好的情况下如果输入的数据已经是排序好的那么魔炮排序只需要进行一次遍历所以最好的情况下时间复杂度是 O(n)。 但是在最坏的情况下例如输入的数据是逆序的那么魔炮排序需要进行 n(n-1)/2 次比较所以最坏的情况下时间复杂度是 O(n^2)。 平均情况下魔炮排序的时间复杂度也是 O(n^2)。
2.1 例子
举例说明假设我们有一个待排序的数列[5, 1, 4, 2, 8, 0, 2]
第一轮从左到右的排序后数列变为[1, 4, 2, 5, 0, 2, 8]第一轮从右到左的排序后数列变为[0, 1, 2, 4, 2, 5, 8]第二轮从左到右的排序后数列变为[0, 1, 2, 2, 4, 5, 8]第二轮从右到左的排序后数列变为[0, 1, 2, 2, 4, 5, 8] 此时所有元素已经排序完成。
2.2 示例代码
#include stdio.hvoid cocktailSort(int a[], int n) {int swapped 1;int start 0;int end n - 1;while (swapped) {swapped 0;for (int i start; i end; i) {if (a[i] a[i 1]) {int temp a[i];a[i] a[i 1];a[i 1] temp;swapped 1;}}if (!swapped)break;swapped 0;--end;for (int i end - 1; i start; --i) {if (a[i] a[i 1]) {int temp a[i];a[i] a[i 1];a[i 1] temp;swapped 1;}}start;}
}void printArray(int a[], int n) {for (int i 0; i n; i)printf(%d , a[i]);printf(\n);
}int main() {int a[] {5, 1, 4, 2, 8, 0, 2};int n sizeof(a) / sizeof(a[0]);cocktailSort(a, n);printf(Sorted array: \n);printArray(a, n);return 0;
}这段代码首先定义了一个 cocktailSort 函数用于执行魔炮排序。然后定义了一个 printArray 函数用于打印数组。在 main 函数中我们创建了一个数组并调用 cocktailSort 函数对其进行排序然后打印排序后的数组。
