用函数来实现冒泡排序 |
您所在的位置：网站首页 › PHP自定义函数实现$a排序 › 用函数来实现冒泡排序 |
用函数来实现冒泡排序
|
冒泡排序: 冒泡排序重复地走访过要排序的元素列，依次比较两个相邻的元素，如果顺序（如从大到小、首字母从Z到A）错误就把 他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素列已经排序完成。 也就是说, 一直进行简单的两两比较, 直到符合所指定的顺序即可 比如说: 5, 4, 3, 2, 1, 我要用冒泡排序的方式将其排成 1, 2, 3, 4, 5. 那么就从开始的两个元素进行比较. 5和4进行比较, 发现5>4, 不符合所要求的顺序, 那么就将5和4进行交换, 从而得到 4, 5, 3, 2, 1. 这时再比较5和3, 发现5>3, 不符合顺序, 继续交换得到4, 3, 5, 2, 1. 然后重复以上的动作, 直到得到4, 3, 2, 1, 5. 这时5已经被交换到了它应该所在的最终位置, 这样的话, 一趟冒泡排序就结束了 也可以如图表示:
从图中红色曲线可得, 第一趟冒泡排序是需要比较四次, 第二趟冒泡排序需要比较三次, 之后的比较次数也是递减的 5个元素, 需要进行4趟冒泡排序.因此, 代码如下: void BubbleSort(int arr[], int sz) { // 明确冒泡排序的趟数 int i = 0; for (i = 0; i < sz; i++) { // 一趟冒泡 int j = 0; for (j = 0; j < sz - 1 - i; j++) { // sz-1-i代表着每一趟冒泡时, 进行的元素比较次数 if (arr[j] > arr[j + 1]) { // 两数进行交换 int tmp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = tmp; } } } } void Print(int arr[], int sz) { int i = 0; for (i = 0; i < sz; i++) { printf("%d ", arr[i]); } printf("\n"); } int main() { int arr[] = { 5, 4, 3, 2, 1 }; int sz = sizeof(arr) / sizeof(arr[0]); Print(arr, sz); BubbleSort(arr, sz); Print(arr, sz); return 0; }由于数组在传参的时候, 会隐式转化成数组首元素的地址, 所以根本无法在函数内部求数组中的元素个数, 只能在函数外边求好之后再通过参数进行传递使用. 运行结果:
但是, 如果数组本来就有序, 数组若一开始的顺序就是我们所希望的, 例如 1, 2, 3, 4, 5 如果采用上述代码的功能, 即使数组已然是我们所期望的顺序, 却还是会进入循环, 进行比较. 这样会降低代码的执行效率. 所以在这里需要进行代码优化 我在进行一趟冒泡的for循环之前加了一个变量simple并赋值为1, 如果在进行一趟冒泡的排序时有元素发生了交换, 就将simple置为0. 但是若在一趟冒泡排序之后, simple仍旧为1, 说明在这一趟冒泡排序中, 没有进行元素的交换, 就说明这个数组的元素已然有序, 就可以直接跳出循环, 不再进行排序.这样就会很大的提高代码的执行效率. void BubbleSort(int arr[], int sz) { // 明确冒泡排序的趟数 int i = 0; for (i = 0; i < sz; i++) { // 一趟冒泡 int j = 0; int simple = 1; for (j = 0; j < sz - 1 - i; j++) { if (arr[j] > arr[j + 1]) { int tmp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = tmp; simple = 0; } } if (simple == 1) { break; } } } void Print(int arr[], int sz) { int i = 0; for (i = 0; i < sz; i++) { printf("%d ", arr[i]); } printf("\n"); } int main() { int arr[] = { 5, 4, 3, 2, 1 }; int sz = sizeof(arr) / sizeof(arr[0]); Print(arr, sz); BubbleSort(arr, sz); Print(arr, sz); return 0; }运行结果:
|
【本文地址】
今日新闻 |
推荐新闻 |