root
/
geekdoc-python-zh
mirror of https://github.com/OpenDocCN/geekdoc-python-zh
1
0
Fork 0
Code Issues Actions Packages Projects Releases Wiki Activity
geekdoc-python-zh/docs/overiq/121.md

8.3 KiB
Raw Permalink Blame History

C 程序：使用冒泡排序法对数组升序排序

原文：https://overiq.com/c-examples/c-program-to-sort-an-array-in-ascending-order-using-bubble-sort/

最后更新于 2020 年 9 月 23 日

冒泡排序

冒泡排序是一种简单的方法，它将数组的元素按升序或降序排序。它的工作原理是比较相邻的元素，如果它们顺序不对，就交换它们。需要多次通过阵列。

以下是使用冒泡排序以升序对大小为N的数组进行排序的步骤:

通过#1 :

  1. 将arr[0]与arr[1]进行比较。如果arr[0] > arr[1]，交换他们。
  2. 将arr[1]与arr[2]进行比较。如果arr[1] > arr[2]，交换他们。
  3. 最后将a[N-2]和arr[N-1]进行对比，如果arr[N-2] > arr[N-1]的话，互换。

这完成了第一次通过。

在第一次通过之后，数组中的最高值将位于末尾。

通过#2 :

  1. 将arr[0]与arr[1]进行比较。如果arr[0] > arr[1]，交换他们。
  2. 将arr[1]与arr[2]进行比较。如果arr[1] > arr[2]，交换他们。
  3. 最后将a[N-3]和arr[N-2]进行对比，如果arr[N-3] > arr[N-2]的话，互换。

这完成了第二次通过。在此传递之后，第二高的元素将位于数组中第二高的索引处。

请注意，在第二次通过的最后一步中，我们没有将第二个最后元素即a[N-2]与最后一个元素即arr[N-1]进行比较，这是因为最后一个元素已经处于其正确位置。

通过#3 :

  1. 将arr[0]与arr[1]进行比较。如果arr[0] > arr[1]，交换他们。
  2. 将arr[1]与arr[2]进行比较。如果arr[1] > arr[2]，交换他们。
  3. 最后将a[N-4]和arr[N-3]进行对比，如果arr[N-4] > arr[N-3]的话，互换。

这完成了第三次通过。在此传递之后，第三高的元素将位于数组中第三高的索引处。

就这样，我们不停地穿过阵列。当我们遇到一个没有交换任何元素的通道时，我们就停下来。

举个例子吧。

假设，我们有一个数组arr声明并初始化为:

#define SIZE 5
int arr[SIZE] = {80, 60, 90, 10, 40}; // unsorted array

以下是使用冒泡排序按升序对该数组进行排序的步骤。

通过#1 :

第一步:比较80和60。80 > 60自，互换它们:

| 60 | 80 | 90 | 10 | 40 |

第二步:比较80和90。80 < 90自，我们什么都不做:

| 60 | 80 | 90 | 10 | 40 |

第三步:比较90和10。90 > 10自，互换它们:

| 60 | 80 | 10 | 90 | 40 |

第四步:比较90和40。90 > 40自，互换它们:

| 60 | 80 | 10 | 40 | 90 |

这完成了第一次通过。最高的元素，即90，现在在数组的末尾。在这个通道中，我们进行了三次互换。所以，我们需要进行另一次穿越。请记住，我们会一直穿过数组，直到遇到一个没有交换任何元素的通道。

通过#2 :

第一步:比较60和80。60 < 80自，我们什么都不做:

| 60 | 80 | 10 | 40 | 90 |

第二步:比较80和10。80 > 10自，互换它们:

| 60 | 10 | 80 | 40 | 90 |

第三步:比较80和40。80 > 40自，互换它们:

| 60 | 10 | 40 | 80 | 90 |

这完成了第二次通过。第二高的元素，即80，现在位于数组中第二高的索引处。另外，请注意，我们没有将80与90进行比较。这是因为元件90已经处于从通道#1 开始的正确位置。

我们在这个通道中进行了两次交换。所以，我们需要再表演一个。

通过#3 :

第一步:比较60和10。60 > 10自，互换它们:

| 10 | 60 | 40 | 80 | 90 |

第二步:比较60和40。60 > 40自，互换它们:

| 10 | 40 | 60 | 80 | 90 |

这完成了第三次通过。第三高的元素，即60，现在位于数组中第三高的索引处。另外，请注意，我们没有将60与80进行比较。这是因为元件80已经从通道#2 处于其正确位置。

我们在这个通道中进行了两次交换。所以，我们需要再表演一个。

通过#4 :

第一步:比较10和40。10 < 40自，我们什么都不做:

| 10 | 40 | 60 | 80 | 90 |

这完成了第四次通过。我们没有在这个通道里交换任何东西。所以，我们需要不需要再表演一个。数组中的所有元素现在都按升序排序。

冒泡排序程序

下面是一个使用冒泡排序算法对数组进行升序排序的 C 程序:

/****************************************************************
 * Program to sort an array in ascending order using Bubble sort  
 ****************************************************************/

#include<stdio.h> // include stdio.h library
#define MAX 5
void bubble_sort(int arr[]); // function declaration

int main(void)
{        
    int arr[MAX]; 

    // input array
    for(int i = 0; i < MAX; i++)
    {
        printf("arr[%d] = ", i);    
        scanf("%d", &arr[i]);
    }

    printf("\nUnsorted array: \n");

    // print unsorted array
    for(int i = 0; i < MAX; i++)
    {
        printf("%d ", arr[i]);    
    }

    // sort array
    bubble_sort(arr);

    printf("\n\nSorted array: \n");

    // print sorted array
    for(int i = 0; i < MAX; i++)
    {
        printf("%d ", arr[i]);    
    }

    return 0; // return 0 to operating system
}

/*
 *  bubble_sort() takes an array and sorts it
 *  in the ascending order
 */

void bubble_sort(int arr[])
{
    int tmp,  // temporary variable to hold one of the values while swapping
        is_swapped; // variable to indicate whether we have made any swaps during the passthrough

    for(int i = 0; i < MAX; i++)
    {
        // re-initialize is_swapped to 0 after every passthrough       
        is_swapped = 0;  

        for(int j = 0; j < MAX - 1 - i; j++)
        {            
            if(arr[j] > arr[j+1]) // compare adjacent elements
            {
                // swap adjacent elements
                tmp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = tmp;

                // set is_swapped to 1, to indicate
                // that we have made at least one 
                // swap during the passthrough
                is_swapped = 1;               
            }     
        }        

        // if no swaps are made in the last passthrough,
        // exit the outer for loop

        if (!is_swapped)
        {
            break;
        }
    }        
}

现在试试

预期输出:

Enter array: 
arr[0] = 80
arr[1] = 60
arr[2] = 90
arr[3] = 10
arr[4] = 40

Unsorted array: 
80 60 90 10 40 

Sorted array: 
10 40 60 80 90

它是如何工作的

所有工作都在bubble_sort()功能中完成:

以下是它的工作原理:

在第 50 行和第 51 行，我们已经声明了两个变量:tmp和is_swapped。在交换元素时，tmp变量将保存其中一个值，is_swapped用作一个标志，指示我们在传递过程中是否进行了任何交换。

在第 53-81 行，我们有一个外部 for 循环，它一直运行到数组没有被排序。

第 58-72 行的内部 for 循环在传递过程中交换无序元素。它从数组的开头开始，一直到还没有排序的索引。

如果我们在通过期间至少进行了一次交换，我们将is_swapped设置为1(第 70 行)。

最后，第 77-80 行的 if 语句检查is_swapped的值，以确定是否脱离外部 for 循环。当我们遇到一个没有交换任何元素的通道时，我们脱离了外部 for 循环。

请记住，上面的函数按升序对数组进行排序。要按降序排列元素，只需将第 60 行的 if 条件从arr[j] > arr[j+1]更改为arr[j] < arr[j+1]。

推荐阅读: