C++實現排序算法 代碼地址

vector<unsigned int> cVec;
int nSize = cVec.size();

1 冒泡排序

算法思路：
每兩兩相鄰的數值都會比較大小，前面比后面大的時候就交換位置，否則就不動。

代碼：

void BubbleSort() {//優化：//可以設置一個標記為，表示前一輪是否移動過數字，如果沒有則表示后一位均比前一位大//即數組已經有序bool flag =  true;//每次j循環完成后，表示數組的第i位是數組里最大的for (int i = nSize - 1; i > 0 && flag; --i) {flag = false;//從數組第一個值開始for (int j = 0; j < i; ++j) {//和后一個值比較，如果大于就交換位置if (cVec[j] > cVec[j + 1]) {std::swap(cVec[j], cVec[j + 1]);flag = true;}}}
}

每次i循環結束，cVec[i] 就是前i個最大的，就是每次循環結束，最大的那個值就會到最后面。所以j只到i

2 插入排序

算法思路：
假設前 i 個值有序（不包括 i），這時要排序i的時候就要將 i 和前面的值比較，找到一個位置j的值比他大的，這樣就將這個位置后面的值 [j+1,i-1] 全部后移，將 i 位置的值覆蓋。

void InsertSort() {for (int i = 1; i < nSize; ++i) {//這個是前i個數for (int j = 0; j < i; ++j) {if (cVec[i] < cVec[j]) {//這個是移動循環unsigned int temp = cVec[i];for (int k = i - 1; k >= j; --k) {cVec[k + 1] = cVec[k];}cVec[j] = temp;break;}}}
}

3 希爾排序

算法思路：
和插入算法類似，首先確定分組長度，即下標間隔為i的分為同一組：
當i=3時：
第1組為0,3,6,9
第2組為1,4,7,10
第3組為2,5,8
然后分別對這些分組進行插入排序，然后減少分組長度即 –i，重新確定分組，重新排序，直到i==0
第一個循環是確定分組長度，一般是數組長度的一半；
第二個循環是確定分組的起始下標，即分組的第一個下標位置
第三個循環和第四個循環和插入排序相同

void ShellSort() {//分組距離for (int i = nSize / 2; i > 0; i/=2) {//起始下標，即將[j]插入到前面去for (int j = 0; j < i ; ++j) {//k循環表示列舉每個分組的值		for (int k = j+i; k < nSize; k += i) {//l循環表示在前面的值中找到位置插入，因為j是第一個值的位置，所以要大于他for (int l = k; l > j; l -= i) {//如果當前位置的值比前一個位置的小就交換位置，否則就已經是有序了if (cVec[l] < cVec[l - i]) {std::swap(cVec[l], cVec[l - i]);}else {break;}}}}}
}

4 選擇排序

算法思路：
選擇個最大/最小的值，然后和數組的尾/頭交換位置
這里是選擇最小值的。

void sort::SelectSort() {//每次j循環結束，表示找到一個最小的值了for (int i = 0; i < nSize; ++i) {//假設m為當前最小值的下標位置int m = i;//在m后面的下標中找到比下標m還要小的值for (int j = i+1; j < nSize; ++j) {if (cVec[m] > cVec[j]) {m = j;}}//發現這個m的值改變了，就交換他們的位置if (m != i) {std::swap(cVec[m], cVec[i]);}}
}

5 快速排序

算法思路：
設置兩個變量b、e，分別保存數組的頭和尾的下標；
設置兩個變量bsite、esite保存剛開始時b、e的值；
再隨便找一個值flag，這里就找數組的第一個值 flag=cVec[b]；
0、如果b==e，表示數組里就只有1個數，那就沒必要排序了，直接返回就好了；
1、從數組后面開始找，找到第一個比flag小的值，即cVec[e]<flag；
2、交換他們的位置，這時cVec[e]后面的值都是比flag要大。
3、從數組前面開始找，找到第一個比flag大的值，即cVec[b]<flag；
4、交換他們的位置，這是**cVec[b]前面的值都是比cVec[b]**小的值；
5、比較 b 是否等于 e:
如果是的話表示 cVec[b] 前面的值都比它小，后面的值都比它大，這樣的話可以將數組以 cVec[b] 為界限，分成兩個數組，分別是 cVec[bsite]-cVec[b-1]、cVec[b+1]-cVec[esite]；
如果不是的話回到第1步繼續；

void quickSort(int b,int e) {if (b >= e) {return;}unsigned int flag = cVec[b];int bsite = b, esite = e;while (b < e) {while (b<e && flag <= cVec[e]) {--e;}if (flag > cVec[e]) {std::swap(cVec[b], cVec[e]);++b;}while (b < e && flag >= cVec[b]) {++b;}if (flag < cVec[b]) {std::swap(cVec[b], cVec[e]);--e;}}quickSort(e + 1, esite);quickSort(bsite, b-1);}

6 堆排序

算法思路：
堆分為大頂堆/小頂堆，表示雙親結點大于/小于子結點。
這里以大頂堆為例。
1、將數組構造成大頂堆，這樣cVec[0] 就是最大的值了；
2、然后將cVec[0] 和 cVec[nSize-1]（也就是最后一個值）交換位置，這樣nSize的值就減1，因為最后一個值已經是最大的；
3、交換位置后，數組就不是大頂堆了，這時又要重新構造大頂堆
4、重復2、3步，直到nSize為 0

現在問題是怎么構建大頂堆了：
每個結點的子結點的下標分別是：
左節點（left）：site * 2 + 1；
右結點（right）：site * 2 + 2；
這樣的話，可以從數組的中間位置nSize/2開始遞減，直到等于0：
從下標nSize/2開始，如果左右結點存在并且比父結點還大，就交換它們的位置，這樣父結點就比子結點大了。

那剩下的是構造大頂堆后，也交換值的位置，怎么將交換后的數組恢復回大頂堆呢？
1、首先看看左結點是否在數組的長度內，即 site*2+1 < nSize，在的話就往下執行，不在的話表示該結點沒有子結點，可以直接返回了。
2、比較cVec[site] 結點和 它的子結點cVec[site*2+1] 、cVec[site*2+2] 的大小；如果子結點存在且比它大，那就選最大的子結點就交換位置；如果子結點不存在那就直接返回
3、交換位置后就要修改site的值，保證site的子結點不會比它大，回到第1步，直到不存在子結點。

void buildHeapify(int site,int size) {int temp;int left = site * 2 + 1;int right = site * 2 + 2;temp = left;while (left < size) {//找到子結點中比較大的那個if (right < size && cVec[right] > cVec[left]) {temp = right;}//再和雙親結點比較大小，如果小于等于就結束if (cVec[site] >= cVec[temp]) {break;}//如果大于雙親結點就交換位置，并繼續往下調整std::swap(cVec[temp], cVec[site]);site = temp;left = site * 2 + 1;right = site * 2 + 2;temp = left;}}void initHeapify() {int half = nSize / 2;for (int j = half; j >= 0; --j) {buildHeapify(j,nSize);}
}void HeapSort() {initHeapify();//initHeapify構造出大頂堆for (int i = 0; i < nSize; ++i) {std::swap(cVec[0], cVec[nSize - 1 - i]);//調整結點位置恢復大頂堆buildHeapify(0,nSize-1-i);}
}

7 歸并排序

算法思路：
1、判斷當前數組長度是否為1，不是就往下，是就結束
2、將當前數組以nSize/2為中心分成兩段
3、對分成兩段的數組進行排序

這樣循環的話，將1個數組分成兩個數組，分別對這兩個數組進行排序，然后再將這兩個數組有序地合回1個數組

怎么將兩個數組合成一個有序數組：
1、比較兩個數組的首項大小，將比較小的值保存到一個臨時數組，移動首項的位置，即 ++；
2、重復第1步，直到其中一個數組將所有的數字都保存到臨時數組里面
3、將另一個數組剩下的值全都保存到臨時數組里面

這是整個臨時數組已經是有序的了，再將它存回到原始數組對應的位置就可以了

void mergeArray(int l,int r,int mid){std::vector<unsigned int> tempArray;int left = l;int right = mid+1;while (left <= mid&&right <= r) {while (left <= mid && cVec[left] <= cVec[right]) {tempArray.push_back(cVec[left++]);}while (right <= r && cVec[left] > cVec[right]) {tempArray.push_back(cVec[right++]);}}while (left <= mid) {tempArray.push_back(cVec[left++]);}while (right <= r) {tempArray.push_back(cVec[right++]);}for (int i = 0; i <tempArray.size(); i++) {cVec[l + i] = tempArray[i];}
}
void mergeSort(int l,int r) {if (l == r) {return;}int mid = (l + r) >> 1;mergeSort(l, mid);mergeSort(mid + 1, r);mergeArray(l,r,mid);}