一、交換排序
利用交換元素的位置進行排序的方法稱作交換排序。常用的交換排序的方法有冒泡排序和快速排 序。快速排序是一種分區交換排序方法。
二、冒泡排序
之前已經介紹過冒泡排序，點選打開連結
冒泡排序最好情況時間複雜度O(n)，冒泡排序最壞情況下時間複雜度O(n^2). 冒泡排序空間複雜度O(1)，冒泡排序是一種穩定的排序算法。
三、快速排序
快速排序，實際上是找一個基準值，将這個數組分成兩個部分,左邊部分的資料都比右邊部分的資料要小,再按照此方法對子區間進行劃分進行排序。
算法思想是：
1、開始時設定兩個變量left,right,給定一個基準值key。
2、left向後移,找到第一個比key值大的數,否則繼續向後走,。
3、right向前移,找到第一個比key小的數,否則繼續向前走。
4、判斷是否滿足條件left小于right,不滿足則交換,否則重複步驟2和步驟3,直到left和right相遇,這樣所有的數就有序。
遞歸：
void QuickSort(int *array, int left, int right)
{
if (left < right)
{
size_t div = Pation1(array, left, right);
//size_t div = Pation2(array, left, right);
//size_t div = Pation3(array, left, right);
QuickSort(array, left, div);
QuickSort(array, div + 1, right);
}
} 方法一：左右指針法
代碼如下：
int Pation1(int *array, int left, int right)
{
size_t begin = left;
size_t end = right - 1;
int key = array[end];
while (begin < end)
{
while (begin < end&&array[begin] <= key)
begin++;
while (begin < end&&array[end] >= key)
end--;
if (begin < end) //沒有相遇
swap(array[begin], array[end]);
}
if (begin!=right)
swap(array[begin], array[right-1]);
return begin;
} 方法二：挖坑法
先将最左邊或者最右邊取為基準值，保留這個值，這個位置就是起始坑，然後從左邊開始周遊，找到第一個比坑裡面的值大的數就交換，相當于用大的數填坑，以前的位置就會形成新的坑。然後我們可在右邊找比坑的值小的數入坑, 又會形成新的坑，這樣不斷周遊走子問題直到兩個坑相遇.
第一種類似隻是保留了key的值，換成坑，然後不斷找新的值去填坑,直到相遇。
//挖坑法
int Pation2(int *array, int left, int right)
{
size_t begin = left;
size_t end = right - 1;
int key = array[end];
while (begin < end)
{
while (begin < end&&array[begin] <= key)
begin++;
if (begin < end)
array[end--] = array[begin];
while (begin < end&&array[end] >= key)
end--;
if (begin < end)
array[begin++] = array[end];
}
array[begin] = key;
return begin;
} 方法三：
前兩種都是從兩邊周遊，第三種是從一邊取兩個指針。如下：
取兩個指針prev和cur,如下圖：
代碼如下：
int Pation3(int *array, int left, int right)
{
int key = array[right - 1];
//int key = GetMidDataIdx(array, left, right);
int cur = 0;
int pre = cur - 1;
while (cur < right)
{
//不相鄰
if (array[cur] < key&&pre++ != cur) //前者不成立後者不執行
swap(array[pre], array[cur]);
cur++;
}
if (++pre != right)
swap(array[pre], array[right - 1]);
return pre;
} 以上三種方法的基準值都是取最左或最右，若取的值是最小或者最大的值，效率就很低。我們可以用三數取中法。
它并不是選擇待排數組的第一個數作為中軸，而是選用待排數組最左邊、最右邊和最中間的三個元素的中間值作為中軸。
//三數取中
int GetMidDataIdx(int *array, int left, int right)
{
int mid = left + ((right - left) >> 1);
if (array[left] < array[right])
{
if (array[left]>array[mid])
return left;
else if (array[right] < array[mid])
return right;
else
return mid;
}
else
{
if (array[right]>array[mid])
return right;
else if (array[left] < array[mid])
return left;
else
return mid;
}
} 非遞歸
void QuickSortNor(int *array, int size)
{
int left = 0;
int right = size; //左閉右開
stack<int> s;
s.push(right);
s.push(left);
while (!s.empty())
{
left = s.top();
s.pop();
right = s.top();
s.pop();
if (left < right)
{
int div = Pation2(array, left, right);
//儲存右半部分區間
s.push(right);
s.push(div + 1);
//儲存左半部分區間
s.push(div);
s.push(left);
}
}
} 四、歸并排序
基本思想：将待排序的元素序列分成兩個長度相等的子序列，為每一個子序列排序，然後将他們合并成一個序列。合并兩個子序列的過程稱為兩路歸并。
第一步：劃分，為每一個子序列排序
第二步：歸并
void Merge(int *array, int left,int mid, int right, int *temp)
{
int index1 = left;
int index2 = mid;
int index = left;
while (index1 < mid&&index2 < right)
{
if (array[index1] < array[index2])
temp[index++] = array[index1++];
else
temp[index++] = array[index2++];
}
//如果有剩餘元素
while (index1 < mid)
temp[index++] = array[index1++];
while (index2 < right)
temp[index++] = array[index2++];
memcpy(array + left, temp + left, (right - left)*sizeof(int));
}
void _MergeSort(int *array, int left,int right,int *temp)
{
if (left + 1 < right)
{
int mid = left + ((right - left) >> 1);
_MergeSort(array, left, mid,temp);
_MergeSort(array, mid, right, temp);
Merge(array, left, mid, right,temp);
}
}
void MergeSort(int *array, int size)
{
int *temp = new int[size];
_MergeSort(array, 0, size, temp);
delete[] temp;
} //非遞歸
void MergeSortNor(int *array, int size)
{
int gap = 1;
int *temp = new int[size];
while (gap < size)
{
for (int i = 0; i < size; i += 2 * gap)
{
int left = i;
int mid = i + gap;
int right = mid + gap;
if (mid>size)
mid = size;
if (right>size)
right = size;
Merge(array, left, mid, right, temp);
}
gap *= 2;
}
delete[] temp;
}