Last active
June 7, 2019 18:43
-
-
Save black-black-cat/e899c9fa87d2ae35d13425ae5751f506 to your computer and use it in GitHub Desktop.
快速排序、选择排序、冒泡排序, merge sort
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| <!doctype html> | |
| <html lang="en"> | |
| <head> | |
| <meta charset="utf-8"> | |
| <title>GistRun</title> | |
| <!--<link rel="stylesheet" href="styles.css">--> | |
| </head> | |
| <body> | |
| <h1>Hello world!</h1> | |
| <script src="sort.js"></script> | |
| <script src="mergeSort.js"></script> | |
| </body> | |
| </html> |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| function mergeSort (arr, start, end) { | |
| if (start >= end) { | |
| return | |
| } | |
| let mid = Math.floor((end - start) / 2) + start | |
| let start1 = start | |
| let end1 = mid | |
| let start2 = mid + 1 | |
| let end2 = end | |
| let orderedArr = [] | |
| let k = start | |
| mergeSort(arr, start, mid) | |
| mergeSort(arr, mid + 1, end) | |
| while (start1 <= end1 && start2 <= end2) { | |
| orderedArr[k++] = arr[start1] < arr[start2] | |
| ? arr[start1++] | |
| : arr[start2++] | |
| } | |
| while (start1 <= end1) { | |
| orderedArr[k++] = arr[start1++] | |
| } | |
| while (start2 <= end2) { | |
| orderedArr[k++] = arr[start2++] | |
| } | |
| for (let i = start; i <= end; i++) { | |
| arr[i] = orderedArr[i] | |
| } | |
| return arr | |
| } | |
| function getRandomArr () { | |
| let str = Math.random() + '' | |
| let arr = str.replace(/^0\.?/, '').split('') | |
| return arr.map(s => s - 0) | |
| } | |
| let t = getRandomArr() | |
| console.log(mergeSort(t, 0, t.length - 1)) |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| function sort (arr, left, right) { | |
| if (left >= right || !arr || arr.length <= 1) { | |
| return | |
| } | |
| left = left != null ? left : 0 | |
| right = right != null ? right : arr.length - 1 | |
| let l = left | |
| let r = right | |
| let pivot = arr[(left+right) / 2 | 0] | |
| while (l <= r) { | |
| while (arr[l] < pivot) { | |
| l++ | |
| } | |
| while (arr[r] > pivot) { | |
| r-- | |
| } | |
| if (l < r) { | |
| swap(arr, l, r) | |
| l++ | |
| r-- | |
| } else if (l === r) { | |
| l++ | |
| } | |
| } | |
| _sort(arr, left, r) | |
| _sort(arr, l, right) | |
| } | |
| function swap(arr, a, b) { | |
| var t = arr[a] | |
| arr[a] = arr[b] | |
| arr[b] = t | |
| } | |
| function quickSort(arr, {clone = true} = {}) { | |
| if (clone) { | |
| arr = arr.slice(0) | |
| } | |
| sort(arr, 0, arr.length - 1) | |
| return arr | |
| } | |
| var selectSort = function (arr) { | |
| var i,a,b = arr.length - 1 | |
| for (;0<b;b--) { | |
| a = 0 | |
| for (i = 0; i <= b; i++) { | |
| arr[a] < arr[i] && (a = i) | |
| } | |
| swap(arr, a, b) | |
| } | |
| return arr | |
| } | |
| var popSort = function (arr) { | |
| var i,end = arr.length - 1 | |
| for (; 0 < end; end--) { | |
| for (i = 0; i < end; i++) { | |
| arr[i] > arr[i + 1] && swap(arr, i, i+1) | |
| } | |
| } | |
| return arr | |
| } | |
| // exports.quickSort = quickSort | |
| // exports.selectSort = selectSort | |
| // exports.popSort = popSort |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment