旅游网站建设与设计,做外链等于网站更新么,微商货源类网站源码,某网站突然不能浏览了排序算法 —— 冒泡排序
基本概念
冒泡排序是一种简单的排序算法。它重复地遍历要排序的列表#xff0c;一次比较两个元素#xff0c;并交换它们的位置#xff0c;如果它们不是按照升序排列的。这步遍历是重复进行的#xff0c;直到没有再需要交换#xff0c;也就是说该…排序算法 —— 冒泡排序
基本概念
冒泡排序是一种简单的排序算法。它重复地遍历要排序的列表一次比较两个元素并交换它们的位置如果它们不是按照升序排列的。这步遍历是重复进行的直到没有再需要交换也就是说该列表已经排序完成。该算法为交换排序之一。
算法步骤
比较相邻的元素。如果第一个比第二个大就交换它们两个。对每一对相邻元素作同样的工作从开始第一对到结尾的最后一对。这步做完后最后的元素会是最大的数。针对所有的元素重复以上的步骤除了最后一个。重复步骤1~3直到排序完成。
时间复杂度
冒泡排序算法的运行时间与输入数据有关。最佳情况下数据已经排序算法仅需一次遍历即可完成。在最坏情况下数据是完全逆序的需要 n-1 次遍历和 n-1 次比较。因此其时间复杂度为 O(n^2)。
最好的时间复杂度
当列表已经排序时冒泡排序的最佳时间复杂度为 O(n)。在最坏情况下当列表反转时时间复杂度为 O(n^2)。
最坏的时间复杂度
当列表反转时冒泡排序的最坏时间复杂度为 O(n^2)。
平均时间复杂度
冒泡排序的平均时间复杂度为 O(n^2)。
空间复杂度
冒泡排序的空间复杂度为 O(1)它只使用了两个附加变量。
稳定性
冒泡排序是一种稳定的排序算法因为它不会改变相等元素的顺序。
优缺点
冒泡排序是一种简单的排序算法但它也有其优缺点。它的优点是它的实现非常简单并且对于小数据集来说它的性能很好。然而它的缺点是它对于大型数据集来说非常慢并且它需要额外的空间来存储临时变量。因此它最适合用于小数据集的排序。
优点
实现简单对于小数据集来说它的性能很好它是一个稳定的排序算法不会改变具有相等键的元素的相对顺序。原地排序不需要额外的内存。
缺点
对于大型数据集来说它的性能很慢它需要额外的空间来存储临时变量
应用场景
冒泡排序是一种基础的排序算法由于其算法简单因此常用于教学排序算法的入门。在实际应用中由于其平均和最坏情况下的时间复杂度都是O(n^2)所以它并不适合处理大数据集。然而冒泡排序在特定情况下仍然有其适用场景
小型数据集当数据量较小特别是数据规模在几十到几百之间时冒泡排序可以很快完成任务因为其常数因子较小。部分已排序的数组如果数组已经部分排序冒泡排序可以很快地将剩下的元素排到正确的位置因为它在每一轮排序后至少会将一个元素放到最终位置。几乎已排序的数组对于几乎已经排序好的数组冒泡排序的时间复杂度可以接近O(n)因为在这种情况下内部循环的提前终止特性会发挥作用。内存使用限制冒泡排序是原地排序算法除了交换元素时需要的常数额外空间不需要额外的存储空间这在有严格内存使用限制的环境下是一个优点。实现简单在一些简单的应用场景中如嵌入式系统或教学示例中可能会优先选择冒泡排序因为它的实现代码简单易于理解和维护。稳定排序冒泡排序是一个稳定的排序算法如果需要保持相等元素的相对顺序不变冒泡排序可以满足这一需求。教学演示在计算机科学教育中冒泡排序经常被用来教授排序算法的基本概念如比较和交换操作。 尽管冒泡排序在上述场景中有其应用但在大多数需要高性能排序的应用中更高效的算法如快速排序、归并排序或堆排序通常是更好的选择。
代码实现
下面是一个简单的python的案例
def bubble_sort(arr):n len(arr)for i in range(n):for j in range(0, n-i-1):if arr[j] arr[j1]:arr[j], arr[j1] arr[j1], arr[j]return arr接下来是一个C代码案例
void bubbleSort(int arr[], int n) {for (int i 0; i n-1; i) {for (int j 0; j n-i-1; j) {if (arr[j] arr[j1]) {int temp arr[j];arr[j] arr[j1];arr[j1] temp;}}}
}下面是一个 C 模板的代码案例
template typename T
void bubbleSort(T arr[], int n)
{// Loop through the array n-1 timesfor (int i 0; i n - 1; i){// Loop through the array n-i-1 timesfor (int j 0; j n - i - 1; j){// If the element at index j is greater than the element at index j1, swap themif (arr[j] arr[j 1]){swap(arr[j], arr[j 1]);}}}
}完整 C 代码
下面是一个完整的C代码案例
#include iostream
#include cassert
#include stringusing namespace std;template typename T
void bubbleSort(T arr[], int n)
{// Loop through the array n-1 timesfor (int i 0; i n - 1; i){// Loop through the array n-i-1 timesfor (int j 0; j n - i - 1; j){// If the element at index j is greater than the element at index j1, swap themif (arr[j] arr[j 1]){swap(arr[j], arr[j 1]);}}}
}class Person
{
public:Person(string name, int age, int score){this-name name;this-age age;this-socre score;}// Override the operator for other function to use.bool operator(const Person other) const{// Compare the socre of two Person objects.return this-socre other.socre;}// Override the operator for other function to use.bool operator(const Person other) const{// Compare the socre of two Person objects.return this-socre other.socre;}// Override the operator for other function to use.bool operator(const Person other) const{// Compare the socre, age and name of two Person objects.return this-socre other.socre this-age other.age this-name other.name;}// Override the operator! for other function to use.bool operator!(const Person other) const{// Compare the socre, age and name of two Person objects.return this-socre ! other.socre ||this-age ! other.age ||this-name ! other.name;}// Now there are some get parameters function for this calss:const string getName() const { return this-name; }int getAge() const { return this-age; }int getSocre() const { return this-socre; }private:string name;int age;int socre;
};// This is a unit test function for Person class.
void testPerson()
{Person person1(Alice, 20, 90);Person person2(Bob, 21, 80);Person person3(Charlie, 22, 85);// Test operatorassert(person1 person2);assert(!(person1 person3));// Test operatorassert(person2 person1);assert(!(person3 person1));// Test operatorassert(person1 person1);assert(!(person1 person2));// Test operator!assert(person1 ! person2);assert(!(person1 ! person1));
}int main()
{// Declare an array of integersint arr[] {64, 34, 25, 12, 22, 11, 90};// Calculate the size of the arrayint n sizeof(arr) / sizeof(arr[0]);// Call the bubbleSort function to sort the arraybubbleSortint(arr, n);// Print the sorted arraycout Sorted array: \n;for (int i 0; i n; i){cout arr[i] ;}cout endl;// Declare an array of floatsdouble arr2[] {64.5, 34.2, 25.1, 12.6, 22.8, 11.9, 90.0};// Calculate the size of the arrayint n2 sizeof(arr2) / sizeof(arr2[0]);// Call the bubbleSort function to sort the arraybubbleSortdouble(arr2, n2);// Print the sorted arraycout Sorted array: \n;for (int i 0; i n2; i){cout arr2[i] ;}cout endl;// Declare an array of characterschar arr3[] {g, e, k, i, t, c, h};// Calculate the size of the arrayint n3 sizeof(arr3) / sizeof(arr3[0]);// Call the bubbleSort function to sort the arraybubbleSortchar(arr3, n3);// Print the sorted arraycout Sorted array: \n;for (int i 0; i n3; i){cout arr3[i] ;}cout endl;testPerson();// Now I want to write some Person classs bubble sort examples in here:// Declare an array of Person objectsPerson arr4[] {Person(John, 25, 90), Person(Alice, 30, 85), Person(Bob, 20, 78), Person(Eve, 22, 89)}; // This is a dummy Person class, you need to implement it properly.// Calculate the size of the arrayint n4 sizeof(arr4) / sizeof(arr4[0]);// Call the bubbleSort function to sort the arraybubbleSortPerson(arr4, n4);// Print the sorted arraycout Sorted array: \n;for (int i 0; i n4; i){const auto person arr4[i];cout person.getName() person.getAge() person.getSocre() endl;}cout endl;// Declare an array of Person pointersPerson *arr5[4];arr5[0] new Person(John, 25, 90);arr5[1] new Person(Alice, 30, 85);arr5[2] new Person(Bob, 20, 78);arr5[3] new Person(Eve, 22, 89);// Calculate the size of the arrayint n5 sizeof(arr5) / sizeof(arr5[0]);// Call the bubbleSort function to sort the arraybubbleSortPerson *(arr5, n5);// Print the sorted arraycout Sorted array: \n;for (int i 0; i n5; i){const auto person arr5[i];cout person-getName() person-getAge() person-getSocre() endl;}cout endl;return 0;
}这段代码在最开始定义了一个模板函数bubbleSort用于对不同类型的数据如整数、浮点数和字符进行冒泡排序。然后定义了一个名为Person的类该类具有name、age和score属性并重载了、、和!运算符以便在排序时比较Person对象。
接下来定义了一个名为testPerson的函数用于测试Person类。在这个函数中创建了一些Person对象并测试了重载的运算符。
在main函数中首先对整数、浮点数和字符类型的数组进行冒泡排序然后测试Person类。最后对Person对象的数组和Person指针的数组进行冒泡排序并输出排序后的结果。
综上所述这段代码演示了如何使用冒泡排序算法对不同类型的数据进行排序并展示了如何使用Person类进行排序。
扩展阅读
优化时间复杂度和空间复杂度的思路
冒泡排序的时间复杂度和空间复杂度优化通常涉及以下几个方面
提前终止在冒泡排序的过程中如果在某一趟遍历中没有发生任何元素的交换那么可以认为数组已经排序完成可以提前终止排序过程。这种优化可以将最好情况下的时间复杂度从O(n^2)降低到O(n)。双向冒泡鸡尾酒排序传统的冒泡排序每次只将最大的元素移动到数组的一端而双向冒泡排序则是在每趟遍历中同时将最大元素和最小元素移动到数组的两端。这样可以在一定程度上减少排序所需的趟数。梳排序Comb Sort梳排序是冒泡排序的一种改进它通过设置一个逐渐减小的“间隔”也称为“梳子”来比较和交换元素。开始时间隔较大可以快速将大距离的元素移动到正确位置随着排序的进行间隔逐渐减小最终变为1这时数组几乎已经排序完成进行最后一轮冒泡排序。梳排序的平均时间复杂度接近O(n2/2p)其中p是梳子间隔减小的速度。泡沫优化在冒泡排序中每一趟遍历后最后一个交换的位置之后的元素在下一趟遍历中不再需要比较因为这部分的元素已经是排序好的。记录这个位置下一趟遍历只需要遍历到这个位置即可。差值交换在冒泡排序中如果使用差值交换代替传统的交换方式可以减少交换操作的次数。差值交换是指只在需要交换的元素之间记录差值而不是实际交换它们的位置。
常见的变种算法
历史上常用的冒泡排序变种包括
经典冒泡排序最基本的冒泡排序每次遍历将最大的元素移动到数组的末尾。鸡尾酒排序也称为双向冒泡排序每次遍历同时将最大元素移动到数组的一端最小元素移动到另一端。梳排序Comb Sort通过逐渐减小的间隔来比较和交换元素最后进行一次冒泡排序来修正剩余的元素顺序。奇偶排序在冒泡排序的基础上交替进行奇数索引和偶数索引的元素比较和交换。混沌冒泡排序引入随机性每次随机选择两个元素进行比较和交换用于某些特定场景下的排序。
需要注意的是尽管这些优化可以在某些情况下提高冒泡排序的性能但它们通常不能改变冒泡排序最坏情况下的时间复杂度O(n^2)。因此对于大规模数据集的排序更高效的算法如快速排序、归并排序或堆排序通常是更好的选择。
鸡尾酒排序双向冒泡排序
鸡尾酒排序Cocktail Sort也被称为双向冒泡排序或鸡尾酒搅拌排序它是一种改进的冒泡排序算法。与传统的冒泡排序不同鸡尾酒排序在每趟遍历中会同时将最大元素和最小元素移动到数组的两端而不是只将最大元素移动到一端。这样可以在一定程度上减少排序所需的趟数。
算法步骤
算法步骤如下
初始化设置两个指针一个指向数组的开始left另一个指向数组的末尾right。设置一个标志变量用于检测在上一趟遍历中是否发生了元素交换。正向遍历从left开始到right结束比较相邻元素如果它们的顺序错误则交换它们。这一步将最大的元素移动到数组的末尾。反向遍历将right指针减一从right开始到left结束比较相邻元素如果它们的顺序错误则交换它们。这一步将最小的元素移动到数组的开头。重复步骤2和3重复步骤2和3直到在一次完整的正向遍历和反向遍历中都没有发生元素交换这时数组已经排序完成。结束当left right时排序结束。
伪代码描述
鸡尾酒排序的伪代码如下
procedure cocktailSort(arr: list of sortable items)n length(arr)swapped truestart 0end n - 1while (swapped true)// 设置交换标志为falseswapped false// 正向遍历for i start to end - 1if (arr[i] arr[i 1])swap(arr[i], arr[i 1])// 发生了交换设置交换标志为trueswapped true// 如果没有发生交换数组已经排序完成if (swapped false)break// 将end指针减一end end - 1// 设置交换标志为falseswapped false// 反向遍历for i end - 1 downto startif (arr[i] arr[i 1])swap(arr[i], arr[i 1])// 发生了交换设置交换标志为trueswapped true// 将start指针加一start start 1// 结束循环
end procedureC 模板代码
下面是使用C模板实现的鸡尾酒排序
templatetypename T
void cocktailSort(std::vectorT arr) {bool swapped true;int start 0;int end arr.size() - 1;while (swapped) {// 设置交换标志为falseswapped false;// 正向遍历for (int i start; i end; i) {if (arr[i] arr[i 1]) {std::swap(arr[i], arr[i 1]);// 发生了交换设置交换标志为trueswapped true;}}// 如果没有发生交换数组已经排序完成if (!swapped) {break;}// 将end指针减一--end;// 设置交换标志为falseswapped false;// 反向遍历for (int i end - 1; i start; --i) {if (arr[i] arr[i 1]) {std::swap(arr[i], arr[i 1]);// 发生了交换设置交换标志为trueswapped true;}}// 将start指针加一start;}
}梳排序(Comb Sort)
梳排序Comb Sort是一种由Wlodzimierz Dobosiewicz于1980年发明由Tim Peter于1989年发表的排序算法。它是冒泡排序的一种改进算法旨在减少其所需的交换次数。梳排序通过比较相隔一定“间隔”也称为“梳子”的元素来工作逐渐减小这个间隔最终进行一次冒泡排序来修正剩余的元素顺序。
算法步骤
算法步骤如下
初始化间隔开始时间隔设置为数组长度除以1.3这个值是经验值也可以使用其他系数向下取整。这个间隔会随着排序的进行而逐渐减小。缩减间隔在每趟排序之后间隔会按照某个系数通常也是1.3减小直到间隔变为1。排序对于当前的间隔比较相隔该间隔的元素如果它们的顺序错误则交换它们。这个过程类似于冒泡排序但是比较的元素间隔更大。重复步骤2和3重复步骤2和3直到间隔减小到1。这时数组应该已经基本有序。最终冒泡排序进行一次传统的冒泡排序确保数组完全有序。
伪代码描述
梳排序的伪代码如下
procedure combSort(arr: list of sortable items)n length(arr)gap nshrink 1.3swapped falsewhile gap 1 or swapped// 设置间隔gap floor(gap / shrink)if gap 1gap 1swapped false// 对于当前的间隔进行排序for i 0 to n - gap - 1if arr[i] arr[i gap]swap(arr[i], arr[i gap])swapped true// 最终进行一次冒泡排序for i 0 to n - 2if arr[i] arr[i 1]swap(arr[i], arr[i 1])
end procedureC 模板代码
下面是使用C模板实现的梳排序
#include iostream
#include vector
#include cmath // 用于计算地板除法
templatetypename T
void combSort(std::vectorT arr) {int n arr.size();int gap n;bool swapped false;const double shrink 1.3;while (gap 1 || swapped) {// 设置间隔gap static_castint(floor(gap / shrink));if (gap 1) {gap 1;}swapped false;// 对于当前的间隔进行排序for (int i 0; i n - gap; i) {if (arr[i] arr[i gap]) {std::swap(arr[i], arr[i gap]);swapped true;}}}// 最终进行一次冒泡排序for (int i 0; i n - 1; i) {if (arr[i] arr[i 1]) {std::swap(arr[i], arr[i 1]);}}
}混沌冒泡排序
混沌冒泡排序Chaotic Bubble Sort是一种基于冒泡排序的变体它在比较和交换元素时引入了混沌理论的原理。混沌理论是一种研究在确定性系统中出现的看似随机或复杂行为的方法。在混沌冒泡排序中混沌序列用于决定哪些元素进行比较和交换而不是按照固定的顺序。
算法步骤
算法步骤如下
生成混沌序列首先需要生成一个混沌序列这个序列的长度与待排序数组的长度相同。混沌序列中的每个元素都是数组索引的一个排列确保每个索引都会被访问到。排序过程使用生成的混沌序列进行排序。对于混沌序列中的每一对索引比较对应的数组元素如果它们的顺序错误则交换它们。重复排序重复步骤2直到没有更多的元素需要交换即数组已经排序完成。
伪代码描述
混沌冒泡排序的伪代码如下
procedure chaoticBubbleSort(arr: list of sortable items)n length(arr)// 生成混沌序列chaoticSequence generateChaoticSequence(n)// 初始化交换标志swapped truewhile swapped// 设置交换标志为falseswapped false// 使用混沌序列进行排序for i 1 to n - 1// 获取混沌序列中的索引index1 chaoticSequence[i]index2 chaoticSequence[i 1]// 比较并交换元素if arr[index1] arr[index2]swap(arr[index1], arr[index2])// 发生了交换设置交换标志为trueswapped trueend while
end procedureC模板实现
下面是使用C模板实现的混沌冒泡排序
#include iostream
#include vector
#include cstdlib // 用于生成随机数
templatetypename T
void chaoticBubbleSort(std::vectorT arr) {int n arr.size();std::vectorint chaoticSequence(n);bool swapped true;// 生成混沌序列for (int i 0; i n; i) {chaoticSequence[i] i;}// 混沌打乱序列for (int i 0; i n; i) {std::swap(chaoticSequence[i], chaoticSequence[rand() % n]);}while (swapped) {swapped false;// 使用混沌序列进行排序for (int i 0; i n - 1; i) {// 获取混沌序列中的索引int index1 chaoticSequence[i];int index2 chaoticSequence[i 1];// 比较并交换元素if (arr[index1] arr[index2]) {std::swap(arr[index1], arr[index2]);swapped true;}}}
}这段代码定义了一个模板函数chaoticBubbleSort它可以接受任何类型的可排序元素数组。在main函数中我们创建了一个整数向量并使用chaoticBubbleSort进行排序然后打印排序后的结果。请注意这个实现使用了std::rand()来生成混沌序列这并不是真正的混沌序列生成方法而是一种简单的随机化方法。在实际应用中可能需要使用更复杂的混沌映射函数来生成混沌序列。
奇偶排序
奇偶排序Odd-Even Sort也称为奇偶换位排序是一种基于比较的排序算法它是冒泡排序的一种变体。在奇偶排序中排序过程分为两个阶段奇数阶段和偶数阶段。在奇数阶段比较所有奇数索引的元素对在偶数阶段比较所有偶数索引的元素对。这样交替进行直到数组完全排序。
算法步骤
算法步骤如下
初始化设置一个标记变量用于检测在上一轮排序中是否发生了元素交换。奇数阶段比较所有奇数索引的元素对索引为1, 2, 3, …如果它们的顺序错误则交换它们。偶数阶段比较所有偶数索引的元素对索引为0, 2, 4, …如果它们的顺序错误则交换它们。重复步骤2和3重复步骤2和3直到在一次完整的奇数阶段和偶数阶段中都没有发生元素交换这时数组已经排序完成。
伪代码描述
奇偶排序的伪代码如下
procedure oddEvenSort(arr: list of sortable items)n length(arr)swapped truewhile swappedswapped false// 奇数阶段for i 1 to n - 2 by 2if arr[i] arr[i 1]swap(arr[i], arr[i 1])swapped true// 偶数阶段for i 0 to n - 2 by 2if arr[i] arr[i 1]swap(arr[i], arr[i 1])swapped trueend while
end procedureC模板代码实现
下面是使用C模板实现的奇偶排序
#include iostream
#include vector
templatetypename T
void oddEvenSort(std::vectorT arr) {bool swapped true;int n arr.size();while (swapped) {swapped false;// 奇数阶段for (int i 1; i n - 1; i 2) {if (arr[i] arr[i 1]) {std::swap(arr[i], arr[i 1]);swapped true;}}// 偶数阶段for (int i 0; i n - 1; i 2) {if (arr[i] arr[i 1]) {std::swap(arr[i], arr[i 1]);swapped true;}}}
}带扩展阅读的完整C代码
#include iostream
#include cassert
#include string
#include vector
#include cstdlibusing namespace std;template typename T
void bubbleSort(T arr[], int n)
{// Loop through the array n-1 timesfor (int i 0; i n - 1; i){// Loop through the array n-i-1 timesfor (int j 0; j n - i - 1; j){// If the element at index j is greater than the element at index j1, swap themif (arr[j] arr[j 1]){swap(arr[j], arr[j 1]);}}}
}class Person
{
public:Person(string name, int age, int score){this-name name;this-age age;this-socre score;}// Override the operator for other function to use.bool operator(const Person other) const{// Compare the socre of two Person objects.return this-socre other.socre;}// Override the operator for other function to use.bool operator(const Person other) const{// Compare the socre of two Person objects.return this-socre other.socre;}// Override the operator for other function to use.bool operator(const Person other) const{// Compare the socre, age and name of two Person objects.return this-socre other.socre this-age other.age this-name other.name;}// Override the operator! for other function to use.bool operator!(const Person other) const{// Compare the socre, age and name of two Person objects.return this-socre ! other.socre ||this-age ! other.age ||this-name ! other.name;}// Now there are some get parameters function for this calss:const string getName() const { return this-name; }int getAge() const { return this-age; }int getSocre() const { return this-socre; }private:string name;int age;int socre;
};// This is a unit test function for Person class.
void testPerson()
{Person person1(Alice, 20, 90);Person person2(Bob, 21, 80);Person person3(Charlie, 22, 85);// Test operatorassert(person1 person2);assert(!(person1 person3));// Test operatorassert(person2 person1);assert(!(person3 person1));// Test operatorassert(person1 person1);assert(!(person1 person2));// Test operator!assert(person1 ! person2);assert(!(person1 ! person1));
}template typename T
void cocktailSort(vectorT arr)
{// Initialize swapped to true to enter loopbool swapped true;// Initialize start and end indicesint start 0;int end arr.size() - 1;// Loop until all swaps are donewhile (swapped){// Reset swapped to falseswapped false;// Loop through all elements in arrayfor (int i start; i end; i){// If element is greater than next element, swap themif (arr[i] arr[i 1]){swap(arr[i], arr[i 1]);swapped true;}}// If no swaps, then array is sortedif (!swapped){break;}// Decrement end index--end;// Reset swapped to falseswapped false;// Loop through all elements in arrayfor (int i end - 1; i start; --i){// If element is greater than next element, swap themif (arr[i] arr[i 1]){swap(arr[i], arr[i 1]);swapped true;}}// Increment start indexstart;}
}template typename T
void combSort(vectorT arr)
{// n is the size of the arrayint n arr.size();// gap is the gap between elementsint gap n;// swapped is a flag to check if any elements have been swappedbool swapped false;// the constant value of the gap is 1.3const double shrink 1.3;// while the gap is greater than 1 or swapped is truewhile (gap 1 || swapped){// gap is the new gapgap static_castint(floor(gap / shrink));// if the gap is less than 1, set it to 1if (gap 1){gap 1;}// set swapped to falseswapped false;// loop through the arrayfor (int i 0; i n - gap; i){// if the current element is greater than the next elementif (arr[i] arr[i gap]){// swap themswap(arr[i], arr[i gap]);// set swapped to trueswapped true;}}}// loop through the arrayfor (int i 0; i n - 1; i){// if the current element is greater than the next elementif (arr[i] arr[i 1]){// swap themswap(arr[i], arr[i 1]);}}
}template typename T
void chaoticBubbleSort(vectorT arr)
{// n is the size of the arrayint n arr.size();// create a vector to store the chaotic sequencevectorint chaoticSequence(n);// set swapped to true to start the loopbool swapped true;// fill the chaotic sequence with the indices of the arrayfor (int i 0; i n; i){chaoticSequence[i] i;}// shuffle the chaotic sequencefor (int i 0; i n; i){swap(chaoticSequence[i], chaoticSequence[rand() % n]);}// start the bubble sort loopwhile (swapped){swapped false;// loop through the array and compare each element to the one after itfor (int i 0; i n - 1; i){// store the indices of the elementsint index1 chaoticSequence[i];int index2 chaoticSequence[i 1];// if the element at the first index is greater than the one after itif (arr[index1] arr[index2]){// swap themswap(arr[index1], arr[index2]);// set swapped to true to start the next loopswapped true;}}}
}template typename T
void oddEvenSort(vectorT arr)
{bool swapped true;int n arr.size();while (swapped){swapped false;for (int i 1; i n - 1; i 2){if (arr[i] arr[i 1]){swap(arr[i], arr[i 1]);swapped true;}}for (int i 0; i n - 1; i 2){if (arr[i] arr[i 1]){swap(arr[i], arr[i 1]);swapped true;}}}
}void bubbleSortTestCase()
{// Declare an array of integersint arr[] {64, 34, 25, 12, 22, 11, 90};// Calculate the size of the arrayint n sizeof(arr) / sizeof(arr[0]);// Call the bubbleSort function to sort the arraybubbleSortint(arr, n);// Print the sorted arraycout Sorted array: \n;for (int i 0; i n; i){cout arr[i] ;}cout endl;// Declare an array of floatsdouble arr2[] {64.5, 34.2, 25.1, 12.6, 22.8, 11.9, 90.0};// Calculate the size of the arrayint n2 sizeof(arr2) / sizeof(arr2[0]);// Call the bubbleSort function to sort the arraybubbleSortdouble(arr2, n2);// Print the sorted arraycout Sorted array: \n;for (int i 0; i n2; i){cout arr2[i] ;}cout endl;// Declare an array of characterschar arr3[] {g, e, k, i, t, c, h};// Calculate the size of the arrayint n3 sizeof(arr3) / sizeof(arr3[0]);// Call the bubbleSort function to sort the arraybubbleSortchar(arr3, n3);// Print the sorted arraycout Sorted array: \n;for (int i 0; i n3; i){cout arr3[i] ;}cout endl;testPerson();// Now I want to write some Person classs bubble sort examples in here:// Declare an array of Person objectsPerson arr4[] {Person(John, 25, 90), Person(Alice, 30, 85), Person(Bob, 20, 78), Person(Eve, 22, 89)}; // This is a dummy Person class, you need to implement it properly.// Calculate the size of the arrayint n4 sizeof(arr4) / sizeof(arr4[0]);// Call the bubbleSort function to sort the arraybubbleSortPerson(arr4, n4);// Print the sorted arraycout Sorted array: \n;for (int i 0; i n4; i){const auto person arr4[i];cout person.getName() person.getAge() person.getSocre() endl;}cout endl;// Declare an array of Person pointersPerson *arr5[4];arr5[0] new Person(John, 25, 90);arr5[1] new Person(Alice, 30, 85);arr5[2] new Person(Bob, 20, 78);arr5[3] new Person(Eve, 22, 89);// Calculate the size of the arrayint n5 sizeof(arr5) / sizeof(arr5[0]);// Call the bubbleSort function to sort the arraybubbleSortPerson *(arr5, n5);// Print the sorted arraycout Sorted array: \n;for (int i 0; i n5; i){const auto person arr5[i];cout person-getName() person-getAge() person-getSocre() endl;}cout endl;
}void cocktailSortTestCase()
{// Declare an array of integersvectorint arr {64, 34, 25, 12, 22, 11, 90};// Call the bubbleSort function to sort the arraycocktailSortint(arr);// Print the sorted arraycout Sorted array: \n;for (int i 0; i arr.size(); i){cout arr[i] ;}cout endl;// Declare an array of floatsvectordouble arr2 {64.5, 34.2, 25.1, 12.6, 22.8, 11.9, 90.0};// Call the bubbleSort function to sort the arraycocktailSortdouble(arr2);// Print the sorted arraycout Sorted array: \n;for (int i 0; i arr2.size(); i){cout arr2[i] ;}cout endl;// Declare an array of charactersvectorchar arr3 {g, e, k, i, t, c, h};// Call the bubbleSort function to sort the arraycocktailSortchar(arr3);// Print the sorted arraycout Sorted array: \n;for (int i 0; i arr3.size(); i){cout arr3[i] ;}cout endl;// Now I want to write some Person classs bubble sort examples in here:// Declare an array of Person objectsvectorPerson arr4 {Person(John, 25, 90), Person(Alice, 30, 85), Person(Bob, 20, 78), Person(Eve, 22, 89)}; // This is a dummy Person class, you need to implement it properly.// Call the bubbleSort function to sort the arraycocktailSortPerson(arr4);// Print the sorted arraycout Sorted array: \n;for (int i 0; i arr4.size(); i){const auto person arr4[i];cout person.getName() person.getAge() person.getSocre() endl;}cout endl;
}void combSortTestCase()
{// Declare an array of integersvectorint arr {64, 34, 25, 12, 22, 11, 90};// Call the bubbleSort function to sort the arraycombSortint(arr);// Print the sorted arraycout Sorted array: \n;for (int i 0; i arr.size(); i){cout arr[i] ;}cout endl;// Declare an array of floatsvectordouble arr2 {64.5, 34.2, 25.1, 12.6, 22.8, 11.9, 90.0};// Call the bubbleSort function to sort the arraycombSortdouble(arr2);// Print the sorted arraycout Sorted array: \n;for (int i 0; i arr2.size(); i){cout arr2[i] ;}cout endl;// Declare an array of charactersvectorchar arr3 {g, e, k, i, t, c, h};// Call the bubbleSort function to sort the arraycombSortchar(arr3);// Print the sorted arraycout Sorted array: \n;for (int i 0; i arr3.size(); i){cout arr3[i] ;}cout endl;// Now I want to write some Person classs bubble sort examples in here:// Declare an array of Person objectsvectorPerson arr4 {Person(John, 25, 90), Person(Alice, 30, 85), Person(Bob, 20, 78), Person(Eve, 22, 89)}; // This is a dummy Person class, you need to implement it properly.// Call the bubbleSort function to sort the arraycombSortPerson(arr4);// Print the sorted arraycout Sorted array: \n;for (int i 0; i arr4.size(); i){const auto person arr4[i];cout person.getName() person.getAge() person.getSocre() endl;}cout endl;
}void chaoticButtleSortTestCase()
{// Declare an array of integersvectorint arr {64, 34, 25, 12, 22, 11, 90};// Call the bubbleSort function to sort the arraychaoticBubbleSortint(arr);// Print the sorted arraycout Sorted array: \n;for (int i 0; i arr.size(); i){cout arr[i] ;}cout endl;// Declare an array of floatsvectordouble arr2 {64.5, 34.2, 25.1, 12.6, 22.8, 11.9, 90.0};// Call the bubbleSort function to sort the arraychaoticBubbleSortdouble(arr2);// Print the sorted arraycout Sorted array: \n;for (int i 0; i arr2.size(); i){cout arr2[i] ;}cout endl;// Declare an array of charactersvectorchar arr3 {g, e, k, i, t, c, h};// Call the bubbleSort function to sort the arraychaoticBubbleSortchar(arr3);// Print the sorted arraycout Sorted array: \n;for (int i 0; i arr3.size(); i){cout arr3[i] ;}cout endl;// Now I want to write some Person classs bubble sort examples in here:// Declare an array of Person objectsvectorPerson arr4 {Person(John, 25, 90), Person(Alice, 30, 85), Person(Bob, 20, 78), Person(Eve, 22, 89)}; // This is a dummy Person class, you need to implement it properly.// Call the bubbleSort function to sort the arraychaoticBubbleSortPerson(arr4);// Print the sorted arraycout Sorted array: \n;for (int i 0; i arr4.size(); i){const auto person arr4[i];cout person.getName() person.getAge() person.getSocre() endl;}cout endl;
}void oddEvenSortTestCase()
{// Declare an array of integersvectorint arr {64, 34, 25, 12, 22, 11, 90};// Call the bubbleSort function to sort the arrayoddEvenSortint(arr);// Print the sorted arraycout Sorted array: \n;for (int i 0; i arr.size(); i){cout arr[i] ;}cout endl;// Declare an array of floatsvectordouble arr2 {64.5, 34.2, 25.1, 12.6, 22.8, 11.9, 90.0};// Call the bubbleSort function to sort the arrayoddEvenSortdouble(arr2);// Print the sorted arraycout Sorted array: \n;for (int i 0; i arr2.size(); i){cout arr2[i] ;}cout endl;// Declare an array of charactersvectorchar arr3 {g, e, k, i, t, c, h};// Call the bubbleSort function to sort the arrayoddEvenSortchar(arr3);// Print the sorted arraycout Sorted array: \n;for (int i 0; i arr3.size(); i){cout arr3[i] ;}cout endl;// Now I want to write some Person classs bubble sort examples in here:// Declare an array of Person objectsvectorPerson arr4 {Person(John, 25, 90), Person(Alice, 30, 85), Person(Bob, 20, 78), Person(Eve, 22, 89)}; // This is a dummy Person class, you need to implement it properly.// Call the bubbleSort function to sort the arrayoddEvenSortPerson(arr4);// Print the sorted arraycout Sorted array: \n;for (int i 0; i arr4.size(); i){const auto person arr4[i];cout person.getName() person.getAge() person.getSocre() endl;}cout endl;
}int main()
{testPerson();bubbleSortTestCase();cocktailSortTestCase();combSortTestCase();chaoticButtleSortTestCase();oddEvenSortTestCase();return 0;
}
个人格言
追寻与内心共鸣的生活未来会逐渐揭晓答案。
Pursue the life that resonates with your heart, and the future will gradually reveal the answer.
文章转载自： http://www.morning.rljr.cn.gov.cn.rljr.cn http://www.morning.mlbn.cn.gov.cn.mlbn.cn http://www.morning.prgdy.cn.gov.cn.prgdy.cn http://www.morning.bxgpy.cn.gov.cn.bxgpy.cn http://www.morning.lpqgq.cn.gov.cn.lpqgq.cn http://www.morning.txrkq.cn.gov.cn.txrkq.cn http://www.morning.abgy8.com.gov.cn.abgy8.com http://www.morning.krhkb.cn.gov.cn.krhkb.cn http://www.morning.xrpjr.cn.gov.cn.xrpjr.cn http://www.morning.jpgfx.cn.gov.cn.jpgfx.cn http://www.morning.jtnph.cn.gov.cn.jtnph.cn http://www.morning.gfprf.cn.gov.cn.gfprf.cn http://www.morning.tfrlj.cn.gov.cn.tfrlj.cn http://www.morning.gmswp.cn.gov.cn.gmswp.cn http://www.morning.qrmyd.cn.gov.cn.qrmyd.cn http://www.morning.gthwz.cn.gov.cn.gthwz.cn http://www.morning.kqxwm.cn.gov.cn.kqxwm.cn http://www.morning.cdygl.com.gov.cn.cdygl.com http://www.morning.bflws.cn.gov.cn.bflws.cn http://www.morning.crrmg.cn.gov.cn.crrmg.cn http://www.morning.xjqkh.cn.gov.cn.xjqkh.cn http://www.morning.qfqld.cn.gov.cn.qfqld.cn http://www.morning.mdjzydr.com.gov.cn.mdjzydr.com http://www.morning.qflwp.cn.gov.cn.qflwp.cn http://www.morning.ygrdb.cn.gov.cn.ygrdb.cn http://www.morning.xrwbc.cn.gov.cn.xrwbc.cn http://www.morning.wcghr.cn.gov.cn.wcghr.cn http://www.morning.slysg.cn.gov.cn.slysg.cn http://www.morning.rtmqy.cn.gov.cn.rtmqy.cn http://www.morning.kxqfz.cn.gov.cn.kxqfz.cn http://www.morning.rnmmh.cn.gov.cn.rnmmh.cn http://www.morning.tpyrn.cn.gov.cn.tpyrn.cn http://www.morning.xltwg.cn.gov.cn.xltwg.cn http://www.morning.wslpk.cn.gov.cn.wslpk.cn http://www.morning.qtzqk.cn.gov.cn.qtzqk.cn http://www.morning.pfnrj.cn.gov.cn.pfnrj.cn http://www.morning.zbmcz.cn.gov.cn.zbmcz.cn http://www.morning.mzrqj.cn.gov.cn.mzrqj.cn http://www.morning.tgyzk.cn.gov.cn.tgyzk.cn http://www.morning.qhrlb.cn.gov.cn.qhrlb.cn http://www.morning.ksgjn.cn.gov.cn.ksgjn.cn http://www.morning.bxbnf.cn.gov.cn.bxbnf.cn http://www.morning.fdmfn.cn.gov.cn.fdmfn.cn http://www.morning.lcmhq.cn.gov.cn.lcmhq.cn http://www.morning.rgxll.cn.gov.cn.rgxll.cn http://www.morning.mzzqs.cn.gov.cn.mzzqs.cn http://www.morning.horihe.com.gov.cn.horihe.com http://www.morning.vuref.cn.gov.cn.vuref.cn http://www.morning.qfwfj.cn.gov.cn.qfwfj.cn http://www.morning.ejknty.cn.gov.cn.ejknty.cn http://www.morning.nrqtk.cn.gov.cn.nrqtk.cn http://www.morning.qrzqd.cn.gov.cn.qrzqd.cn http://www.morning.rnzgf.cn.gov.cn.rnzgf.cn http://www.morning.rqbr.cn.gov.cn.rqbr.cn http://www.morning.rxhs.cn.gov.cn.rxhs.cn http://www.morning.sjqml.cn.gov.cn.sjqml.cn http://www.morning.rxnr.cn.gov.cn.rxnr.cn http://www.morning.ndcf.cn.gov.cn.ndcf.cn http://www.morning.rbffj.cn.gov.cn.rbffj.cn http://www.morning.prsxj.cn.gov.cn.prsxj.cn http://www.morning.bsghk.cn.gov.cn.bsghk.cn http://www.morning.zrlwl.cn.gov.cn.zrlwl.cn http://www.morning.lgrkr.cn.gov.cn.lgrkr.cn http://www.morning.nbrkt.cn.gov.cn.nbrkt.cn http://www.morning.fpxms.cn.gov.cn.fpxms.cn http://www.morning.trwkz.cn.gov.cn.trwkz.cn http://www.morning.dnpft.cn.gov.cn.dnpft.cn http://www.morning.rqkk.cn.gov.cn.rqkk.cn http://www.morning.hclqy.cn.gov.cn.hclqy.cn http://www.morning.yfstt.cn.gov.cn.yfstt.cn http://www.morning.ktqtf.cn.gov.cn.ktqtf.cn http://www.morning.yxshp.cn.gov.cn.yxshp.cn http://www.morning.hmgqy.cn.gov.cn.hmgqy.cn http://www.morning.i-bins.com.gov.cn.i-bins.com http://www.morning.lmmyl.cn.gov.cn.lmmyl.cn http://www.morning.xjnjb.cn.gov.cn.xjnjb.cn http://www.morning.bpmdz.cn.gov.cn.bpmdz.cn http://www.morning.drgmr.cn.gov.cn.drgmr.cn http://www.morning.yltyz.cn.gov.cn.yltyz.cn http://www.morning.yfcyh.cn.gov.cn.yfcyh.cn
