冒泡排序
冒泡排序:它重复地走访要排序的数列，一次比较两个相邻的元素，如果它们的顺序错误就把它们交换过来。重复地进行直到没有再需要交换，也就是说该数列已经排序完成。
下面是冒泡排序的步骤：
- 从第一个元素开始，依次比较相邻的两个元素，如果顺序不对则交换它们。
- 继续比较相邻的元素，直到最后一个元素，这样一轮比较下来，最大的元素就会被交换到最后的位置。
- 接着重复上述步骤，但是不包括已经排序好的最后一个元素，因为它们已经是最大的了。
重复以上步骤，直到所有元素都排好序为止。
对数组
arr[]= { 66, 34, 25, 12, 22, 11, 98 }进行冒泡排序
i=0，j=5,第一趟，交换了6次；
i=1, j=4,第二趟，交换了5次，
i=2, j=3,第三趟，交换了4次；
…以此类推
结论：
7个元素每走一趟，交换少一次，j少一次,i+1
代码实现：
#include <stdio.h> void bubbleSort(int arr[], int n) { //i为趟数 for (int i = 0; i < n - 1; i++) //arr[]7个元素 { for (int j = 0; j < n - i - 1; j++) { if (arr[j] > arr[j + 1]) { // 交换arr[j]和arr[j+1] int temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } } } int main() { int arr[] = { 66, 34, 25, 12, 22, 11, 98 }; int n = sizeof(arr) / sizeof(arr[0]); bubbleSort(arr, n); printf("排序后的数组: \n"); for (int i = 0; i < n; i++) { printf("%d ", arr[i]); } return 0; }
因为冒泡排序比较次数和交换次数都比较多，当数据量很大时，效率比较低。
优化:如果在一次排序中没有发生交换，则表示数组已经排好序了，可以提前结束排序。
使用Flag看他有没有进入交换，交换后就改为
#include <stdio.h> void bubbleSort(int arr[], int n) { for (int i = 0; i < n - 1; i++) { int flag = 1;//假设这⼀趟已经有序了 for (int j = 0; j < n - i - 1; j++) { if (arr[j] > arr[j + 1]) { flag = 0;//发⽣交换就说明，⽆序 // 交换arr[j]和arr[j+1] int temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } if (flag == 1)//这⼀趟没交换就说明已经有序，后续⽆序排序了 break; } } int main() { int arr[] = { 66, 34, 25, 12, 22, 11, 98 }; int n = sizeof(arr) / sizeof(arr[0]); bubbleSort(arr, n); printf("排序后的数组: \n"); for (int i = 0; i < n; i++) { printf("%d ", arr[i]); } return 0; }
