DevinXian · August 29, 2015 14:04 · Jul 31, 2014 · Jul 30, 2014 · Jul 30, 2014 · Jul 30, 2014
diff --git a/QuickSort b/QuickSort
@@ -1,7 +1,7 @@
 /**
  * 快速排序--降序
  * 思路：每次选定一基准元素，将数组划分成大于和小于基准元素的两部分，再分别对子序列进行排序，直到子序列长度为1
- * 效率：O(nlog2 n)
+ * 效率：O(nlog n)
  */
 function quick_sort(arr, start, end) {
     if (!arr instanceof Array) {

diff --git a/QuickSort b/QuickSort
@@ -1,5 +1,6 @@
 /**
  * 快速排序--降序
+ * 思路：每次选定一基准元素，将数组划分成大于和小于基准元素的两部分，再分别对子序列进行排序，直到子序列长度为1
  * 效率：O(nlog2 n)
  */
 function quick_sort(arr, start, end) {

diff --git a/QuickSort b/QuickSort
@@ -14,7 +14,7 @@ function quick_sort(arr, start, end) {
             while (!(arr[start] >= arr[i] || i == end));        //arr[i]比基准元素大，则++i
             do --j;
             while (!(arr[start] <= arr[j] || j == start));      //arr[j]比基准元素小，则--j
-            if (i < j) {                                        //arr[i]>基准元素，arr[j]<基准元素
+            if (i < j) {                                        //arr[i]<基准元素，arr[j]>基准元素
                 swap(arr, i, j);
             } else {
                 break;                                          //break while(true)

diff --git a/QuickSort b/QuickSort
@@ -1,7 +1,6 @@
 /**
  * 快速排序--降序
  * 效率：O(nlog2 n)
- * @Returns 排序结果
  */
 function quick_sort(arr, start, end) {
     if (!arr instanceof Array) {

diff --git a/QuickSort b/QuickSort
@@ -1,12 +1,37 @@
 /**
- * 快速排序
+ * 快速排序--降序
  * 效率：O(nlog2 n)
  * @Returns 排序结果
  */
-function quick_sort(arr, start, end){
-    if(!arr instanceof Array || start < 0 || end >= arr.length){
-        console.log('invalid arguments');
+function quick_sort(arr, start, end) {
+    if (!arr instanceof Array) {
+        console.log('invalid array');
         return;
     }
-    //TODO
-}
+    var i = start, j = end + 1;
+    if (start < end) {                                          //边界条件
+        while (true) {                                          //第一次划分基准元素选择arr[start]
+            do ++i;
+            while (!(arr[start] >= arr[i] || i == end));        //arr[i]比基准元素大，则++i
+            do --j;
+            while (!(arr[start] <= arr[j] || j == start));      //arr[j]比基准元素小，则--j
+            if (i < j) {                                        //arr[i]>基准元素，arr[j]<基准元素
+                swap(arr, i, j);
+            } else {
+                break;                                          //break while(true)
+            }
+        }
+        swap(arr, start, j);                                    //交换基准元素和arr[j]，完成一次划分
+        console.log('完成一次划分:' + arr);
+        quick_sort(arr, start, j - 1);
+        quick_sort(arr, j + 1, end);
+    }
+}
+
+function swap(arr, i, j) {
+    console.log('exchange: ' + arr[i] + ' <----> ' + arr[j]);
+    var tmp = arr[i];
+    arr[i] = arr[j];
+    arr[j] = tmp;
+}
+
diff --git a/Run QuickSort b/Run QuickSort
@@ -0,0 +1,7 @@
+Example:
+var arr = [2, 10, 1, 3, 5, 100, 8, 100000];
+quick_sort(arr, 0, arr.length - 2);
+console.log(arr);
+
+Result:
+[ 100, 10, 8, 5, 3, 2, 1, 100000 ]
diff --git a/QuickSort b/QuickSort
@@ -0,0 +1,12 @@
+/**
+ * 快速排序
+ * 效率：O(nlog2 n)
+ * @Returns 排序结果
+ */
+function quick_sort(arr, start, end){
+    if(!arr instanceof Array || start < 0 || end >= arr.length){
+        console.log('invalid arguments');
+        return;
+    }
+    //TODO
+}
No results found