search
Homephp教程PHP开发Three implementations of bubble sort

Three implementations of bubble sort

Dec 19, 2016 pm 01:15 PM
Bubble Sort

Bubble sorting is very easy to understand and implement, take sorting from small to large as an example:

Suppose the array length is N.

1. Compare the two adjacent data before and after. If the former data is greater than the latter data, the two data will be exchanged.

2. In this way, after traversing the 0th data to the N-1th data of the array, the largest data will "sink" to the N-1th position of the array.

3. N=N-1, if N is not 0, repeat the previous two steps, otherwise the sorting is completed.

It is easy to write the code by definition:

//冒泡排序1  
void BubbleSort1(int a[], int n)  
{  
       int i, j;  
       for (i = 0; i < n; i++)  
              for (j = 1; j < n - i; j++)  
                     if (a[j - 1] > a[j])  
                            Swap(a[j - 1], a[j]);  
}

Let’s optimize it and set a flag, which is true if an exchange occurs on this trip, otherwise it is false. Obviously, if there is no exchange in one trip, it means that the sorting has been completed.

//冒泡排序2  
void BubbleSort2(int a[], int n)  
{  
       int j, k;  
       bool flag;  
  
       k = n;  
       flag = true;  
       while (flag)  
       {  
              flag = false;  
              for (j = 1; j < k; j++)  
                     if (a[j - 1] > a[j])  
                     {  
                            Swap(a[j - 1], a[j]);  
                            flag = true;  
                     }  
              k--;  
       }  
}

Let’s do further optimization. If there is an array of 100 numbers, only the first 10 are unordered, and the next 90 are all sorted and all are greater than the first 10 numbers, then after the first traversal, the last position where the exchange occurs must be less than 10, and this The data after the position must be in order. Record this position. The second time you just need to traverse from the head of the array to this position.

//冒泡排序3  
void BubbleSort3(int a[], int n)  
{  
    int j, k;  
    int flag;  
      
    flag = n;  
    while (flag > 0)  
    {  
        k = flag;  
        flag = 0;  
        for (j = 1; j < k; j++)  
            if (a[j - 1] > a[j])  
            {  
                Swap(a[j - 1], a[j]);  
                flag = j;  
            }  
    }  
}

Bubble sorting is, after all, an inefficient sorting method and can be used when the data size is small. When the data size is relatively large, it is best to use other sorting methods.


For more articles related to the three implementations of bubble sorting, please pay attention to the PHP Chinese website!

Statement
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn

Hot AI Tools

Undresser.AI Undress

Undresser.AI Undress

AI-powered app for creating realistic nude photos

AI Clothes Remover

AI Clothes Remover

Online AI tool for removing clothes from photos.

Undress AI Tool

Undress AI Tool

Undress images for free

Clothoff.io

Clothoff.io

AI clothes remover

Video Face Swap

Video Face Swap

Swap faces in any video effortlessly with our completely free AI face swap tool!

Hot Tools

ZendStudio 13.5.1 Mac

ZendStudio 13.5.1 Mac

Powerful PHP integrated development environment

mPDF

mPDF

mPDF is a PHP library that can generate PDF files from UTF-8 encoded HTML. The original author, Ian Back, wrote mPDF to output PDF files "on the fly" from his website and handle different languages. It is slower than original scripts like HTML2FPDF and produces larger files when using Unicode fonts, but supports CSS styles etc. and has a lot of enhancements. Supports almost all languages, including RTL (Arabic and Hebrew) and CJK (Chinese, Japanese and Korean). Supports nested block-level elements (such as P, DIV),

Atom editor mac version download

Atom editor mac version download

The most popular open source editor

VSCode Windows 64-bit Download

VSCode Windows 64-bit Download

A free and powerful IDE editor launched by Microsoft

Zend Studio 13.0.1

Zend Studio 13.0.1

Powerful PHP integrated development environment