常見的交換排序算法有冒泡排序和快速排序
冒泡排序
冒泡排序算法的基本原理如下：（從后往前）
1. 比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。
2. 對每一對相鄰元素作同樣的工作，從開始第一對到結(jié)尾的最后一對。在這一點，最后
3. 的元素應(yīng)該會是大的數(shù)。
4. 針對所有的元素重復(fù)以上的步驟，除了最后一個。
5. 持續(xù)每次對越來越少的元素重復(fù)上面的步驟，直到?jīng)]有任何一對數(shù)字需要比較。
算法示意圖如下：動畫演示經(jīng)過優(yōu)化過后的代碼如下：
重慶分公司
重慶分公司
void BubbleSort(int* a, size_t n) //冒泡排序優(yōu)化版
{
assert(a);
bool flag = true;
for (int i = 0; i < n - 1 && flag; ++i)
{
flag = false;
for (int j = 1; j < n - i; ++j)
{
if (a[j - 1] > a[j])
{
std::swap(a[j - 1], a[j]);
flag = true;
}
}
}
}性能分析
若文件的初始狀態(tài)是正序的，一趟掃描即可完成排序，所以，冒泡排序最好時間
復(fù)雜度為O(N)。
若初始文件是反序的，需要進行 N -1 趟排序。每趟排序要進行 N - i 次關(guān)鍵字的
比較(1 ≤ i ≤ N - 1)。在這種情況下，比較和移動次數(shù)均達到大值，所以，冒泡排
序的最壞時間復(fù)雜度為O(N2)。
因此，冒泡排序的平均時間復(fù)雜度為O(N2)。
總結(jié)起來，其實就是一句話：當數(shù)據(jù)越接近正序時，冒泡排序性能越好。
穩(wěn)定性
冒泡排序就是把小的元素往前調(diào)或者把大的元素往后調(diào)。比較是相鄰的兩個元素比
較，交換也發(fā)生在這兩個元素之間。
所以相同元素的前后順序并沒有改變，所以冒泡排序是一種穩(wěn)定排序算法。
快速排序
快速排序的基本原理：
1.通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨立的兩部分：分割點左邊都是比它小
的數(shù)，右邊都是比它大的數(shù)。
2. 然后再按此方法對這兩部分數(shù)據(jù)分別進行快速排序，整個排序過程可以遞歸
進行，以此達到整個數(shù)據(jù)變成有序序列。
算法示意圖如下：
代碼如下：
比較直觀的代碼：
int Partition(int* a, int left, int right)
{
assert(a);
int key = a[right];
int begin = left;
int end = right - 1;
while (begin < end)
{
while (begin < end && a[begin] <= key)
{
++begin;
}
while (begin < end && a[end] >= key)
{
--end;
}
std::swap(a[begin], a[end]);
}
if (a[begin] > key) // 大于key再交換
{
std::swap(a[begin], a[right]);
return begin;
}
else
{
return right;
}
}
void QuickSort(int* a, int left, int right)
{
assert(a);
if (left < right)
{
int pivotloc = Partition(a, left, right);
QuickSort(a, left, pivotloc-1);
QuickSort(a, pivotloc+1, right);
}
}比較簡單的代碼：（挖坑填數(shù)發(fā)）
int Partition(int* a, int left, int right)
{
assert(a);
int base = a[left];
while (left < right)
{
while (left < right && a[right] >= base) //注意這里一定要有等于
--right; //否則會有死循環(huán)
a[left] = a[right];
while (left < right && a[left] <= base)
++left;
a[right] = a[left];
}
a[left] = base;
return left;
}
void QuickSort(int* a, int left, int right)
{
assert(a);
if (left < right)
{
int pivotloc = Partition(a, left, right);
QuickSort(a, left, pivotloc-1);
QuickSort(a, pivotloc+1, right);
}
}非遞歸寫法：
void QuickSortNoRe(int* a, int left, int right) //快排非遞歸
{
assert(a);
if (left >= right)
return;
stack st;
st.push(right);
st.push(left);
while (!st.empty())
{
int _left = st.top();
st.pop();
int _right = st.top();
st.pop();
int mid = Partition(a, _left, _right);
if (_left < mid - 1)
{
st.push(mid - 1);
st.push(_left);
}
if (mid + 1 < _right)
{
st.push(_right);
st.push(mid + 1);
}
}
} 性能分析
而當數(shù)據(jù)隨機分布時，以第一個關(guān)鍵字為基準分為兩個子序列，兩個子序列的元素
個數(shù)接近相等，此時執(zhí)行效率最好。
當每次遞歸的基準值都是當前區(qū)間中大或者最小的數(shù)時，此時效率最差
穩(wěn)定性
在快速排序中，相等元素可能會因為分區(qū)而交換順序，所以它是不穩(wěn)定的算法。
創(chuàng)新互聯(lián)www.cdcxhl.cn，專業(yè)提供香港、美國云服務(wù)器，動態(tài)BGP最優(yōu)骨干路由自動選擇，持續(xù)穩(wěn)定高效的網(wǎng)絡(luò)助力業(yè)務(wù)部署。公司持有工信部辦法的idc、isp許可證， 機房獨有T級流量清洗系統(tǒng)配攻擊溯源，準確進行流量調(diào)度，確保服務(wù)器高可用性。佳節(jié)活動現(xiàn)已開啟，新人活動云服務(wù)器買多久送多久。
