C/C++教程

算法学习笔记:1.1冒泡排序和优化(c语言实现)

本文主要是介绍算法学习笔记:1.1冒泡排序和优化(c语言实现),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

一,冒泡排序

思想:

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;
}

​​​​​​​

这篇关于算法学习笔记:1.1冒泡排序和优化(c语言实现)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!