<> bubble sort
Bubble sort is the most classic method , One of the most basic sorting algorithms . This algorithm is widely used in engineering practice , But job interviews ,ACM competition ,CCF In the case of certification examination and so on, it can't be used , Because this algorithm is not technical and time-consuming . Bubble sorting is one of the algorithms that every programming learner can easily master and must master .
<> stability ： stable
So called stable sorting algorithm , When there are multiple identical values in the original data , The relative positions of these values remain unchanged after sorting .
What's the use of this stability ? For example, a company should count the turnover of all departments , Rank these departments according to their turnover , When the turnover of two departments is the same, they keep the original order
, For this kind of problem, we need to use a stable sorting algorithm to deal with it .
<> Time complexity ： O(n2)
<> Spatial complexity ： O(1)
Bubble sort process does not include the original data storage process , So the spatial complexity is O(1) instead of O(n).
<> Algorithm explanation
Take sorting from small to large as an example , The idea of bubble sort method is ：
Traverse raw data , Start with the first number , To the end of the penultimate
, Compare the size of this number with that of the next , If this number is larger than the next one , Then exchange the two numbers . This will move the largest number in the data to the end of the array .
Then traverse the original data again , But it starts with the first number , To the end of the penultimate
, Compare the size of this number with that of the next , If this number is larger than the next one , Then exchange the two numbers . This transfers the second largest number to the penultimate bit of the array .
Repeat the above process , All the way to the first number , At the end of the second number , Thus the sorting process is completed .
Because this cycle is like a bubble rising , So it's called bubble sort .
Next, use an example to demonstrate the whole sorting process .
notes ： In the picture , Red represents the two numbers to compare , Blue stands for exchange （ Or not ） The last two numbers , Green represents the part that has been sorted .
<>C/C++ code
<> The functional form of the algorithm
Sort from small to large ：
// Header file #include <vector> using namespace std; // Sort from small to large void bubbleSort_MinToMax(
vector<int> &numberList) { int N = numberList.size(); for (int i = 1; i < N; i++
) { for (int j = 0; j < N - i; j++) { if (numberList[j] > numberList[j + 1]) {
// exchange int buffer = numberList[j]; numberList[j] = numberList[j + 1]; numberList[j
+ 1] = buffer; } } } }
Sort from big to small ：
// Header file #include <vector> using namespace std; // Sort from big to small void bubbleSort_MaxToMin(
vector<int> &numberList) { int N = numberList.size(); for (int i = 1; i < N; i++
) { for (int j = 0; j < N - i; j++) { if (numberList[j] < numberList[j + 1]) {
// exchange int buffer = numberList[j]; numberList[j] = numberList[j + 1]; numberList[j
+ 1] = buffer; } } } }
<> Complete procedure ：
#include <iostream> #include <vector> using namespace std; // Sort from small to large void
bubbleSort_MinToMax(vector<int> &numberList) { int N = numberList.size(); for (
int i = 1; i < N; i++) { for (int j = 0; j < N - i; j++) { if (numberList[j] >
numberList[j + 1]) { // exchange int buffer = numberList[j]; numberList[j] = numberList
[j + 1]; numberList[j + 1] = buffer; } } } } // Sort from big to small void bubbleSort_MaxToMin(
vector<int> &numberList) { int N = numberList.size(); for (int i = 1; i < N; i++
) { for (int j = 0; j < N - i; j++) { if (numberList[j] < numberList[j + 1]) {
// exchange int buffer = numberList[j]; numberList[j] = numberList[j + 1]; numberList[j
+ 1] = buffer; } } } } int main() { // Input raw data // The original data is ：2 9 4 3 6 0 5 8 7 1 vector<
int> numberList; numberList.push_back(2); numberList.push_back(9); numberList.
push_back(4); numberList.push_back(3); numberList.push_back(6); numberList.
push_back(0); numberList.push_back(5); numberList.push_back(8); numberList.
push_back(7); numberList.push_back(1); // Print raw data int N = numberList.size(); for (
int i = 0; i < N; i++) { cout << numberList[i]; if (i == N - 1) { cout << endl;
} else { cout << " "; } } // Bubble sort bubbleSort_MinToMax(numberList);// from small to large
//bubbleSort_MaxToMin(numberList);// From big to small // Print sorted data for (int i = 0; i < N; i++)
{ cout << numberList[i]; if (i == N - 1) { cout << endl; } else { cout << " "; }
} //system("pause");//vs We need to add this sentence in the environment return 0; }
Program running results
Technology