排序的穩(wěn)定性
對于一個排序算法，假設兩個相同的元素Ai和Aj·
在排序前這兩個元素滿足條件i<j，即Ai在Aj之前·
在排序后Ai仍在Aj之前，則稱為排序算法為穩(wěn)定排序·
否則稱這個算法為不穩(wěn)定排序
穩(wěn)定性的說明
排序的穩(wěn)定性并不影響排序算法的效率，穩(wěn)定性只對類/結構體類型數據有影響
冒泡排序
這里全部以從小到大(升序)為例講解
冒泡排序介紹
基本思想:每輪不斷將元素進行兩兩比較，并按“前小后大"規(guī)則交換實現思路:
比較相鄰元素，若前者大于后者，兩元素進行交換
對每組相鄰元素，實現上述步驟，在第一輪結束后，最后一個元素即為最大值重復上述步驟，每次比較次數減1，直到無需比較，排序結束
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;
void bubbleSort(int arr[], int len)
{
//外層循環(huán) len-1次
for (int i = 0; i < len - 1; i++)
{
//內層循環(huán)len-i-1
for (int j = 0; j < len - i - 1; j++)
{
//相鄰元素，前者大于后者，進行交換
if (arr[j]>arr[j+1])
{
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
//打印數組
void printArray(int arr[], int len)
{
for (int i = 0; i < len; i++)
{
cout << arr[i] << "";
}
cout << endl;
}
void test01()
{
int arr[8] = { 2,5,4,5,7,1,3,6 };
//數組中的元素個數
int len = sizeof(arr) / sizeof(int);
//調用冒泡排序
bubbleSort(arr, len);
//打印數組
printArray(arr, len);
}
int main()
{
test01();
system("pause");
return EXIT_SUCCESS;
}
優(yōu)化后的冒泡排序
我們先觀察此冒泡排序的具體的步驟，用下面這段代碼即可實現
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;
//打印數組
void printArray(int arr[], int len)
{
for (int i = 0; i < len; i++)
{
cout << arr[i] << "";
}
cout << endl;
}
void bubbleSort(int arr[], int len)
{
//外層循環(huán) len-1次
for (int i = 0; i < len - 1; i++)
{
//內層循環(huán)len-i-1
for (int j = 0; j < len - i - 1; j++)
{
//相鄰元素，前者大于后者，進行交換
if (arr[j] > arr[j + 1])
{
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
//打印數組
printArray(arr, len);
}
}
void test01()
{
int arr[8] = { 2,5,4,5,7,1,3,6 };
//數組中的元素個數
int len = sizeof(arr) / sizeof(int);
//調用冒泡排序
bubbleSort(arr, len);
}
int main()
{
test01();
system("pause");
return EXIT_SUCCESS;
}
下面是優(yōu)化后的冒泡排序
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;
//打印數組
void printArray(int arr[], int len)
{
for (int i = 0; i < len; i++)
{
cout << arr[i] << "";
}
cout << endl;
}
void bubbleSort2(int arr[], int len)
{
bool flag = true;//true 代表交換過 false代表還沒交換
//外層循環(huán) len-1次
for (int i = 0; i < len - 1; i++)
{
flag = false;//每輪初始化狀態(tài)為真
//內層循環(huán)len-i-1
for (int j = 0; j < len - i - 1; j++)
{
//相鄰元素，前者大于后者，進行交換
if (arr[j]>arr[j+1])
{
flag = true;//發(fā)生交換 狀態(tài)改為真
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
if (flag==false)
{
break;
}
printArray(arr, len);
}
}
void test02()
{
int arr[8] = { 2,5,4,5,7,1,3,6 };
//數組中的元素個數
int len = sizeof(arr) / sizeof(int);
//調用冒泡排序
bubbleSort2(arr, len);
}
int main()
{
test02();
system("pause");
return EXIT_SUCCESS;
}
最終代碼
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;
//打印數組
void printArray(int arr[], int len)
{
for (int i = 0; i < len; i++)
{
cout << arr[i] << "";
}
cout << endl;
}
void bubbleSort2(int arr[], int len)
{
bool flag = true;//true 代表交換過 false代表還沒交換
//外層循環(huán) len-1次
for (int i = 0; i < len - 1 && flag==true; i++)
{
flag = false;//每輪初始化狀態(tài)為真
//內層循環(huán)len-i-1
for (int j = 0; j < len - i - 1; j++)
{
//相鄰元素，前者大于后者，進行交換
if (arr[j]>arr[j+1])
{
flag = true;//發(fā)生交換 狀態(tài)改為真
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
void test02()
{
int arr[8] = { 2,5,4,5,7,1,3,6 };
//數組中的元素個數
int len = sizeof(arr) / sizeof(int);
//調用冒泡排序
bubbleSort2(arr, len);
//打印
printArray(arr, len);
}
int main()
{
test02();
system("pause");
return EXIT_SUCCESS;
}
文章來源：http://www.zghlxwxcb.cn/news/detail-456627.html
冒泡排序的復雜度
文章來源地址http://www.zghlxwxcb.cn/news/detail-456627.html
到了這里，關于排序算法——冒泡排序詳解及優(yōu)化的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網！
