Algorithm in Action

알고리즘이 작동합니다

알고리즘에 대한 나의 관행 중 일부 :)이 저장소는 알고리즘 플랫폼에 대한 내 답을 보유하고 있으며 코드에 필요한 주석을 보유합니다. 반드시 최상의 솔루션은 아니지만 코드가 간결하고 이해하기 쉽도록 노력합니다. 나는 또한 앞으로 다른 질문 은행을 통합 할 것입니다. 당신이 어떤 오류를 발견하면, 나는 당신이 나에게 말하거나 그들을 해결하도록 도울 수 있기를 바랍니다. 매우 감사합니다!

목록

• 코디 르
• 레 코드
• 제안을 목표로하는 검
• 프로그래머 인터뷰 가이드

 /**
 * 快速排序
 */
public class QuickSort {
    public void sort ( Comparable [] arr ) {
        sort ( arr , 0 , arr . length - 1 );
    }
    
    private void sort ( Comparable [] arr , int lo , int hi ) {
        if ( lo >= hi ) {
            return ;
        }
        // 切分
        int j = partition ( arr , lo , hi );
        // 将左半部分 arr[lo, j-1] 排序
        sort ( arr , lo , j - 1 );
        // 将右半部分 arr[j+1, hi] 排序
        sort ( arr , j + 1 , hi );
    }

    /**
     * 将数组分为 arr[lo..i-1], arr[i], arr[i+1.. hi]
     */
    private int partition ( Comparable [] arr , int lo , int hi ) {
        // 随机在arr[lo...hi]的范围中, 选择一个数值作为标定点pivot，保证在数组近乎有序的情况下也能良好完成排序
        swap ( arr , lo , ( int ) ( Math . random () * ( hi - lo + 1 )) + lo );
        Comparable v = arr [ lo ];
        // 左右扫描指针
        int i = lo + 1 ;
        int j = hi ;
        while ( true ) {
            // 扫描左右，检查是否结束并交换元素
            // 注意条件，减少等值元素的交换，防止算法时间复杂度退化为 O(n^2)
            while ( i <= hi && arr [ i ]. compareTo ( v ) <= 0 ) {
                i ++;
            }
            while ( j >= lo && arr [ j ]. compareTo ( v ) > 0 ) {
                j --;
            }
            if ( i >= j ) {
                // 此时 j 一定指向的是小于或等于的元素
                break ;
            }
            swap ( arr , i , j );
        }
        swap ( arr , lo , j );
        return j ;
    }

    private void swap ( Comparable [] arr , int i , int j ) {
        Comparable e = arr [ i ];
        arr [ i ] = arr [ j ];
        arr [ j ] = e ;
    }
}

특허

 MIT License

Copyright (c) 2018 Angus

Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all
copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
SOFTWARE.