当前位置:网站首页>Bubble sort
Bubble sort
2022-06-30 02:17:00 【Life needs depth】
Summary
This chapter introduces bubble sorting in sorting algorithm , Focus on the idea of bubble sorting .
Catalog
1. Introduction to bubble sort
2. Bubble sort graphic description
3. The time complexity and stability of bubble sorting
4. Bubble sort implementation
4.1 Bubble sort C Realization
4.2 Bubble sort C++ Realization
4.3 Bubble sort Java Realization
Reprint please indicate the source : Bubble sort - If the sky doesn't die - Blog Garden
More : Data structure and algorithm series Catalog
Introduction to bubble sort
Bubble sort (Bubble Sort), Also known as bubble sort or foam sort .
It is a relatively simple sorting algorithm . It will traverse several secondary sequences , Every time I traverse , It will compare the size of two adjacent numbers from front to back ; If the former is bigger than the latter , Then swap their positions . such , After a traversal , The largest element is at the end of the sequence ! When traversing again in the same way , The second largest element is arranged before the largest element . Repeat this operation , Until the whole sequence is in order !
Bubble sort graphic description
Bubble sort C Achieve one
void bubble_sort1(int a[], int n)
{
int i,j;
for (i=n-1; i>0; i--)
{
// take a[0...i] The largest data in is placed at the end
for (j=0; j<i; j++)
{
if (a[j] > a[j+1])
swap(a[j], a[j+1]);
}
}
}
The following is a sequence of numbers {20,40,30,10,60,50} For example , Demonstrate its bubble sorting process ( Here's the picture ).
Let's first analyze the 1 Trip to sort
When i=5,j=0 when ,a[0]<a[1]. here , Do nothing !
When i=5,j=1 when ,a[1]>a[2]. here , In exchange for a[1] and a[2] Value ; After the exchange ,a[1]=30,a[2]=40.
When i=5,j=2 when ,a[2]>a[3]. here , In exchange for a[2] and a[3] Value ; After the exchange ,a[2]=10,a[3]=40.
When i=5,j=3 when ,a[3]<a[4]. here , Do nothing !
When i=5,j=4 when ,a[4]>a[5]. here , In exchange for a[4] and a[5] Value ; After the exchange ,a[4]=50,a[3]=60.
therefore , The first 1 After sorting , The sequence {20,40,30,10,60,50} Turned into {20,30,10,40,50,60}. here , The value at the end of the sequence is the largest .
According to this method :
The first 2 After sorting , In sequence a[5...6] Is ordered .
The first 3 After sorting , In sequence a[4...6] Is ordered .
The first 4 After sorting , In sequence a[3...6] Is ordered .
The first 5 After sorting , In sequence a[1...6] Is ordered .
The first 5 After a sequence of times , The whole sequence is ordered .
Bubble sort C Achieve two
Observe the flow chart of bubble sorting above , The first 3 After a sequence of times , The data is already in order ; The first 4 Hu Hedi 5 There is no data exchange in this trip .
Let's optimize bubble sorting , Make it more efficient : Add a tag , If an exchange occurs in a single pass , Then it is marked with true, Otherwise false. If there is no exchange on a certain trip , Indicates that the sorting is complete !
void bubble_sort2(int a[], int n) { int i,j; int flag; // Mark for (i=n-1; i>0; i--) { flag = 0; // The initialization flag is 0 // take a[0...i] The largest data in is placed at the end for (j=0; j<i; j++) { if (a[j] > a[j+1]) { swap(a[j], a[j+1]); flag = 1; // In case of exchange , Set the flag to 1 } } if (flag==0) break; // If there is no exchange , The sequence is in order . } }
The time complexity and stability of bubble sorting
Bubble sort time complexity
The time complexity of bubble sorting is O(N2).
Let's assume that the sequence being sorted has N Number . The time complexity of traversing a trip is O(N), How many times does it take to traverse ?N-1 Time ! therefore , The time complexity of bubble sorting is O(N2).
Bubble sorting stability
Bubble sorting is a stable algorithm , It satisfies the definition of stable algorithm .
Algorithm stability -- Let's assume that there exists in a sequence a[i]=a[j], If before sorting ,a[i] stay a[j] front ; And after sorting ,a[i] Still in a[j] front . Then the sorting algorithm is stable !
Bubble sort implementation
Bubble sort C Realization
Implementation code (bubble_sort.c)
/**
* Bubble sort :C Language
*
* @author skywang
* @date 2014/03/11
*/
#include <stdio.h>
// The length of the array
#define LENGTH(array) ( (sizeof(array)) / (sizeof(array[0])) )
// Interactive values
#define swap(a,b) (a^=b,b^=a,a^=b)
/*
* Bubble sort
*
* Parameter description :
* a -- Array to sort
* n -- Length of array
*/
void bubble_sort1(int a[], int n)
{
int i,j;
for (i=n-1; i>0; i--)
{
// take a[0...i] The largest data in is placed at the end
for (j=0; j<i; j++)
{
if (a[j] > a[j+1])
swap(a[j], a[j+1]);
}
}
}
/*
* Bubble sort ( Improved version )
*
* Parameter description :
* a -- Array to sort
* n -- Length of array
*/
void bubble_sort2(int a[], int n)
{
int i,j;
int flag; // Mark
for (i=n-1; i>0; i--)
{
flag = 0; // The initialization flag is 0
// take a[0...i] The largest data in is placed at the end
for (j=0; j<i; j++)
{
if (a[j] > a[j+1])
{
swap(a[j], a[j+1]);
flag = 1; // In case of exchange , Set the flag to 1
}
}
if (flag==0)
break; // If there is no exchange , The sequence is in order .
}
}
void main()
{
int i;
int a[] = {20,40,30,10,60,50};
int ilen = LENGTH(a);
printf("before sort:");
for (i=0; i<ilen; i++)
printf("%d ", a[i]);
printf("\n");
bubble_sort1(a, ilen);
//bubble_sort2(a, ilen);
printf("after sort:");
for (i=0; i<ilen; i++)
printf("%d ", a[i]);
printf("\n");
}
Bubble sort C++ Realization
Implementation code (BubbleSort.cpp)
/**
* Bubble sort :C++
*
* @author skywang
* @date 2014/03/11
*/
#include <iostream>
using namespace std;
/*
* Bubble sort
*
* Parameter description :
* a -- Array to sort
* n -- Length of array
*/
void bubbleSort1(int* a, int n)
{
int i,j,tmp;
for (i=n-1; i>0; i--)
{
// take a[0...i] The largest data in is placed at the end
for (j=0; j<i; j++)
{
if (a[j] > a[j+1])
{
// In exchange for a[j] and a[j+1]
tmp = a[j];
a[j] = a[j+1];
a[j+1] = tmp;
}
}
}
}
/*
* Bubble sort ( Improved version )
*
* Parameter description :
* a -- Array to sort
* n -- Length of array
*/
void bubbleSort2(int* a, int n)
{
int i,j,tmp;
int flag; // Mark
for (i=n-1; i>0; i--)
{
flag = 0; // The initialization flag is 0
// take a[0...i] The largest data in is placed at the end
for (j=0; j<i; j++)
{
if (a[j] > a[j+1])
{
// In exchange for a[j] and a[j+1]
tmp = a[j];
a[j] = a[j+1];
a[j+1] = tmp;
flag = 1; // In case of exchange , Set the flag to 1
}
}
if (flag==0)
break; // If there is no exchange , The sequence is in order .
}
}
int main()
{
int i;
int a[] = {20,40,30,10,60,50};
int ilen = (sizeof(a)) / (sizeof(a[0]));
cout << "before sort:";
for (i=0; i<ilen; i++)
cout << a[i] << " ";
cout << endl;
bubbleSort1(a, ilen);
//bubbleSort2(a, ilen);
cout << "after sort:";
for (i=0; i<ilen; i++)
cout << a[i] << " ";
cout << endl;
return 0;
}
Bubble sort Java Realization
Implementation code (BubbleSort.java)
/**
* Bubble sort :Java
*
* @author skywang
* @date 2014/03/11
*/
public class BubbleSort {
/*
* Bubble sort
*
* Parameter description :
* a -- Array to sort
* n -- Length of array
*/
public static void bubbleSort1(int[] a, int n) {
int i,j;
for (i=n-1; i>0; i--) {
// take a[0...i] The largest data in is placed at the end
for (j=0; j<i; j++) {
if (a[j] > a[j+1]) {
// In exchange for a[j] and a[j+1]
int tmp = a[j];
a[j] = a[j+1];
a[j+1] = tmp;
}
}
}
}
/*
* Bubble sort ( Improved version )
*
* Parameter description :
* a -- Array to sort
* n -- Length of array
*/
public static void bubbleSort2(int[] a, int n) {
int i,j;
int flag; // Mark
for (i=n-1; i>0; i--) {
flag = 0; // The initialization flag is 0
// take a[0...i] The largest data in is placed at the end
for (j=0; j<i; j++) {
if (a[j] > a[j+1]) {
// In exchange for a[j] and a[j+1]
int tmp = a[j];
a[j] = a[j+1];
a[j+1] = tmp;
flag = 1; // In case of exchange , Set the flag to 1
}
}
if (flag==0)
break; // If there is no exchange , The sequence is in order .
}
}
public static void main(String[] args) {
int i;
int[] a = {20,40,30,10,60,50};
System.out.printf("before sort:");
for (i=0; i<a.length; i++)
System.out.printf("%d ", a[i]);
System.out.printf("\n");
bubbleSort1(a, a.length);
//bubbleSort2(a, a.length);
System.out.printf("after sort:");
for (i=0; i<a.length; i++)
System.out.printf("%d ", a[i]);
System.out.printf("\n");
}
}
above 3 The principle and output of the two implementations are the same . Here is their output :
before sort:20 40 30 10 60 50 after sort:10 20 30 40 50 60
边栏推荐
- Method of converting songs from DTS to MP3
- Knowledge payment cannot escape the essence of "anxiety"
- [MySQL 05] SUSE 12 SP5 modifies the MySQL password for the first time after installing MySQL
- dhu编程练习
- SCP remote copy command record
- 【MySQL 05】SUSE 12 SP5 安装MySQL后第一次修改mysql密码
- Alphassl digital certificate
- JS advanced -h5 new features
- The odoo15 page jumps directly to the editing status
- 9 — 正则校验集合
猜你喜欢
013_ slider
【自然语言处理】【多模态】OFA:通过简单的sequence-to-sequence学习框架统一架构、任务和模态
Le Code autojs peut - il être chiffré? Oui, présentation des techniques de chiffrement autojs
[Galaxy Kirin V10] [desktop] Firefox browser settings home page does not take effect
DMX configuration
003_ color
How to use SMS to deliver service information to customers? The guide is here!
如何使用SMS向客户传递服务信息?指南在这里!
一种跳板机的实现思路
Quick sort
随机推荐
Is it safe to open an account in Sinosteel futures?
dhu编程练习
DDoS attacks - are we really at war?
网上炒股安全么?炒股需要开户吗?
DHU programming exercise
Jenkins continuous integration environment construction VII (Jenkins parametric construction)
Global communication infrastructure faces apt, robotics and DDoS; The weakest mobile network
Four, forty, fourhundred swatches
Let‘sPlayCurling
Large scale DDoS attacks and simulated DDoS tests against VoIP providers
Knowledge payment cannot escape the essence of "anxiety"
Traffic, but no sales? 6 steps to increase website sales
DDoS "fire drill" service urges companies to prepare
7 — filter
【银河麒麟V10】【桌面】火狐浏览器设置主页不生效
如何制作CSR(Certificate Signing Request)文件?
记录生产的一次OOM异常
True love forever valentine's Day gifts
If mybaits cannot query the data, it can query how to change it in the database
Copy entire directory to output folder maintain folder structure- Copy entire directory to output folder maintaining the folder structure?