冒泡排序法(从小到大)。输入10个整数,用冒泡排序法将它们从小到大排序后输出。
一种天真的方法是 - 实现两种算法并在计算机上运行两个程序以获得不同的输入,看看哪个花费更少的时间。这种方法在算法分析中存在许多问题。
渐进分析是在分析算法时处理上述问题的大思想。在渐近分析中,我们根据输入大小评估算法的性能(我们不测量实际运行时间)。我们计算算法所花费的时间(或空间)如何随着输入大小的增加而增加。
例如,让我们考虑排序数组中的搜索问题(搜索给定项目)。
上述搜索问题的解决方案包括:
为了理解渐近分析如何解决上述分析算法中提到的问题,
输入大小 | 在 A 上的运行时间 | B 上的运行时间 |
---|---|---|
10 | 2 秒 | ~ 1 小时 |
100 | 20 秒 | ~ 1.8小时 |
10^6 | ~ 55.5 小时 | ~ 5.5小时 |
10^9 | ~ 6.3 年 | ~ 8.3小时 |
此示例的运行时间:
可以用冒泡排序法对十个整数从小到大进行排序。冒泡排序法是一种基础排序算法,其实现思路是让相邻的元素不断比较,如果逆序就交换,直到整个序列有序。
下面是冒泡排序的代码实现(C++):
void bubbleSort(int arr[], int n) { for(int i=0;i<n-1;i++){ for(int j=0;jarr[j+1]){ int temp=arr[j]; arr[j]=arr[j+1]; arr[j+1]=temp; } } } }
其中,参数arr为待排序的数组,n为数组元素个数。通过嵌套的循环,依次比较相邻的元素,如果前者大于后者则交换,直到最后一个元素,此时第一个元素即为最小值。重复以上步骤,直到整个数组有序。
示例代码:
int main(){ int arr[10]={5,4,9,8,7,1,6,2,3,0}; bubbleSort(arr,10); for(int i=0;i<10;i++){ cout<<arr[i]<<" "; } return 0; }
输出为:0 1 2 3 4 5 6 7 8 9,表示数组元素从小到大排列。