更新 quicksort.py

Reviewed-on: #4

.gitea/workflows/build.yml

@@ -1,8 +1,17 @@
-name: OpenAI Code Review
-uses: bhavik/gitea-code-review-action@v0.1
-with:
-    PROGRAMMING_LANGUAGE: 'JavaScript'
-    REVIEW_COMMENT_PREFIX: 'openai:'
-    FULL_REVIEW_COMMENT: 'openai'
-    OPENAI_TOKEN: ${{ secrets.OPENAI_TOKEN }}
-    GITHUB_TOKEN: ${{ secrets.GH_TOKEN }}
+name: Code Review
+on:
+  issue_comment:
+    types: [created, edited]
+
+jobs:
+  code-review:
+    runs-on: ubuntu-latest
+    steps:
+    - name: OpenAI Code Review
+      uses: bhavik/gitea-code-review-action@v0.1
+      with:
+        PROGRAMMING_LANGUAGE: 'JavaScript'
+        OPENAI_TOKEN: ${{ secrets.OPENAI_TOKEN }}
+        GITHUB_TOKEN: ${{ secrets.GH_TOKEN }}
+        FULL_REVIEW_COMMENT: 'openai'
+        REVIEW_COMMENT_PREFIX: 'openai:'

js/quicksort.js

@@ -4,9 +4,13 @@
  * 空间复杂度: O(log n)
  */
 
-// 基本快速排序实现
+/**
+ * 快速排序主函数
+ * @param {Array} arr - 要排序的数组
+ * @returns {Array} - 排序后的数组
+ */
 function quickSort(arr) {
-    // 基本情况：如果数组长度小于等于1，直接返回
+    // 如果数组长度小于等于1，直接返回
     if (arr.length <= 1) {
         return arr;
     }
@@ -25,157 +29,127 @@ function quickSort(arr) {
         }
     }
     
-    // 递归排序左右两部分，然后合并
+    // 递归排序左右两部分，并合并结果
     return [...quickSort(left), pivot, ...quickSort(right)];
 }
 
-// 原地快速排序（更高效，不创建新数组）
-function quickSortInPlace(arr, left = 0, right = arr.length - 1) {
-    if (left < right) {
-        const pivotIndex = partition(arr, left, right);
-        quickSortInPlace(arr, left, pivotIndex - 1);
-        quickSortInPlace(arr, pivotIndex + 1, right);
+/**
+ * 原地快速排序（优化版本，节省空间）
+ * @param {Array} arr - 要排序的数组
+ * @param {number} low - 起始索引
+ * @param {number} high - 结束索引
+ */
+function quickSortInPlace(arr, low = 0, high = arr.length - 1) {
+    if (low < high) {
+        const pivotIndex = partition(arr, low, high);
+        quickSortInPlace(arr, low, pivotIndex - 1);
+        quickSortInPlace(arr, pivotIndex + 1, high);
     }
     return arr;
 }
 
-// 分区函数
-function partition(arr, left, right) {
-    // 选择最右边的元素作为基准值
-    const pivot = arr[right];
-    let i = left - 1;
+/**
+ * 分区函数
+ * @param {Array} arr - 数组
+ * @param {number} low - 起始索引
+ * @param {number} high - 结束索引
+ * @returns {number} - 基准值的最终位置
+ */
+function partition(arr, low, high) {
+    // 选择最后一个元素作为基准值
+    const pivot = arr[high];
+    let i = low - 1; // 小于基准值的元素的最后位置
     
-    // 将小于基准值的元素移到左边
-    for (let j = left; j < right; j++) {
+    for (let j = low; j < high; j++) {
+        // 如果当前元素小于等于基准值
         if (arr[j] <= pivot) {
             i++;
-            [arr[i], arr[j]] = [arr[j], arr[i]]; // 交换元素
-        }
-    }
-    
-    // 将基准值放到正确的位置
-    [arr[i + 1], arr[right]] = [arr[right], arr[i + 1]];
-    return i + 1;
-}
-
-// 优化的快速排序（三数取中法选择基准值）
-function quickSortOptimized(arr, left = 0, right = arr.length - 1) {
-    if (left < right) {
-        const pivotIndex = partitionOptimized(arr, left, right);
-        quickSortOptimized(arr, left, pivotIndex - 1);
-        quickSortOptimized(arr, pivotIndex + 1, right);
-    }
-    return arr;
-}
-
-// 优化的分区函数（三数取中法）
-function partitionOptimized(arr, left, right) {
-    // 三数取中法选择基准值
-    const mid = Math.floor((left + right) / 2);
-    const pivot = medianOfThree(arr, left, mid, right);
-    
-    // 将基准值移到最右边
-    [arr[pivot], arr[right]] = [arr[right], arr[pivot]];
-    
-    let i = left - 1;
-    
-    for (let j = left; j < right; j++) {
-        if (arr[j] <= arr[right]) {
-            i++;
+            // 交换元素
             [arr[i], arr[j]] = [arr[j], arr[i]];
         }
     }
     
-    [arr[i + 1], arr[right]] = [arr[right], arr[i + 1]];
+    // 将基准值放到正确的位置
+    [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];
     return i + 1;
 }
 
-// 三数取中法
-function medianOfThree(arr, left, mid, right) {
-    const a = arr[left];
-    const b = arr[mid];
-    const c = arr[right];
-    
-    if (a < b) {
-        if (b < c) return mid;
-        else if (a < c) return right;
-        else return left;
-    } else {
-        if (a < c) return left;
-        else if (b < c) return right;
-        else return mid;
+/**
+ * 三路快速排序（处理重复元素较多的数组）
+ * @param {Array} arr - 要排序的数组
+ * @param {number} low - 起始索引
+ * @param {number} high - 结束索引
+ */
+function quickSortThreeWay(arr, low = 0, high = arr.length - 1) {
+    if (low < high) {
+        const [lt, gt] = partitionThreeWay(arr, low, high);
+        quickSortThreeWay(arr, low, lt - 1);
+        quickSortThreeWay(arr, gt + 1, high);
     }
+    return arr;
+}
+
+/**
+ * 三路分区函数
+ * @param {Array} arr - 数组
+ * @param {number} low - 起始索引
+ * @param {number} high - 结束索引
+ * @returns {Array} - [lt, gt] 小于和大于基准值的边界
+ */
+function partitionThreeWay(arr, low, high) {
+    const pivot = arr[low];
+    let lt = low;     // 小于基准值的右边界
+    let gt = high;    // 大于基准值的左边界
+    let i = low + 1;  // 当前扫描位置
+    
+    while (i <= gt) {
+        if (arr[i] < pivot) {
+            [arr[lt], arr[i]] = [arr[i], arr[lt]];
+            lt++;
+            i++;
+        } else if (arr[i] > pivot) {
+            [arr[gt], arr[i]] = [arr[i], arr[gt]];
+            gt--;
+        } else {
+            i++;
+        }
+    }
+    
+    return [lt, gt];
 }
 
 // 测试函数
 function testQuickSort() {
     console.log("=== 快速排序算法测试 ===");
     
-    // 测试用例
+    // 测试数据
     const testCases = [
         [64, 34, 25, 12, 22, 11, 90],
         [5, 2, 4, 6, 1, 3],
         [1],
         [],
-        [3, 3, 3, 3],
-        [9, 8, 7, 6, 5, 4, 3, 2, 1]
+        [3, 3, 3, 3, 3],
+        [9, 8, 7, 6, 5, 4, 3, 2, 1],
+        [1, 2, 3, 4, 5, 6, 7, 8, 9]
     ];
     
     testCases.forEach((testCase, index) => {
-        console.log(`\n测试用例 ${index + 1}: [${testCase.join(', ')}]`);
+        console.log(`\n测试用例 ${index + 1}:`);
+        console.log(`原始数组: [${testCase}]`);
         
-        // 测试基本快速排序
-        const arr1 = [...testCase];
-        const result1 = quickSort(arr1);
-        console.log(`基本快速排序: [${result1.join(', ')}]`);
+        // 测试标准快速排序
+        const sorted1 = quickSort([...testCase]);
+        console.log(`标准快排: [${sorted1}]`);
         
         // 测试原地快速排序
         const arr2 = [...testCase];
-        const result2 = quickSortInPlace(arr2);
-        console.log(`原地快速排序: [${result2.join(', ')}]`);
-        
-        // 测试优化快速排序
-        const arr3 = [...testCase];
-        const result3 = quickSortOptimized(arr3);
-        console.log(`优化快速排序: [${result3.join(', ')}]`);
-    });
-}
-
-// 性能测试函数
-function performanceTest() {
-    console.log("\n=== 性能测试 ===");
-    
-    // 生成随机数组
-    const generateRandomArray = (size) => {
-        return Array.from({length: size}, () => Math.floor(Math.random() * 1000));
-    };
-    
-    const sizes = [100, 1000, 10000];
-    
-    sizes.forEach(size => {
-        const arr = generateRandomArray(size);
-        console.log(`\n数组大小: ${size}`);
-        
-        // 测试基本快速排序
-        const arr1 = [...arr];
-        const start1 = performance.now();
-        quickSort(arr1);
-        const end1 = performance.now();
-        console.log(`基本快速排序: ${(end1 - start1).toFixed(2)}ms`);
-        
-        // 测试原地快速排序
-        const arr2 = [...arr];
-        const start2 = performance.now();
         quickSortInPlace(arr2);
-        const end2 = performance.now();
-        console.log(`原地快速排序: ${(end2 - start2).toFixed(2)}ms`);
+        console.log(`原地快排: [${arr2}]`);
         
-        // 测试优化快速排序
-        const arr3 = [...arr];
-        const start3 = performance.now();
-        quickSortOptimized(arr3);
-        const end3 = performance.now();
-        console.log(`优化快速排序: ${(end3 - start3).toFixed(2)}ms`);
+        // 测试三路快速排序
+        const arr3 = [...testCase];
+        quickSortThreeWay(arr3);
+        console.log(`三路快排: [${arr3}]`);
     });
 }
 
@@ -184,9 +158,9 @@ if (typeof module !== 'undefined' && module.exports) {
     module.exports = {
         quickSort,
         quickSortInPlace,
-        quickSortOptimized,
-        testQuickSort,
-        performanceTest
+        quickSortThreeWay,
+        partition,
+        partitionThreeWay
     };
 }
 
@@ -195,14 +169,8 @@ if (typeof window !== 'undefined') {
     // 将函数添加到全局作用域
     window.quickSort = quickSort;
     window.quickSortInPlace = quickSortInPlace;
-    window.quickSortOptimized = quickSortOptimized;
-    window.testQuickSort = testQuickSort;
-    window.performanceTest = performanceTest;
+    window.quickSortThreeWay = quickSortThreeWay;
     
-    console.log("快速排序算法已加载，可以使用以下函数：");
-    console.log("- quickSort(arr): 基本快速排序");
-    console.log("- quickSortInPlace(arr): 原地快速排序");
-    console.log("- quickSortOptimized(arr): 优化快速排序");
-    console.log("- testQuickSort(): 运行测试用例");
-    console.log("- performanceTest(): 运行性能测试");
+    // 自动运行测试
+    testQuickSort();
 } 

quicksort.py

@@ -0,0 +1,14 @@
+def quick_sort(arr):
+    if len(arr) <= 1:
+        return arr  
+    pivot = arr[len(arr) // 2]  # 选取中间元素作为基准
+    left = [x for x in arr if x < pivot]
+    middle = [x for x in arr if x == pivot]
+    right = [x for x in arr if x > pivot]
+    return quick_sort(left) + middle + quick_sort(right)
+
+
+# 示例
+nums = [3, 6, 8, 10, 1, 2, 1]
+print("排序前：", nums)
+print("排序后：", quick_sort(nums))