冒泡排序算法优化C语言

冒泡排序的一般实现：

void bubbleSort(int arr[], int n) {
int i, j;
for (i = 0; i < n-1; i++) {
for (j = 0; j < n-i-1; j++) {
if (arr[j] > arr[j+1]) {
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}

冒泡排序的时间复杂度为O(n^2)，因此我们需要对冒泡排序进行优化，在优化的过程中需要考虑两个问题：

1.最优时间复杂度：O(n)

2.平均时间复杂度：O(n^2)

为了达到最优时间复杂度，需要在排序过程中加入一个标记，用来判断当前数组是否是有序的，如果已经有序，那么就可以直接退出循环，这样最优时间复杂度是O(n)。

为了达到平均时间复杂度，有两种方法：

1.鸡尾酒排序

鸡尾酒排序是对冒泡排序的一种改进，它可以在排序过程中来回地移动元素，从而提高排序的速度。

void cocktailSort(int arr[], int n) {
bool swapped = true;
int start = 0;
int end = n - 1;

while (swapped) {
//正向冒泡
swapped = false;
for (int i = start; i < end; ++i) {
if (arr[i] > arr[i + 1]) {
swap(arr[i], arr[i + 1]);
swapped = true;
}
}

if (!swapped)
break;

// 反向冒泡
swapped = false;
--end;
for (int i = end - 1; i >= start; --i) {
if (arr[i] > arr[i + 1]) {
swap(arr[i], arr[i + 1]);
swapped = true;
}
}

++start;
}
}

2.增加一个有序区间

在每次排序过程中，我们将数组分成两部分，一部分是已经排好序的有序部分，另一部分是尚未排序的部分。

void bubbleSort(int arr[], int n){
int i, j;
int t, flag;
for(i= n-1; i>0; i=t){
flag = 0;
t = 0；
for(j=0; j<i; j++){
if(arr[j]>arr[j+1]){
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
flag = j;
}
}
t = flag;
}
}

以上两种方法都可以达到平均时间复杂度为O(n^2)的目的。