冒泡排序及其三种优化模式c++flf1234567898的博客-

1：普通冒泡

void Swap(int* a, int* b) { int temp = *a; *a = *b; *b = temp; } void bubble_sort(int* arr,int length) {  clock_t start, finish;  start = clock(); for (int i = 0; i < length; ++i) { for (int j = 0; j < length - 1 - i; ++j) { if (arr[j] > arr[j+1]) { Swap(&arr[j], &arr[j + 1]); } } }  finish = clock(); double num = difftime(finish, start);  cout << "运行时间是："<<num << endl; } 

优化模式1：消息树法：（适用于完全有序的序列）

 void bubble_sort_1(int *arr, int length)//冒泡排序优化1 { int flag = 0; for (int i = 0; i < length; ++i) { for (int j = 0; j < length - 1 - i; ++j) { if (arr[j] > arr[j + 1]) { Swap(&arr[j], &arr[j + 1]);     flag = 1; } } if (flag == 0)//说明有序 break; } } 

优化2：适用于部分有序的序列

void bubble_sort_2(int *arr, int length)//冒泡排序优化2  部分有序 找截止有序点（记录最后一次交换的数据） { int flag = 0;//记录第几次寻找最长有序集 int pos = 0;//用来记录最后一次交换的位置 int k = length - 1; for (int i = 0; i < length-1; ++i) {   pos = 0;   flag = 0; for (int j = 0; j < k; ++j) { if (arr[j] > arr[j + 1]) { Swap(&arr[j], &arr[j + 1]);     flag = 1;     pos = j;// 记录最后一次交换的位置 } } if (flag == 0) break;   k = pos; } } 

优化3：来回找，从前往后大的放后面，从后往前小的放前面

 void bubble_sort_3(int *arr, int length)//正反交替进行扫描  正向放将最大值放在后面，反向将最小值放在后面 { int pos = 0; int k = length - 1; int flag = 0; int start = 0; for (int i = 0; i < length - 1; ++i) { for (int j = 0; j < k; ++j) // 正向搜索到最大值 { if (arr[j] > arr[j + 1]) { Swap(&arr[j], &arr[j + 1]);     flag = 1;     pos = j; } } for (int j = pos; j > start; --j)//反向搜索最小值 { if (arr[j] < arr[j-1]) { Swap(&arr[j - 1], &arr[j]); } }   start++;   k--; } }