一，冒泡排序

思想：

1，找到数组的最大元素且放在当前数组的最后一位。（1）

2，然后在除去最大元素的数组中进行操作（1）。

3，当数组只有一个元素，则终止。

由于每次找到的元素都小于之前找到的元素，故而这个数组是升序的。

实现：

交换两个元素：

`int temp=a;a=b,b=a;`

找出两个元素的最大元素且放在最后：

if(a[0]>a[1]) {int t=a[0];a[0]=a[1],a[1]=t;}`

循环n次：

for(int i=0;i<n;i++)

找出n个元素的最大元素且放在最后：

for(int i=0;i<n-1;i++) `
​
if(a[i]>a[i+1]) {int t=a[i];a[i]=a[i+1],a[i+1]=t;}

在长度为len-1的数组中，需要比较len-2次。

在长度为len-i的数组中，需要比较len-i-1次；

for(int j=0;j<len-1-i;j++)`

数组长度为1，不用比较，即len-i>1，因此i<len-1；

for(int i=0;i<len-1;i++)`

代码：

void swap(int* a,i,j){
int temp=*(a+i);
*(a+i)=*(a+j),*(a+j)=temp;
}
​
void bubble_sort(int arr[],int len){
    for(int i=0;i<len-1;i++)
        for(int j=0;j<len-1-i;j++)
            if(arr[j]>arr[j+1])
                swap(&arr[j],&arr[j+1]);
}
​
int main() {
    int arr[]={22,34,3,32,82};
    int len=(int)sizeof(arr)/sizeof(*arr);
    bubble_sort(arr,len);
    for(int i=0;i<len;i++)
        printf("%d ",arr[i]);
    return 0;
}

二，冒泡排序的优化

分析：

1，如果数组已经有序，冒泡排序依然会进行

$$
\sum_{i=1}^{len-1}{len-1-i}
$$

次。

2，如果数组部分有序，该部分依然会进行比较；

实现：

1，令变量f等于数组长度。在每一次替换后，f记录j的值。一次内层循环结束，f等于进行过替换的最后一个j。如果f仍等于数组长度，则说明f没有记录过j，即没有替换过，即数组有序。此时，可直接中断循环；

void bubble_sort(int arr[],int len){
    int f=len;
    for(int i=0;i<len-1;i++)
        for(int j=0;j<len-1-i;j++)
            if(arr[j]>arr[j+1]){
                swap(&arr[j],&arr[j+1]);
                f=j;
            }
        if(f==len) break;               
}

2，一次内层循环结束，f=j，即代表着j之后没有替换，即有序，故j之后的元素不需要考虑。故可以设置内层循环的循环次数为f；

void bubble_sort(int arr[],int len){
    int f=0,ff=len;
    for(int i=0;i<len-1;i++)
        for(int j=0;j<ff;j++)
            if(arr[j]>arr[j+1]){
                swap(&arr[j],&arr[j+1]);
                f=j;
            }
        ff=f;
}

三，双向冒泡排序

思想：

1，使数组最大值在最后一位，数组最小值在第一位。（1）

2，在去掉第一位和最后一位的数组中进行操作（1）。

3，当数组只有一个或零个元素则终止。

实现：

用start表示第一位，end表示末位。

int start=0,end=len-1;

从start到end找到最大值并放在末位。

for(int j=start;j<end;j++)
if(arr[j]>arr[j+1])
swap(arr,j,j+1);

不考虑末位的元素。

end--；

从end到start找到最小值，并且不考虑首位元素。

for(int j=end;j>start;j--)
if(arr[j]<arr[j-1])
swap(arr,j,j-1);
start++；

循环结束的标志。

当start=end，数组只有一个元素。当start>end,数组只有0个元素.

while(start<end)

代码：

void bubble_sort(int arr[],int len){
int start=0,end=len-1;
while(start<end){
for(int j=start;j<end;j++)
if(arr[j]>arr[j+1])
swap(arr,j,j+1);
end--；
​
for(int j=end;j>start;j--)
if(arr[j]<arr[j-1])
swap(arr,j,j-1);
start++；
}

四，双向冒泡排序的优化​​​​​​​

分析:

缺点如冒泡排序:

实现：

1，

void bubble_sort(int arr[],int len){
int start=0,end=len-1,f=len-1;
while(start<end){
for(int j=start;j<end;j++)
if(arr[j]>arr[j+1]){
swap(arr,j,j+1);
f=j;
}
if(f==len-1) break;
​
end--；
​
for(int j=end;j>start;j--)
if(arr[j]<arr[j-1])
swap(arr,j,j-1);
start++；
}

2,

void bubble_sort(int arr[],int len){
int start=0,end=len-1,f1=0,f2=len-1;
while(start<end){
for(int j=start;j<end;j++)
if(arr[j]>arr[j+1]){
swap(arr,j,j+1);
f1=j;
}
end=f1;
​
for(int j=end;j>start;j--)
if(arr[j]<arr[j-1]){
swap(arr,j,j-1); 
f2=j;
}
start=f2;
}

​​​​​​​