网站建设维修服务流程/百度首页关键词推广

1.从头依次访问数组每个元素，进行相邻元素之间的交换

2.元素之间两两交换，把小的换到前面，大的放到后面。

3.所有元素交换完成后，一趟交换完成，此时最大的元素会到数组尾部。

4.反复执行以上步骤，直到所有元素都排序完。

结束条件：在任何一趟进行过程中，未出现交换。

注意点：冒泡算法通过双循环来控制跑的趟数和每趟需要比较的元素，即外层循环控制跑的趟数，内层循环控制需要比较的元素个数。

一趟最坏的情况是排好一个元素，所以n个元素需要n趟，因为剩最后一个元素时，已经排好序，所以最后需要n - 1趟。

编程思想：当解决某类问题没有思路时，可以借助实例进行分析。
    eg：冒泡排序中，当不知道j的判断条件时，可以对实例进行分析，第一轮有10个元素，
    进行10 - 1次交换，第二轮有10个元素，进行10 - 1 - j(此时的j为1) =8交换，
    通过结果逆推出代码。

优化一：

假设我们现在排序arr[] = { 1, 2, 3, 4, 5, 6, 7, 9, 8 }这组数据，按照上面的排序方法，第一趟排序后将8 和9 已经交换有序，接下来的排序就是多余的，什么也没做。所以我们

可以在交换的地方加一个标记，如果那一趟排序没有交换元素，说明这组数据已经有序，不用再继续下去。

 

static void Swap(int*xp, int*yp){int temp = *xp;*xp = *yp;*yp = temp;
}
void BubbleSort(int arr[], int num){for (int i = 0; i < num - 1; i++){//交换的轮数//循环从0开始，因为数组元素的下标从0开始int flag = 1;for (int j = 0; j < num - i - 1; j++){//每一轮交换的次数if (arr[j] > arr[j + 1]){Swap(&arr[j], &arr[j + 1]);flag = 0;}}if (flag){break;}}
}

 

优化二：

优化一仅仅适用于连片有序而整体无序的数据（例如：1，2，3，4，5，7，6）。但是对于前面大部分是无序而后面小半部分有序的数据（1，2，5，7，4，3，6，8，9，10）排序效率也不乐观，对于这种数据类型，我们可以继续优化。即我们可以记下最后一次交换的位置，后边没有交换，必然是有序的，然后下一次排序从第一个比较 到      上一次记录的位置  直至结束即可。

注：第二种优化不需要使用flag,比较多余，如果最后交换位置为0，就已经说明没有交换了

static void Swap(int*xp, int*yp){int temp = *xp;*xp = *yp;*yp = temp;
}
void BubbleSort(int arr[], int num){for (int i = 0; i < num - 1; i++){int end = num -1;int pos = 0;for (int j = 0; j < end; j++){if (arr[j] > arr[j + 1]){Swap(&arr[j], &arr[j + 1]);pos = j;//交换元素，记录最后一次交换的位置}}end = pos;//下一次比较到记录位置即可}
}

优化三：

双向冒泡排序，又叫鸡尾酒排序：它的过程是：先从左往右比较一次，再从右往左比较一次，然后又从左往右比较一次，以此类推。

优点：能够再特定条件下，减少排序的回合数；缺点：代码量增大一倍。使用场景：大部分元素已经有序的情况下。

他是为了优化前面的大部分元素都已经排好序的数组，例如对于数组[2,3,4,5,6,7,8,1]如果使用普通的冒泡排序，需要比较7次；而换成双向冒泡排序，只需比较三次。

简单起见，先看下单纯的双向冒泡排序（没有结合前面两种优化）：

void BubbleSort(int arr[], int num){int left = 0;int right = num - 1;while (left < right){//奇数轮，从左向右比较交换for (int i = left; i < right; i++){if (arr[i] > arr[i + 1]){Swap(&arr[i], &arr[i + 1]);}}right--;//偶数轮，从右向左比较交换for (int i = right; i > left; i--){if (arr[i] < arr[i - 1]){Swap(&arr[i], &arr[i - 1]);}}left++;}
}

最终优化：优化一 + 优化二 + 优化三

void BubbleSort(int arr[], int num){int left = 0;int right = num - 1;int lastSwapIndex = 0;int flag = 1;while (left < right){//奇数轮，从左向右比较交换for (int i = left; i < right; i++){if (arr[i] > arr[i + 1]){Swap(&arr[i], &arr[i + 1]);lastSwapIndex = i;}}right = lastSwapIndex;//将最后一次交换的位置作为右边界if (flag){break;}//偶数轮，从右向左比较交换for (int i = right; i > left; i--){if (arr[i] < arr[i - 1]){Swap(&arr[i], &arr[i - 1]);lastSwapIndex = i;}}left = lastSwapIndex;//将最后一次交换的位置作为左边界if (flag){break;}}
}