Merge pull request #55 from chenshouao/master

shouao · web-flow · commit f56cfad812d5 · 2022-01-05T17:32:56.000+08:00
add c-plus-plus version&lsquo;s shell-sort and merge-sort
diff --git a/4.shellSort.md b/4.shellSort.md
@@ -144,3 +144,23 @@ function shellSort($arr)
     return $arr;
 }
 ```
+
+## 7. C++ &#20195;&#30721;&#23454;&#29616;
+
+```cpp
+void shellSort(vector<int>& arr) {
+    int gap = 1;
+    while (gap < (int)arr.size() / 3) {
+    	gap = gap * 3 + 1;
+    }
+    for (; gap >= 1; gap /= 3) {
+	for (int i = 0; i < gap; ++i) {
+	    for (int j = i + gap; j < arr.size(); j += gap) {
+		for (int k = j; k - gap >= 0 && arr[k] < arr[k - gap]; k -= gap) {
+                    swap(arr[k], arr[k - gap]);
+                }
+            }
+        }
+    }
+}
+```
diff --git a/5.mergeSort.md b/5.mergeSort.md
@@ -222,4 +222,41 @@ function merge($left, $right)
 
     return $result;
 }
-```
+```
+
+## 9. C++ &#20195;&#30721;&#23454;&#29616;
+
+```cpp
+void merge(vector<int>& arr, int l, int mid, int r) {
+    int index = 0;
+    int ptrL = l;
+    int ptrR = mid;
+    static vector<int>tempary;
+    if (arr.size() > tempary.size()) {
+        tempary.resize(arr.size());
+    }
+    while (ptrL != mid && ptrR != r) {
+        if (arr[ptrL] < arr[ptrR]) {
+            tempary[index++] = arr[ptrL++];
+        } else {
+            tempary[index++] = arr[ptrR++];
+        }
+    }
+    while (ptrL != mid) {
+        tempary[index++] = arr[ptrL++];
+    }
+    while (ptrR != r) {
+        tempary[index++] = arr[ptrR++];
+    }
+    copy(tempary.begin(), tempary.begin() + index, arr.begin() + l);
+}
+void mergeSort(vector<int>& arr, int l, int r) { // sort the range [l, r) in arr
+    if (r - l <= 1) {
+        return;
+    }
+    int mid = (l + r) / 2;
+    mergeSort(arr, l, mid);
+    mergeSort(arr, mid, r);
+    merge(arr, l, mid, r);
+}
+```
